ビットタップアルゴリズム

ビットタップ アルゴリズム(シフト オア、シフト アンド 、またはBaeza-Yates-Gonnetアルゴリズムとも呼ばれる) は、近似文字列マッチングアルゴリズムです。このアルゴリズムは、指定されたテキストに、指定されたパターンと「ほぼ等しい」部分文字列が含まれているかどうかを判断します。ここで、近似等価性はレーベンシュタイン距離で定義されます 。部分文字列とパターンが互いに指定された距離k以内にある場合、アルゴリズムはそれらを等しいと見なします。このアルゴリズムは、パターンの各要素につき 1 ビットを含むビットマスクのセットを事前に計算することから開始します。その後、非常に高速な ビット単位の演算でほとんどの作業を実行できます。

bitap アルゴリズムは、おそらく、Udi Manber 、Sun Wu、Burra Gopalによって書かれたUnix ユーティリティ agrepの基盤となるアルゴリズムの 1 つとして最もよく知られています。Manber と Wu の元の論文では、一般的な正規表現のあいまい一致を処理するためのアルゴリズムの拡張が示されています。

このアルゴリズムに必要なデータ構造のため、一定の長さ (通常は問題のマシンのワード長) 未満のパターンで最もよく機能し、短いアルファベットよりも入力が優先されます。ただし、特定のアルファベットとワード長mに対して実装されると、その実行時間は完全に予測可能になります。テキストやパターンの構造に関係なく、 O ( mn ) 回の演算で実行されます。

正確な文字列検索のためのビットタップアルゴリズムは、1964年にBálint Dömölkiによって発明され^{[1] [2]}、1977年にRK Shyamasundarによって拡張され^{[3] 、1989年に}Ricardo Baeza-YatesとGaston Gonnet ^[4]によって再発明され（筆頭著者の博士論文の1章^{[5] ）、文字のクラス、ワイルドカード、不一致も処理できるように拡張されました。1991年には、} ManberとWu ^{[6] [7]}によって挿入と削除も処理できるように拡張されました（完全なあいまい文字列検索）。このアルゴリズムは、後に1996年にBaeza-YatesとNavarroによって改良されました。 ^[8]

完全な一般論として、 正確な文字列検索のためのビットタップ アルゴリズムは、疑似コードで次のようになります。

アルゴリズムbitap_searchは、
    入力: 文字列としてのテキスト。
           文字列としての
    パターン。出力:文字列
    m  := length(パターン)

     m = 0の場合は
        テキストを返す 

    /* ビット配列 R を初期化します。 */
    R  :=ビットの新しい配列[ m +1] 、初期値はすべて0
     R [0] := 1

     i  := 0; i < length( text ); i += 1の場合
        /* ビット配列を更新します。 */
         k  := m ; k ≥ 1; k -= 1の場合、R [k] := R [ k - 1] & (テキスト[ i ] =パターン[ k - 1])を実行します。
            

         R [ m ]の場合は(
             text + i - m ) + 1を返す

    null
を返す

Bitap は、上記のプログラムの次の変更のように、単純なビット演算への自然なマッピングにおいて、他のよく知られた文字列検索アルゴリズムと一線を画しています。この実装では、直感に反して、値 0 の各ビットは一致を示し、値 1 の各ビットは不一致を示すことに注意してください。同じアルゴリズムを 0 と 1 の直感的なセマンティクスで記述することもできますが、その場合は、を設定するために内部ループR |= 1に別の命令を導入する必要があります。この実装では、値を左シフトすると右側にゼロがシフトされるという事実を利用しています。これはまさに必要な動作です。

CHAR_MAXまた、一般的な実装の条件をビット単位の演算に変換するには、追加のビットマスクが必要であることにも注意してください(text[i] == pattern[k-1])。したがって、ビットタップ アルゴリズムは、より小さいアルファベットの入力に適用するとパフォーマンスが向上します。

 #include <string.h> #include <limits.h> const char * bitap_bitwise_search ( const char * text , const char * pattern ) { int m = strlen ( pattern ); unsigned long R ; unsigned long pattern_mask [ CHAR_MAX + 1 ]; int i ; if ( pattern [ 0 ] == '\0' ) return text ; if ( m > 31 ) return "The pattern is too long!" ; /* ビット配列 R を初期化します */ R = ~ 1 ; /* パターン ビットマスクを初期化します */ for ( i = 0 ; i <= CHAR_MAX ; ++ i ) pattern_mask [ i ] = ~ 0 ; for ( i = 0 ; i < m ; ++ i ) pattern_mask [ pattern [ i ]] &= ~ ( 1UL << i ); for ( i = 0 ; text [ i ] != '\0' ; ++ i ) { /* ビット配列を更新 */ R |= pattern_mask [ text [ i ]]; R <<= 1 ; if ( 0 == ( R & ( 1UL << m ))) return ( text + i - m ) + 1 ; } return NULL ; } 
  
 
        
 
        
       
       
      
 
          
          
  
     
       
 
     
          
           
          
             
 
           
         
           
           
 
                
                    
     
 
      
 

