文字列検索アルゴリズム

日経ソフトウエアのBM法の説明と奥村先生のC言語による最新アルゴリズム辞典の説明が違うことに気づいてしまいました。それどころか、GoogleでBM法を検索した結果のページも、それぞれみんなちょっとずつ違うんです。
どれが本物でどれが亜種だろうがかまわないんだけど、同じアルゴリズムを違う名前で呼ばれてしまうと困ってしまうま。
で、いろいろ検索しているうちに EXACT STRING MATCHING ALGORITHMS ってサイトにたどりつきました。暗号で有名なNISTの Dictionary of Algorithms and Data Structures からたどりついたってこともメモしておきます。NISTの string matching からリンクされてました。
このサイト、有名な文字検索アルゴリズムがCの実装と一緒に載ってます！すげぇ。高い本買わなくても勉強はできるのね。
このサイトによると、奥村先生の実装が Horspool algorithm (昨日の日記でBMHって呼んでたやつ)と呼ばれていました。
んで、昨日の日記で私が実装した IndexOfBMH は Quick Search algorithm っていうそうです。「SUNDAY D.M., 1990, A very fast substring search algorithm, Communications of the ACM . 33(8):132-142.」だそうで、日曜日さんが発表したもの。いい名前だ。
なんだか頭がこんがらがるけど、そういうこと。

ついでに日本語の説明があるよいサイトにもリンク。

JavaによるBMHの実装。奥村先生の実装とだいたい同じものです。

Quick Search algorithmの説明。昨日もリンクしたけど、あのときはこれがBMHだと信じてた。本当はQuick Search。