引用ジャングル

Boyer-Moore文字列検索と呼ばれ、最近、その直感に反するアルゴリズムに衝撃を受けました。テキストが長くなるほど、処理速度が速くなるのです。

仕組みはこうです。ほとんどの基本的な検索アルゴリズムは左から右へ、文字を一つずつチェックしていきます。しかし、Boyer-Moore法はそれを逆転させ、検索パターン内を右から左へスキャンし、2つの巧妙なトリックを使って大きなテキストの塊をスキップします。巨大なテキストブロックの中で「 needle 」という単語を探しているところを想像してみてください。

1. 悪い性格のルール:

「needle」を検索していて、現在のテキスト文字が「z」の場合、その位置またはその前で一致が始まる可能性はありません。そのため、アルゴリズムは文字ごとにチェックするのではなく、6文字分（「needle」の全長）先へジャンプして、検索を続けます。

2. 良い接尾辞のルール:

「needle」を検索していて、最後に「dle」が一致したのに次の文字で一致が途切れた場合、アルゴリズムは次の文字からやり直すことはありません。代わりに、「dle」が「needle」の前の部分にあるかどうかを尋ねます。もしそうであれば、パターンをずらして、前の「dle」が一列になるようにします。そうでない場合は、「dle」の部分全体をスキップします。いずれの場合も、再確認に時間を無駄にすることなく、スマートに先に進みます。

これらのヒューリスティック スキップ戦略は完璧ではありませんが、ブルートフォース方式よりもはるかに効率的です。

その結果、テキストが長くなるにつれて、アルゴリズムはより多くの文字をスキップする傾向があり、入力サイズに対して速度が向上します。そのため、grepなどのツールは数ギガバイトのログを驚くべき速度で処理できます。