ビットタップ アルゴリズムを使用してあいまい文字列検索を実行するには、ビット配列R を2番目の次元に拡張する必要があります。テキストの長さに応じて変化する単一の配列R を使用する代わりに、 k 個の異なる配列R _{1.. k}を使用します。配列R _{i は}、現在の文字列の任意のサフィックスにi個以下のエラーで一致するパターンのプレフィックスの表現を保持します。このコンテキストでは、「エラー」は挿入、削除、または置換です。これらの操作の詳細については、 レーベンシュタイン距離を参照してください。

以下の実装では、ファジー ビットタップ アルゴリズムを使用してファジー マッチング(最大k 個のエラーを含む最初の一致を返す) を実行します。ただし、置換のみに注意し、挿入や削除には注意しません (つまり、ハミング距離はkです)。前と同様に、 0 と 1 のセマンティクスは従来の意味とは逆になっています。

 #include <stdlib.h> #include <string.h> #include <limits.h> const char * bitap_fuzzy_bitwise_search ( const char * text , const char * pattern , int k ) { const char * result = NULL ; int m = strlen ( pattern ); unsigned long * R ; unsigned long pattern_mask [ CHAR_MAX + 1 ]; int i , d ; if ( pattern [ 0 ] == '\0' ) return text ; if ( m > 31 ) return "The pattern is too long!" ; /* ビット配列 R を初期化します */ R = malloc (( k + 1 ) * sizeof * R ); for ( i = 0 ; i <= k ; ++ i ) R [ i ] = ~ 1 ; /* パターンビットマスクを初期化します */ for ( i = 0 ; i <= CHAR_MAX ; ++ i ) pattern_mask [ i ] = ~ 0 ; for ( i = 0 ; i < m ; ++ i ) pattern_mask [ pattern [ i ]] &= ~ ( 1UL << i ); for ( i = 0 ; text [ i ] != '\0' ; ++ i ) { /* ビット配列を更新します */ unsigned long old_Rd1 = R [ 
  
  
 
          
 
         
        
       
       
       
 
          
          
 
     
          
          
           
 
     
          
           
          
             
 
           
         
             0 ]; 
R [ 0 ] |= pattern_mask [ text [ i ]]; R [ 0 ] <<= 1 ; for ( d = 1 ; d <= k ; ++ d ) { unsigned long tmp = R [ d ]; /* 置換だけが重要です */ R [ d ] = ( old_Rd1 & ( R [ d ] | pattern_mask [ text [ i ]])) << 1 ; old_Rd1 = tmp ; } if ( 0 == ( R [ k ] & ( 1UL << m ))) { result = ( text + i - m ) + 1 ; break ; } } free ( R ); return result ; } 
           
           
 
               
                 
             
                     
               
         
 
                 
                   
             
         
     
 
     
      
 

• 同意
• TRE（コンピューティング）

1. ^ Bálint Dömölki、「統語解析アルゴリズム」、計算言語学3、ハンガリー科学アカデミー、pp. 29–46、1964年。
2. ^ Bálint Dömölki, プロダクションルールに基づくユニバーサルコンパイラシステム, BIT Numerical Mathematics , 8(4), pp 262–275, 1968. doi :10.1007/BF01933436
3. ^ RK Shyamasundar、「Dömölkiのアルゴリズムを使用した優先順位解析」、 International Journal of Computer Mathematics、6(2)pp 105–114、1977年。
4. ^ Ricardo Baeza-Yates。「効率的なテキスト検索」。博士論文、ウォータールー大学、カナダ、1989 年 5 月。
5. ^ Udi Manber、Sun Wu。「エラーのある高速テキスト検索」技術レポート TR-91-11。アリゾナ大学 コンピュータサイエンス学部、ツーソン、1991 年 6 月。(gzip 圧縮された PostScript)
6. ^ Ricardo Baeza-Yates、Gastón H. Gonnet。「テキスト検索への新しいアプローチ」 Communications of the ACM、35(10): pp. 74–82、1992年10月。
7. ^ Udi Manber、Sun Wu。「エラーを許容する高速テキスト検索」 Communications of the ACM、35(10):pp.83–91、1992年10月、 doi :10.1145/135239.135244。
8. ^ R. Baeza-Yates および G. Navarro。近似文字列マッチングの高速アルゴリズム。Dan Hirchsberg および Gene Myers 編、『Combinatorial Pattern Matching (CPM'96)』、LNCS 1075、1 ～ 23 ページ、カリフォルニア州アーバイン、1996 年 6 月。
9. ^ G. Myers. 「動的プログラミングに基づく近似文字列マッチングのための高速ビットベクトルアルゴリズム」 Journal of the ACM 46 (3)、1999年5月、395–415。
10. libbitap は、ほとんどの正規表現に対してアルゴリズムを簡単に拡張できることを示す無料の実装です。上記のコードとは異なり、パターンの長さに制限はありません。
11. リカルド・バエサ＝イエーツ、ベルティエ・リベイロ＝ネト。最新の情報検索。 1999 年。ISBN 0-201-39829 -X。 
12. bitap.py - Wu-Manber 修正を加えた Bitap アルゴリズムの Python 実装。