$shibayu36->blog;

株式会社はてなでエンジニアをしています。プログラミングや読書のことなどについて書いています。

BM法による文字列マッチング学習メモ

grepで文字列マッチングしている時の仕組みを学ぶために、BM法などの文字列マッチングについて調べていた。調べたことをメモしておく。特にまとまってはいない。

参考になった文献は以下。

すごく雑にイメージすると、

  • パターンの方に前処理を加えて、ある文字がパターンの中のどの位置にあるかを保存しておく
  • パターンマッチングしていきマッチしなかった場合に、前処理で作った位置情報を使っていい感じにスキップする

という感じ。雑すぎる。

BM法関連のアルゴリズムでは前処理はパターンの方に加え、検索をかける。このためSuffix Treeとか転置インデックスみたいなアルゴリズムと比べ、検索は効率が低下するものの、前処理のコストは少なくなる。そのため一回きりの検索を行うようなgrepのようなものに利用されることが多いようだった。