Raita アルゴリズム

From Wikipedia, the free encyclopedia

コンピュータ サイエンスでは、Raita アルゴリズムは、Boyer–Moore–Horspool アルゴリズムのパフォーマンスを向上させる文字列検索アルゴリズムです。このアルゴリズムは、パターンを検索する文字列を前処理します。これは、Boyer-Moore 文字列検索アルゴリズムに似ています。特定の文字列内の特定の部分文字列の検索パターンは、Boyer–Moore–Horspool アルゴリズムとは異なります。このアルゴリズムは、1991 年に Timo Raita によって公開されました。[1]

説明

Raita アルゴリズムは、指定されたテキスト内のパターンの各文字を比較することにより、指定されたテキスト "T" 内のパターン "P" を検索します。検索は次のように行われます。テキスト「T」のウィンドウは、「P」の長さとして定義されます。

  1. 最初に、パターンの最後の文字がウィンドウの右端の文字と比較されます。
  2. 一致する場合、パターンの最初の文字がウィンドウの左端の文字と比較されます。
  3. 再度一致した場合は、パターンの中央の文字とウィンドウの中央の文字を比較します。

事前チェックのすべてが成功した場合、元の比較は 2 番目の文字から最後の 2 番目の文字まで開始されます。アルゴリズムのいずれかの段階で不一致がある場合、前処理フェーズで計算された不正な文字シフト関数が実行されます。不良文字シフト関数は、Boyer–Moore–Horspool アルゴリズムで提案されているものと同じです。[1]

同様の事前チェックの最新の定式化はstd::string::find、libc++ および libstdc++ の線形/二次文字列マッチャーである にあります。の適切に最適化されたバージョンを想定するとmemcmp、「元の比較」で文字をスキップしない方が、パターンが整列される可能性が高いため、より効率的になる傾向があります。[2]

Raita アルゴリズムの C コード

#include <limits.h> 
#include <stddef.h> 

#define ALPHABET_SIZE (1 << CHAR_BITS) /* 通常は 256 */

/* 前処理: BMH の不適切な一致テーブル。*/
static inline void preBmBc ( char * pat , size_t lpat , ptrdiff_t bmBc []) {         
  size_t i ; 
  for ( i = 0 ; i < ALPHABET_SIZE ; ++ i )       
    bmBc [] = lpat ;  
  for ( i = 0 ; i < lpat - 1 ; ++ i )         
    bmBc [ pat [ i ]] = lpat - i - 1 ;      
}

void RAITA ( char * pat , size_t lpat , char * s , size_t n ) {         
  ptrdiff_t bmBc [アルファベット_サイズ]; 

  /* クイック エッジ ケース。*/
  if ( lpat == 0 || lpat > n )       
    戻ります

  if ( lpat == 1 ) {    
    char * match_ptr = s ;   
    while ( match_ptr < s + n ) {      
      match_ptr = memchr ( match_ptr , pat [ 0 ], n - ( match_ptr - s ));        
      if ( match_ptr != NULL ) {    
        出力( match_ptr - s );  
        match_ptr ++ ;
      その他_ 
        戻ります
    }
  }

  preBmBc ( pat lpat bmBc );  

  /* プレマッチ ウィンドウ。*/
  char firstCh = pat [ 0 ];   
  char middleCh =パット[ lpat / 2 ];     
  char lastCh = pat [ lpat - 1 ];     

  /* 検索中 */
  ptrdiff_t j = 0 ;   
  while ( j <= n - m ) {      
    char c = s [ j + lpat - 1 ];       
    /* これにより、長いパターンでデータの局所性が損なわれる可能性があります。これらについては、
     * 事前テストの数を減らすか、より多くのクラスター化されたインデックスを使用することを検討してください。*/
    if ( lastCh == c && middleCh == s [ j + lpat / 2 ] && firstCh == s [ j ] &&                
        memcmp ( & pat [ 1 ], & s [ j + 1 ], lpat - 2 ) == 0 )      
      出力( j );
    j += bmBc [ c ];  
  }
}

パターン: abddb

テキスト:父父父

前処理段階:

  アブド
  4 3 1
試行 1:
 父アブドババドブ
 ....b
 4 シフト (bmBc[a])

パターンの最後の文字とウィンドウの右端の文字の比較。これは不一致であり、前処理段階の値に応じて 4 シフトされます。

試行 2:
 父アブドババドブ
     AdB
 3 シフト (bmBc[b])

ここでは、パターンの最後の文字と最初の文字が一致していますが、中間の文字は一致していません。そのため、前処理段階に応じてパターンがシフトされます。

試行 3:
 父アブドババドブ
        ABDDB
 3 シフト (bmBc[b])

ここで完全一致が見つかりましたが、それ以上進めなくなるまでアルゴリズムは続行されます。

試行 4:
 父ABDDBabadbb
           ....b
 4 シフト (bmBc[a])

この段階では、4 だけシフトする必要があり、パターンを 4 だけ移動することはできません。したがって、アルゴリズムは終了します。大文字の文字は、テキストのパターンと完全に一致しています。

複雑さ

  1. 「m」はパターン「P」の長さです。
  2. 「n」がテキスト「T」の長さである場合、検索ステージには O(mn) 時間の複雑さがかかります。

も参照

参考文献

  1. ^ a b RAITA T.、1992 年、Boyer–Moore–Horspool 文字列検索アルゴリズムのチューニング、ソフトウェア - 実践と経験、22(10):879-884 [1]
  2. ^ "⚙ D27068 string::find を改善" . LLVM コード レビュー

外部リンク