HorspoolのアルゴリズムとSunday's Quick Search - 似非学問的な手記
BM法についての記事を書いたとたんに、 「最速の文字列検索アルゴリズムってなんだ？」 と思って調べまくった次第です（；＾ω＾）。この無駄な凝り性はプラスにもマイナスにも働きそうで怖い。 そしたらBM法の亜種がいくつか研究されてるみたいですね。 んで、この亜種についての一般的な話を。 （あ、BM法の記事：http://d.hatena.ne.jp/g940425/20100522/1274520718 を見てない人はわかりにくいかもです（；´・ω・`）） Boyer-Mooreのアルゴリズムの要は、「テキストのどの文字で不一致が起こったか」によって一気に先へ先へとジャンプしていくところだったわけだ。 上のテキストから下のパターンを検索するとき、 BM法では、パターンの後ろから見ていって、 初めて不一致となったこの位置に パターン中の同じ文字を合わせることでパターンの位置を何文字か（例では二文
検索の歴史 一文字進化するのに掛かった年数は、なんと… - 当面C#と.NETな記録
文字列の高速検索の歴史を年表にしてみたんだけど、年表にしたらめちゃくちゃおもしろいことに気づいてしまいました！今日のエントリーは必見ですよ！ id:siokoshou:20060323 に書いた EXACT STRING MATCHING ALGORITHMS に各論文の発表された雑誌が載ってたので、年表に並べてみました。いろいろ検索しててあちこちでみかけた名前だけ並べてます。 1977 KMP 1977 BM (Boyer-Moore algorithm) 1980 BMH (Horspool algorithm) 1990 Sunday Quick Search algorithm 1992 Shift Or algorithm 1992 Turbo-BM algorithm (繰り返し対策.DNAのように文字種の集団が小さい場合に有効) んで、注目のポイントはここ。 1980 BMH
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
