導入
Boyer-Mooreアルゴリズムは、特に効率的な部分文字列検索アルゴリズムです。 1977 年にBob BoyerとJ Strother Mooreによって開発されました。
時間効率/複雑さ
Boyer-Moore アルゴリズムは、多数の反復検索を実行することでテキストの前処理コストを償却する特定のアルゴリズムとは異なり、テキスト(つまり、検索が実行される文字列) ではなく、部分文字列 (つまり、検索された文字列) を前処理します。 。 Boyer-Moore アルゴリズムの実行コストは準線形にすることができます。つまり、テキスト内の各文字をチェックする必要はなく、文字間の一部をスキップできます。一般に、部分文字列の長さが長くなるにつれて、アルゴリズムは高速になります。この効率は、2 つの文字列 (テキストと部分文字列) の照合が失敗するたびに、この失敗から推定される情報を使用して、チェックする位置をできるだけ多く削除するという事実から来ています。
「ブルート フォース」方法 (最初にテキスト全体で部分文字列の最初の文字の一致を検索し、次に次の文字が一致するかどうかをチェックすることで部分文字列を検索します) を使用した基本的な検索方法と、その時間計算量(たとえば、比較する文字のペアの数に応じて) はO ( L · K ) で増加します。ここでK は検索されるキー部分文字列の長さ、 L はキー (Boyer) が少なくとも 1 回出現する場合に検索する長さです。 -Moore アルゴリズムは、一度に出現箇所を見つけることができます。
- 最も好ましいケースではO ( L / K ) のオーダーです。この最良のケースでは、 Mのうち 1 文字だけをチェックする必要があります。したがって、部分文字列が長ければ長いほど、アルゴリズムによる部分文字列の検索効率が高くなります。
- 最悪の場合はO ( L + K ) のオーダーになります ( 2 番目の出現チェック テーブルを備えた改良されたアルゴリズムを使用)。
- そして、非常に多くの場合、最良の場合よりわずかに長い時間になります (キーの長さKが増加すると、その可能性はますます高くなります)。最悪のケースは、テキストに同じ文字が非常に多く含まれており、検索キーの最初の文字が異なる場合を除いて、文字列の末尾にこの頻繁に出現する文字が何度も含まれている場合に発生します。
一致があるかどうかを確認するには、平均的に約 (3 · K ) 回の比較が必要です。証明はリチャード・コールによるものです。
最悪の場合、すべての一致を見つける際の基本アルゴリズム (2 番目の出現チェック テーブルを使用したバリアントなし) のパフォーマンスはO ( K · L ) のオーダーになります。最悪のケースは、部分文字列が単一文字の繰り返しで構成され、テキストがこの同じ文字の ( K – 1) 倍の繰り返しに対応し、その前に別の異なる文字が 1 つある場合に発生します。このシナリオでは、アルゴリズムは、一致ごとにテキスト内の ( L – K + 1) 個の異なるオフセットをチェックする必要があります。ただし、これらの検証にはそれぞれK 回の比較が必要です。
最悪の場合でもサブリニアな動作を可能にする 2 番目のテーブルを備えたバリアントに興味があるため、このバリアントについてここで説明します (現在、C/C++、Java などの多くのテキスト処理ライブラリに統合されているバリアントです)。
