検索の歴史一文字進化するのに掛かった年数は、なんと…

文字列の高速検索の歴史を年表にしてみたんだけど、年表にしたらめちゃくちゃおもしろいことに気づいてしまいました！今日のエントリーは必見ですよ！

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 (Horspool algorithm)
1990 Sunday Quick Search algorithm (BMS)

この２つは考え方がほとんど一緒です。違うのは読み飛ばす際に注目する文字がパターン長の「最後の文字」か「最後の次の文字」かってこと。「たった一文字」の差です。(もちろんテーブルに入れる数字も全部+1するって違いもあるけど、一文字違うところを見るんだから当然と言えば当然)
BMH法が注目する文字はパターン長の「最後の文字」で、Sundayは「最後の次の文字」。

この「たった一文字」進化するのに掛かった年数が。なんと。１０年！！スゲーーーー！ありえない〜。一文字ですよ、一文字。

10年間誰もあと一文字に気づかなかったんだねぇ。こうやってみるとSundayすごい。すごすぎる。コロンブスの卵。

コンピュータの歴史において10年は長〜い長〜い時間だよねぇ。ソフトウェアの進歩は実は遅いってことも言われるけど、やっぱり遅いのかもって思っちゃった。

Sundayの発見を見てしまった今となってみれば、Horspoolはいい線まで気づいてたのにもう一歩詰めが甘かったね。BM法がパターンの最後の文字をテーブルに活かさないから、その考えに引きずられてしまったんでしょう。
Sundayの発見の後だから言えることだけど、BM法を忘れてBMH法を眺めれば、最低でもパターンを一文字右にずらすんだからテーブルから引くべき文字は「最後の文字」じゃなくって「最後の次の文字」だろってつっこみたくなりますね。
でもHorspoolの発見があったからこそSundayの発見もあったんだろうなぁ。う〜ん、歴史はおもしろい！

SundayのQuickSearchはEXACT STRING MATCHING ALGORITHMSによると「very fast in practice for short patterns and large alphabets.」だそうで。普通の文字列からインデックスとか使わない検索なら、今はこれで決まりですね。

BMH法とSunday法の違いが知りたくなった方のためのリンク集。

絵付きの説明 http://www.inf.fh-flensburg.de/lang/algorithmen/pattern/sundayen.htm

BMH法 http://www-igm.univ-mlv.fr/~lecroq/string/node18.html
Sunday法 http://www-igm.univ-mlv.fr/~lecroq/string/node19.html

参考 BM法 http://www-igm.univ-mlv.fr/~lecroq/string/node14.html
(BM法は面倒くさいのでこういうのがあるよって参考程度で)

ところで EXACT STRING MATCHING ALGORITHMS は isbn:0954300645 として売ってる本でした。amazonで4,016円。ネットで全部公開したってことみたい。ありがたい！トップページの一番下にPDFへのリンクもあります。アルゴリズムはあまり詳しく書いてないけど、網羅的だったり、Cによる実装があったり、絵で検索過程を示してたりで、すばらしすぎです。