Boyer-Moore検索法

その他

ちょっとアカデミックな雰囲気のエントリーです。
日経ソフトウエアの2006/04号でアルゴリズム入門特集が載ってて、文字列検索(文字列じゃなくて何かしらのパターンでもいいわけだけど)としてKMP法とBM法が載っていました。
アルゴリズムって開発者にとっては人気のネタだけど、実際に実装することは少ないよねぇ。でも検索ってのも話題のキーワードだしちょっと気になるわけです。で、読んでみると実装は載ってなくって、サイトに行っても検索の実装はおいてなかったので、がっかり。
記事ではテーブルの実装をどうするかっていう肝心なことに触れてないんです。自明なことだろって雰囲気でさらっと流して終わっているので、何やら怪しい雰囲気を感じ取ってしまうわけです。
そんなわけでテーブルはどうするのよ？ってことで「Boyer-Moore法」や「BM法」でGoogleしてみるといくつか実装が見つかります。んで、どれもこれもテーブルは256個の要素を持ったASCII時代の実装しか出てきませんでした。
ふと気づいて本棚から、奥村先生のアルゴリズム辞典を引っ張り出すと、ネットで見つかるのとだいたい同じような実装が載っていました。自分の持ってる書籍の全文検索機能が欲しいなぁ…。
ところで、2byte文字でやろうとすると65536個のテーブル？って考えると初期化するだけでも大変そう。あらかじめ用意しておくにしても早くなるのかね？って疑問が湧いてきます。このあたりには触れている記事がいくつかあって、やっぱり1byteずつにばらして検索して、最後に見つかったものが本当に正しい文字なのか再検証するって手法が使われてるようです。
やっぱりテーブルのあたりが肝なんですね！