読者です 読者をやめる 読者になる 読者になる

FPGA開発日記

FPGAというより、コンピュータアーキテクチャかもね! カテゴリ別記事インデックス https://sites.google.com/site/fpgadevelopindex/

Boyer-Moore-Horspoolアルゴリズムの勉強

f:id:msyksphinz:20160427013856p:plain

(出展: http://wisdomdesign.jp/blog/archives/2755)

昔からアルゴリズムに興味があって、いろいろ未知のアルゴリズムを調べるのが好きなのだが、最近興味を持ったのは、silver-searcherにも使われているBoyer-Moor-Horspoolというアルゴリズムだ。

silver-searcherはgrepよりも高速な文字列検索コマンドで、会社でも自宅でもお世話になっている。 このアルゴリズムはどのような仕組みになっているのか調べた。

Boyer-Moor-Horspoolのアルゴリズムを調査するのに役に立ったビデオ

www.youtube.com

既存のアルゴリズムと比較したときの動作の違い、サンプルを使って解説している。最悪計算量は一緒だが、平均的な計算量は小さくなる、ということか。

まずはここまで。いろんな実装を見て勉強したり、ハードウェア化する場合について調査してみたい。