【ボイヤームーアほう】
ボイヤー・ムーア法 とは？
公開:
💡 後ろから比べて、あり得ない位置は飛び越える
探す文字列を末尾側から照合し、不一致で得た情報から比較位置を先へずらす文字列検索法。一致し得ない位置を飛ばして比較を減らす。
📌 このページのポイント
- 各候補位置ではパターンの右端から左へ比較する
- 不一致文字や一致済みの末尾部分を利用して、安全にずらせる量を求める
- 飛ばせる距離や性能は文字列と実装に依存し、常に大きく飛べるわけではない
ひよこ 文字列なのに、後ろから探すの？
ペンギン先生 本文全体を後ろから読むわけではないよ。本文上に探すパターンを置き、その範囲をパターンの右端から左へ照合するんだ。不一致になったら、その情報を使ってパターンを右へずらすよ。
ひよこ どんなときに飛ばせるの？
ペンギン先生 本文がZZXCATで、探す文字列がCATだとしよう。最初は右端のTと本文のXが不一致になる。XはCATのどこにもないので、1文字や2文字ずらした位置にも一致はない。3文字ずらしてCATの位置まで進めるんだ。
ひよこ Xがパターンに含まれていたら？
ペンギン先生 その文字の位置に応じて、ずらせる距離を小さくするよ。これが不一致文字の規則だね。標準的なボイヤー・ムーア法では、すでに一致した末尾部分を利用する規則も組み合わせる。資料やライブラリによって片方だけの変種もあるので区別しよう。
ひよこ 毎回3文字ずつ進むなら、3倍速い？
ペンギン先生 そうは言えないよ。図で3文字飛べたのは、その入力だからなんだ。似た文字が繰り返される場合には、飛ばせる距離が小さくなることもある。前処理のコストや使う規則も含めて、対象の文章で効果を確認する必要があるね。
もっと詳しく知りたい人へ
最悪でも本文の長さに比例する時間ですか？
変種と検索条件を区別します。不一致文字規則だけの単純な実装では、本文長n・パターン長mに対し最悪O(nm)となり得ます。全一致の列挙を含む性能保証も実装次第なので、「ボイヤー・ムーア法なら必ず線形時間」とまとめないようにします。
まとめ：ざっくりこれだけ覚えればOK！
「ボイヤー・ムーア法」って出てきたら「右から照合し、不一致の情報で先へ進む文字列検索」と思えればだいたいOK！