簡略化されたボイヤームーアアルゴリズム

文字列内の部分文字列検索アルゴリズムに関する記事を読んだ後、ボイヤー・ムーアアルゴリズムについて話していないことがわかりました。 彼についてのいくつかの言葉はまだそこにあります。つまり、平均して最良の検索時間を与えるので、ボイヤー・ムーア・アルゴリズムは「デフォルト・アルゴリズム」のタイトルを獲得したと言われています。 猫の下では、このアルゴリズムの簡略版が説明されています。 原則として、大学の1年目または2年目（私のような）にこのアルゴリズムを研究した可能性が最も高いので、この記事をスキップできます。

アルゴリズム

このアルゴリズムは、Boyer-Moore-Horspoolアルゴリズムとも呼ばれます。 アルゴリズムの手順は非常に簡単です。 まず、文字ごとにオフセットテーブルが作成されます。 次に、元の行とテンプレートが最初に結合され、最後の文字によって比較が実行されます。 最後の文字が一致する場合、比較は最後から2番目の文字に続きます。 文字が一致しなかった場合、パターンはソース文字列の文字の変位テーブルから取得した位置の数だけ右にシフトされ、再びソース文字列とパターンの最後の文字が比較されます。 など、パターンがソース文字列の部分文字列に完全に一致するまで、または文字列の最後に到達するまで。

オフセット表

オフセットテーブルは、「できるだけ多くの文字をスキップしますが、それ以上にしない」という原則に基づいて構築されています。 たとえば、アルゴリズムのあるステップで最後の文字が一致せず、ソース行にある文字がテンプレートにまったく存在しない場合、恐れることなくテンプレートの全長まで移動できることは明らかです。 一般的な場合、各シンボルには、テンプレートの長さとシンボルのシリアル番号との差に等しい値が割り当てられます（シンボルが繰り返される場合、右端のオカレンスが取得されます）。 行の終わりから数えると、この値が文字の序数と正確に等しくなり、可能な最大位置数だけ右にシフトできることは明らかです。

イラスト

完全に明確にするために、アルゴリズムの動作を例として考えてください。

ソース文字列を「somestring」とし、パターンを「string」に等しくします。 これでオフセットテーブルが作成されます。これは、パターンに表示されないすべての文字のパターンの長さと、残りの最後からのシリアル番号に等しくなります（最後のものを除き、パターンの長さも考慮されます）。



s->5

t->4

r->3

i->2

n->1

g->6







次に、行を結合します。

somestring

string







最後の文字を比較します。「t」は「g」と等しくないことがわかります。 シンボル "t"のオフセット値を取得します。これは4です。ラインを4ポジション右にシフトします。



somestring

string







次に、アルゴリズムは、テンプレートの最後の文字から最初の文字を、ソース文字列の対応する文字と比較します。 彼が後者を比較するとすぐに、これが最初の発生であることがわかります。

コード

この理論を盛り上げるために、Javaコードをいくつか書きました。 コメントを歓迎します。

 /** *      template   source,  * -1,      . * * @param source *  ,     . * @param template *  ,     source. * @return     template   source,  -1, *      . */ public int getFirstEntry(String source, String template) { int sourceLen = source.length(); int templateLen = template.length(); if (templateLen > sourceLen) { return -1; } HashMap<Character, Integer> offsetTable = new HashMap<Character, Integer>(); for (int i = 0; i <= 255; i++) { offsetTable.put((char) i, templateLen); } for (int i = 0; i < templateLen - 1; i++) { offsetTable.put(template.charAt(i), templateLen - i - 1); } int i = templateLen - 1; int j = i; int k = i; while (j >= 0 && i <= sourceLen - 1) { j = templateLen - 1; k = i; while (j >= 0 && source.charAt(k) == template.charAt(j)) { k--; j--; } i += offsetTable.get(source.charAt(i)); } if (k >= sourceLen - templateLen) { return -1; } else { return k + 1; } }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

おわりに

Boyer-Mooreアルゴリズムのこのような変更は、元のアルゴリズム自体よりもランダムテキストをより適切に処理すると言われています。 ただし、最悪の場合の難易度はさらに悪くなります。 ただし、元のアルゴリズムとは異なり、ここでは複雑な計算は必要ありません。オフセットのテーブルのみが構築され、実装はそれほど難しくありません。