(出展: http://wisdomdesign.jp/blog/archives/2755)
昔からアルゴリズムに興味があって、いろいろ未知のアルゴリズムを調べるのが好きなのだが、最近興味を持ったのは、silver-searcherにも使われているBoyer-Moor-Horspoolというアルゴリズムだ。
silver-searcherはgrepよりも高速な文字列検索コマンドで、会社でも自宅でもお世話になっている。 このアルゴリズムはどのような仕組みになっているのか調べた。
Boyer-Moor-Horspoolのアルゴリズムを調査するのに役に立ったビデオ
既存のアルゴリズムと比較したときの動作の違い、サンプルを使って解説している。最悪計算量は一緒だが、平均的な計算量は小さくなる、ということか。
まずはここまで。いろんな実装を見て勉強したり、ハードウェア化する場合について調査してみたい。
