おおいしつかさ


旅行とバイクとドライブと料理と宇宙が好き。
Ubie Discoveryのプログラマ。
Share:  このエントリーをはてなブックマークに追加

Double Arrayの勉強中

WEB+DB PRESS Vol.42

アルゴリズム超重要でやったキーワード検索機能ですが、 「WEB+DB PRESS Vol.42」にDoubleArrayのお話が載っていたので、ちょっと勉強しています。ぼくが作ったキーワード検索では、TRIEをハッシュ木で実現しているのですが、DoubleArrayではどうなのだろうかと思った次第。
 ところが、検索のアルゴリズムはすごく簡単なのですが、BASEとCHECKの配列を構築するアルゴリズムがよくわからない。ちょっとググってみても特に見つからない。見つかるのは、あらかじめわかっているキーワードをすべて登録する方法。これならちょっと考えれば実装できる。でも、途中でキーワードを追加したり削除したりする方法がむずかしい。違うキーワードなのに、遷移先が衝突しちゃうことがあるけど、このときどうすればいいのか。まあ、のんびりと勉強していこう。