ボイヤー・ムーア文字列検索アルゴリズム

コンピュータサイエンスにおいて、Boyer–Moore 文字列検索アルゴリズムは、実用的な文字列検索に関する文献の標準的なベンチマークとなっている効率的な文字列検索アルゴリズムです。 ^{[ 1 ]}これは、 1977 年にRobert S. BoyerとJ Strother Mooreによって開発されました。^{[ 2 ]}元の論文には、パターンシフトを計算するための静的テーブルが含まれていましたが、それらの生成方法については説明されていませんでした。テーブルを生成するアルゴリズムは、後続の論文で発表されました。この論文には、後にWojciech Rytterによって1980 年に修正されたエラーが含まれていました。 ^{[ 3 ] [ 4 ]}

このアルゴリズムは、検索対象の文字列（パターン）を前処理しますが、検索対象の文字列（テキスト）は前処理しません。そのため、パターンがテキストよりもはるかに短い場合や、パターンが複数の検索にわたって継続する場合に適しています。Boyer–Mooreアルゴリズムは、前処理ステップで収集した情報を使用してテキストのセクションをスキップするため、他の多くの文字列検索アルゴリズムよりも定数係数が低くなります。一般的に、パターンの長さが長くなるにつれて、アルゴリズムの実行速度は速くなります。このアルゴリズムの主な特徴は、パターンの先頭ではなく末尾でマッチングを行い、テキスト内のすべての文字を検索するのではなく、複数の文字単位でテキストをスキップすることです。

• Tは検索対象の入力テキストを表します。その長さはnです。
• Pは検索対象の文字列を表し、パターンと呼ばれます。その長さはmです。
• S [ i ]は、文字列Sのインデックスiにある文字を表し、インデックスは 1 から始まります。
• S [ i .. j ]は、文字列Sのインデックスiからjまでの部分文字列を表します。
• Sの接頭辞は、範囲 [1, l ]内のiに対する部分文字列S [1.. i ] であり、 lはSの長さです。
• Sの接尾辞は、範囲 [1, l ]内のiに対する部分文字列S [ i .. l ] であり、 lはSの長さです。
• PとTのアライメントとは、 Pの最後の文字が T のインデックス k に揃うようなTのインデックスkのことである。
• PがT [( k - m +1).. k ]と等しい場合、アライメントk でPの一致または出現が発生します。

Boyer–Mooreアルゴリズムは、異なるアライメントで明示的な文字比較を行うことにより、T中のPの出現箇所を探索します。すべてのアライメント（その数は⁠${\displaystyle n-m+1}$Boyer –Mooreは、 Pの前処理によって得られた情報を使用して、可能な限り多くのアライメントをスキップします。

このアルゴリズムが導入される以前は、テキスト内を検索する一般的な方法は、テキストの各文字を調べてパターンの最初の文字を探すことでした。パターンの最初の文字が見つかると、テキストの残りの文字がパターンの文字と比較されます。一致する文字が見つからない場合は、再びテキストを文字ごとにチェックして一致を探します。そのため、テキスト内のほぼすべての文字を調べる必要がありました。

このアルゴリズムの重要な点は、パターンの末尾をテキストと比較する場合、テキストのすべての文字をチェックするのではなく、テキストに沿ってジャンプできることです。この仕組みが機能する理由は、パターンをテキストに合わせる際に、パターンの最後の文字がテキスト内の文字と比較されるためです。文字が一致しない場合は、テキストに沿って逆方向に検索を続ける必要はありません。テキスト内の文字がパターン内のどの文字とも一致しない場合、次にチェックするテキスト内の文字は、パターンの長さをmとした場合、テキスト内でm文字先にあります。テキスト内の文字がパターン内にある場合は、一致する文字に合わせてパターンをテキストに沿って部分的にシフトし、このプロセスを繰り返します。テキスト内のすべての文字をチェックするのではなく、テキストに沿ってジャンプして比較を行うことで、比較回数を減らすことができ、これがこのアルゴリズムの効率性の鍵となります。

より厳密には、アルゴリズムはアライメントから始まります。${\displaystyle k=m}$⁠ 、そのためPの開始位置がTの開始位置と揃います。次に、 PのインデックスmとTのインデックスkから逆方向に移動して、 PとTの文字を比較します。文字列はPの末尾からPの開始位置まで。比較は、 Pの開始位置に到達するか (一致があることを意味します)、不一致が発生して、いくつかのルールで許可されている最大値に従ってアライメントが前方 (右方向) にシフトされるまで続きます。比較は新しいアライメントで再度実行され、アライメントがTの末尾を超えてシフトされるまで(つまり、それ以上一致が見つからないまで) プロセスが繰り返されます。

