Boyer-Moore法入門：理論・実装・最適化ガイド

2025年12月12日 最終更新日時 : 2025年12月12日 エバープレイ編集部

概要

Boyer-Moore法は、1977年に Robert S. Boyer と J Strother Moore によって提案された文字列検索アルゴリズムで、パターンマッチングにおいて非常に効率的であることで知られます。一般的なテキスト検索（テキスト中にパターンが出現する位置を探す）で、平均的には探索の際にウィンドウを多く飛ばせるためサブリニアな振る舞いを示します。検索の高速化は主に「バッドキャラクタ（悪い文字）則」と「グッドサフィックス（良い接尾辞）則」という2つのシフト戦略に基づいています。

基本アイデアとメリット

従来の左から右に1文字ずつ比較するアルゴリズムと異なり、Boyer-Moore法はパターンの右端から比較を始めます。右端からの比較により、照合が失敗した時に比較済み領域の情報を活用してパターンを大きくシフトできることが多く、これが高速化の源です。

  • 平均的には探索がサブリニア（テキスト長に対して比較回数が少ない）
  • 短いパターンやデータ内のランダム性が高い場合に特に高速
  • 事前処理でテーブルを作るので、同一パターンで複数検索すると効果的

主な2つのヒューリスティック

バッドキャラクタ則（Bad Character Heuristic）

比較が失敗した位置にあるテキスト中の文字（悪い文字）を見て、パターン内でその文字が最右に出現する位置までパターンをシフトする方法です。パターンにその文字が存在しなければ、パターン全体をウィンドウの次に移動させることができます。

実装上はアルファベット（文字集合）ごとに、パターン内での直近の出現位置を保持するテーブル（bad-character table）を作ります。作成時間は O(m + |Σ|)（m はパターン長、|Σ| は文字集合サイズ）で、検索時は失敗位置に応じて O(1) でシフト幅を計算できます。

グッドサフィックス則（Good Suffix Heuristic）

パターンの右端から比較して、ある接尾辞（サフィックス）が一致したがその直前の文字で失敗した場合に、その一致したサフィックスともう一度重ならないように最適にシフトする方法です。具体的には次のいずれかの位置までシフトします：

  • パターン内にそのサフィックスと同じ文字列が別に現れる直後（サフィックスの別位置への一致）
  • パターンの接頭辞が、サフィックスの最大の真の接尾部分（prefix-suffix）と一致する位置

このヒューリスティックを実装するには、サフィックス長や補助的な配列（一般に L[]、l'[] あるいは最長接尾接頭配列）を前処理で計算します。これにより、失敗時に適切なシフト値を O(1) で得られるようにします。

グッドサフィックス則の前処理（少し詳しく）

グッドサフィックス則の前処理はやや複雑です。代表的な手順は以下のとおりです。

  • パターン P の各位置 i について、P[i..m-1]（i から末尾までの接尾辞）が P 内のどこに再出現するかを調べ、再出現位置情報 L[i] を作る。
  • さらに、パターンのある接尾辞が接頭辞と一致する最長長さを示す配列 l'（しばしば small-l と記述）を求める。これは接尾辞がパターン先頭に接続できるか調べるのに使う。
  • これらの配列は最終的に、位置 i で失敗したときのシフト量を決定するために利用される。

計算は線形時間 O(m) で可能とされています（いくつかの実装上の技巧を用いる）。

アルゴリズムの統合（比較からシフトまで）

実際の探索では、ウィンドウの右端から左へ比較を進め、失敗した位置 k に対して以下を計算します。

  • bad = k - lastOccur[text[k]] （bad-character に基づくシフト）
  • good = (m - 1 - k) に基づくグッドサフィックス由来のシフト（L や l' を参照）
  • 実際のシフトは max(bad, good) を取る（2つのルールのうち安全に最も進める量を採用）

この合算により、比較済み文字を無駄にせず正当な大きな移動を行うことができます。

計算量

