BMマッチングアルゴリズム

1414 ワード

まとめ:
KMPアルゴリズムは最も効率的なアルゴリズムではなく,実際にはあまり採用されていない.さまざまなテキストエディタの「検索」機能(Ctrl+F)は、Boyer-Mooreアルゴリズムを採用することが多い.
仮定文字列は「HERE IS A SIMPLE EXAMPLE」、検索語は「EXAMPLE」
E X A M P L E
0 1 2 3 4 5 6

悪文字ルール:移動位置=悪文字位置-検索語の前回出現位置7=EXAMPLE最後の文字E(6)-EXAMPLEでS(-1)好文字ルールが見つかりません:移動位置=好接尾辞文字位置(好接尾辞:一致文字列の最後の文字)-検索語の前回出現位置5=MPLEでのE位置(6)-EXAMPLでのE(1)
文章の詳細(http://www.ruanyifeng.com/blog/2013/05/boyer-moore_string_search_algorithm.html)
悪い文字の規則、良い文字の規則は位置を移動します
文字列:1 2 3 4 1 2 3 3 3 4 5 1 2 3検索語:7 5 3 4 5下付き:0 1 2 3 4
1 2 3 4 1 2 3 3 4 5 1 2 3 
7 5 3 4 5

悪い文字規則:
1と5は一致せず、1と検索語は一致しなかった.移動位置=悪文字位置-検索語の前回の出現位置(1前回出現位置、存在しない場合-1)5=4-(-1)
1 2 3 4 1 2 3 3 4 5 1 2 3
          7 5 3 4 5

5、5マッチング4、4マッチング3、3マッチング3、5不マッチング
悪い文字規則を押すと、次のようになります.
移動位置の処理:2=1-(-1)
1 2 3 4 1 2 3 3 4 5 1 2 3
              7 5 3 4 5

しかし、ここでは文字ルールを使用できます.
移動位置=接尾辞文字位置(接尾辞:一致文字列の最後の文字)-検索語の最後の出現位置(5最後の出現位置、存在しない場合-1)は移動位置を処理します:3=4-1
1 2 3 4 1 2 3 3 4 5 1 2 3
                7 5 3 4 5