シフトルールは、 Pの前処理中に生成されたテーブルを使用して、定数時間テーブルルックアップとして実装されます。

シフトは、不良文字ルールと良接尾辞ルールの2つのルールを適用して計算されます。実際のシフトオフセットは、これらのルールによって計算されたシフトの最大値となります。

インデックス｜不一致｜シフト 0 | N| 1 1 | AN| 8 2 | 男性 | 3 3 | NMAN| 6 4 | アンマン | 6 5 | パンマン| 6 6 | NPANMAN| 6 7 |アンパンマン| 6

ボイヤー・ムーアの単純だが重要な最適化は、 1979 年にZvi Galilによって提案された。^{[ 7 ]} シフトとは対照的に、Galil ルールは、一致することがわかっているセクションをスキップすることで、各アライメントで実際に行われる比較を高速化する。アライメントk ₁で、PがTの文字cまでTと比較されると仮定する。次に、Pがk ₂にシフトされ、その左端がcとk ₁の間にある場合、次の比較フェーズでは、Pの接頭辞が部分文字列T [( k ₂ - n ).. k ₁ ]と一致する必要がある。したがって、比較がTの位置k ₁まで進むと、 k ₁より前の部分を明示的に比較することなく、 Pの出現を記録できる。ボイヤー・ムーアの効率を高めることに加えて、Galil ルールは最悪の場合の線形時間実行を証明するために必要である。

Galil ルールは、元のバージョンでは、複数の一致を出力するバージョンにのみ有効です。部分文字列の範囲はc = 0、つまり完全一致の場合にのみ更新されます。部分一致を扱うための一般化されたバージョンは、1985 年にApostolico–Giancarlo アルゴリズムとして報告されました。^{[ 8 ]}

原論文で提示されたボイヤー・ムーアアルゴリズムの最悪実行時間は⁠${\displaystyle O(n+m)}$パターンがテキストに現れない場合に限ります。これは、 1977 年にKnuth、 Morris、およびPrattによって最初に証明され^{[ 3 ]} 、続いて1980 年にGuibasとOdlyzkoによって最悪の場合の上限が5 n の比較で証明されました^{[ 9 ]} 。Richard Cole は1991 年に最悪の場合の上限が3 nの比較^{で証明を与えました[ 10 ]。BM}アルゴリズムの簡単な修正により、上限が2 n に改善されます^{[ 11 ]}。

テキスト中にパターンが出現する場合、元のアルゴリズムの実行時間は⁠${\displaystyle O(nm)}$最悪の場合。これは、パターンとテキストの両方が同じ繰り返し文字のみで構成されている場合、簡単にわかります。ただし、ガリル規則を含めると、^すべてのケースで線形実行時間になります。 [ ^{7 ] [ 10 ]}

Knuth、Morris、Pratt は、ランダムなテキストの場合、文字比較の平均回数は次のように制限される ことも示しました。${\displaystyle O\left({\frac {n\log _{k}m}{m}}\right)}$、 どこ${\displaystyle k}$はアルファベットのサイズです。

さまざまなプログラミング言語で、多様な実装が存在します。C ++では、C++17以降、標準ライブラリの一部となっており、Boostでは、アルゴリズムライブラリに汎用的なBoyer–Moore検索の実装が提供されています。Go （プログラミング言語）では、 search.goに実装があります。D （プログラミング言語）では、Phobosランタイムライブラリの一部として、範囲内での述語ベースのマッチングにBoyerMooreFinderを使用しています。

Boyer–MooreアルゴリズムはGNUのgrepでも使用されています。^{[ 12 ]}

Boyer –Moore–Horspoolアルゴリズムは、Boyer–Mooreアルゴリズムを簡略化したもので、不良文字ルールのみを使用します。

アポストリコ・ジャンカルロアルゴリズムは、明示的な文字比較を省略することで、指定されたアライメントで一致が発生したかどうかをチェックする処理を高速化します。このアルゴリズムは、パターンの前処理中に得られた情報と、各一致試行時に記録された接尾辞一致長を組み合わせて使用​​します。接尾辞一致長を保存するには、検索対象のテキストと同じサイズのテーブルを追加で用意する必要があります。

Raitaアルゴリズムは、Boyer–Moore–Horspoolアルゴリズムの性能を向上させます。与えられた文字列の中から特定の部分文字列を検索するパターンは、Boyer–Moore–Horspoolアルゴリズムとは異なります。

• Boyer-Mooreアルゴリズムに関するオリジナル論文
• アルゴリズムの共同発明者であるJ・ストローザー・ムーアのホームページに掲載されているボイヤー・ムーア・アルゴリズムの例。
• リチャード・コールの1991年の論文は、実行時間の線形性を証明している。