一般的な性質として：

  • 前処理時間：O(m + |Σ|)（bad-character テーブルの構築は |Σ| を使う場合）
  • 前処理メモリ：O(|Σ| + m)（文字集合が大きい場合、bad-character の扱いに注意）
  • 平均時間：多くの実用データでサブリニアな動作（比較回数がテキスト長より小さくなる）
  • 最悪時間：適切に実装し最適化（例えば Galil のルールなど）を入れると線形 O(n + m) を達成可能とされる。単純な実装や特定の悪いパターン・テキストの組合せでは理論的に悪化するケースが存在するため、実装上の配慮が重要です。

要するに、Boyer-Moore は平均的に非常に速く、最悪ケース回避のためにも実装で追加の工夫を行うことが推奨されます。

実用上の派生と簡易化

Boyer-Moore の完全版は前処理がやや重く実装も複雑です。実用的には以下の派生や簡易化がよく使われます。

  • Horspool 法：グッドサフィックスを省略し、バッドキャラクタ則だけを使うシンプルな変種。実装が簡単で高速であるため多くの実用環境で採用される。
  • Sunday のアルゴリズム（Sunday's Quick Search）：ウィンドウの右端の次の文字を見てシフトを決めるシンプルで高速な方法。実装コストが低い。
  • Turbo Boyer-Moore：直前のマッチ結果を利用して追加の最適化を行う変種。
  • 正規表現エンジンやテキスト検索ツール（grep, agrep など）では、実用的な高速化（Horspool をベースにした実装や、複数ヒューリスティックの組合せ）が取り入れられていることが多い。

実装上の注意点

実装するときに注意すべき点をまとめます。

  • 文字集合（|Σ|）が大きい場合（Unicode やマルチバイト文字）、bad-character テーブルを単純に全コードポイント分用意するのは現実的でない。ハッシュマップや配列の圧縮表現を使うとよい。
  • エンコーディング（UTF-8 など）では、バイト列に対する検索と文字列（コードポイント）に対する検索を区別する必要がある。多バイト文字列はコードポイント単位で扱うとアルゴリズム設計が変わる。
  • インデックスのオフバイワンや配列境界の管理に注意。右端から比較するため、位置計算を慎重に行う。
  • 最悪ケース対策として Galil の最適化を入れるか、あるいは簡便な実装なら Horspool や Sunday を選ぶことも検討する。
  • キャッシュ効率や分岐予測も実行速度に影響する。ループ内での余分な処理を避け、テーブル参照を局所化するのが望ましい。

実装例（擬似的な流れ）

高水準では以下の流れになります。

  • 前処理：bad-character テーブルを作る（各文字に対してパターン中の最後の出現位置を設定）、グッドサフィックス関連の配列を計算する。
  • 検索：テキスト上のウィンドウを右端から比較。失敗が起きたら bad と good を計算し、max(bad, good) だけシフトする。成功なら位置を報告してシフト（通常は次の可能な一致へ）を行う。

実際のコードではインデックス管理やループ条件、Unicode 対応などを丁寧に実装します。

ユースケースと実世界での採用例

Boyer-Moore およびその変種は次のような場面で有効です。

  • 巨大なテキストデータからのパターン検索（ログ解析、テキストマイニング）
  • テキストエディタやコマンドラインツール（grep 系）での高速検索
  • 単一パターンを多数のテキストに繰り返し検索するバッチ処理

一方、パターンが短すぎる場合や極端に小さなアルファベット（例えば DNA シーケンスの 4 文字）ではビット演算を使った Shift-Or/Shift-And などのアルゴリズムが有利なことがあります。

まとめ

Boyer-Moore法は、右端からの比較と2種類のヒューリスティックにより多くの実問題で非常に効率よく働く文字列検索アルゴリズムです。実装はやや複雑ですが、前処理をしっかり行えば平均的に高速に動作します。実用上は Horspool や Sunday のような簡易変種、また Galil のルールなどの最適化を組み合わせて使うことが多いです。Unicode や大きな文字集合を扱う際は前処理テーブルの設計に注意してください。

参考文献

カテゴリー
IT
前の記事
ジョージ・キューカー──「女優の監督」が築いたハリウッド黄金期の美学と遺産New!!
2025年12月12日
次の記事
エルンスト・ルビッチの魅力とLubitsch Touch：映画史を変えたコメディの魔術師New!!
2025年12月12日