grepで文字列マッチングしている時の仕組みを学ぶために、BM法などの文字列マッチングについて調べていた。調べたことをメモしておく。特にまとまってはいない。
参考になった文献は以下。
- 文字列の中から効率良くキーワードを探し出せ：コーディングに役立つ！ アルゴリズムの基本（7）（3/4 ページ） - ＠IT
- BM法をJSで実装している
- とりあえずイメージ掴むのには分かりやすい
- サービス終了のお知らせ
- BM法や、その亜種のHorspool のアルゴリズムとQuick-Searchを解説している
- ちょっとわかりづらいけど、一番ちゃんと書かれている
すごく雑にイメージすると、
- パターンの方に前処理を加えて、ある文字がパターンの中のどの位置にあるかを保存しておく
- パターンマッチングしていきマッチしなかった場合に、前処理で作った位置情報を使っていい感じにスキップする
という感じ。雑すぎる。
BM法関連のアルゴリズムでは前処理はパターンの方に加え、検索をかける。このためSuffix Treeとか転置インデックスみたいなアルゴリズムと比べ、検索は効率が低下するものの、前処理のコストは少なくなる。そのため一回きりの検索を行うようなgrepのようなものに利用されることが多いようだった。
