Bitapアルゴリズム

ウィキペディアから、無料の百科事典
ナビゲーションにジャンプ 検索にジャンプ

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

bitapアルゴリズムは、Unix ユーティリティ agrepの基礎となるアルゴリズムの1つとしておそらく最もよく知られており、 Udi ManberSun Wu、およびBurraGopalによって作成されています。ManberとWuの元の論文は、一般的な正規表現のあいまい一致を処理するためのアルゴリズムの拡張を提供します

アルゴリズムに必要なデータ構造により、一定の長さ(通常は問題のマシンの単語の長さ)未満のパターンで最高のパフォーマンスを発揮し、小さなアルファベットよりも入力を優先します。ただし、特定のアルファベットと語長mに対して実装されると、その実行時間は完全に予測可能になります。テキストの構造やパターンに関係なく 、 Omn )操作で実行されます。

正確な文字列検索のためのbitapアルゴリズムは、1964年にBálintDömölkiによって発明され[1] [2]、1977年にRK Shyamasundarによって拡張され[3] 1989年にRicardoBaeza -YatesGastonGonnetによって再発明されました(1章筆頭著者の博士論文[5])も拡張して、文字、ワイルドカード、および不一致のクラスを処理できるようにしました。1991年に、ManberWu [6] [7]によって拡張され、挿入と削除(完全なあいまい文字列検索)も処理できるようになりました。このアルゴリズムは、1996年にBaeza-YatesとNavarroによって後で改善されました。 [8]

正確な検索

正確な文字列検索のbitapアルゴリズムは、一般的に、擬似コードでは次のようになります。

アルゴリズムbitap_search
    入力されます:文字列としての テキスト文字列としてのパターン出力:文字列
    m  :=長さ(パターン

     m = 0の場合、テキスト
        返します 

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

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

         R [ m ]の場合
            returntext + i --m  + 1

    nullを
返す

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

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

 #include <string.h> 
 #include <limits.h> 
 
 const char * bitap_bitwise_search const char * text const char * pattern        
 {{
     int m = strlen パターン);   
     unsigned long R ;  
     unsigned long pattern_mask [ CHAR_MAX + 1 ];  
     int i ; 
 
     if pattern [ 0 ] == '\ 0' return text ;     
     if m > 31 return "パターンが長すぎます!" ;     
  
     /*ビット配列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 ; _       
     }
 
     NULLを返します; 
 }

あいまい検索

bitapアルゴリズムを使用してあいまい文字列検索を実行するには、ビット配列Rを2次元に拡張する必要があります。テキストの長さ全体で変化する単一の配列Rを使用する代わりに、 k個の異なる配列R 1..kを使用できるようになりました。配列Riは、 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 パターン);   
     unsigned long * R ;  
     unsigned long pattern_mask [ CHAR_MAX + 1 ];  
     int i d ;  
 
     if pattern [ 0 ] == '\ 0' return text ;     
     if m > 31 return "パターンが長すぎます!" ;     
 
     /*ビット配列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 ))){        
             結果= テキスト+ i --m + 1 ; _      
             休憩;
         }
     }
 
     無料R );
     結果を返す; 
 }

も参照してください

外部リンクと参照

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