ライタアルゴリズム

コンピュータサイエンスにおいて、ライタアルゴリズムは、ボイヤー・ムーア・ホースプールアルゴリズムの性能を向上させる文字列検索アルゴリズムです。このアルゴリズムは、検索対象の文字列を前処理してパターンを検索する点で、ボイヤー・ムーアの文字列検索アルゴリズムに似ています。与えられた文字列内の特定の部分文字列の検索パターンは、ボイヤー・ムーア・ホースプールアルゴリズムとは異なります。このアルゴリズムは、1991年にティモ・ライタによって発表されました。[1]

説明

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

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

事前チェックがすべて成功した場合、最初の比較は最後から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 [ i ] = 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 [ ALPHABET_SIZE ];         
   

  /* クイックエッジケース。 */ 
if ( lpat == 0 || lpat > n ) return ;         
    

  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 ) { OUTPUT ( match_ptr - s ); match_ptr ++ ; } else return ; } }    
       
          
              
          
          
        
       
        
    
  

  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 ) OUTPUT ( j ); j += bmBc [ c ]; } }

例

パターン: abddb

テキスト：abbaabaabddbabadbb

前処理段階： 

  abd
  4 3 1

1回目の試み：
 abbaabaabddbabadbb
 ....b
 4シフト (bmBc[a])

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

試行2：
 abbaabaabddbabadbb
     AdB
 3シフト (bmBc[b])

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

3回目の試行：
 abbaabaabddbabadbb
        ABDDB
 3シフト (bmBc[b])

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

試行4：
 abbaabaABDDBabadbb
           ....b
 4シフト (bmBc[a])

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

計算量

  1. 前処理段階にはO(m)の時間がかかります。ここで「m」はパターン「P」の長さです
  2. 検索段階には O(mn) の時間計算量が必要です。ここで、「n」はテキスト「T」の長さです。

参照

参考文献

  1. ^ ab RAITA T., 1992, Boyer–Moore–Horspool文字列検索アルゴリズムのチューニング, Software - Practice & Experience, 22(10):879-884 [1]
  2. ^ 「⚙ D27068 string::find の改善」。LLVMコードレビュー。
  • Raitaアルゴリズムのアプレットアニメーションと説明
Retrieved from "https://en.wikipedia.org/w/index.php?title=Raita_algorithm&oldid=1157291016"