[Sekka]の曖昧文字列マッチングはかなり手抜きな実装になっているので直したい。 トライ木を実装すべき時かもと思いはじめてきた。

残念なデータ構造

[Sekka]の辞書は、Tokyo CabinetやRedisなどKey-Value Storeに格納されるが、次のような残念なデータ構造になっている。 例えば、”kanji” というローマ字をキーに曖昧検索をする場合は、先頭2文字 “ka” のキーワードリストを キー “(ka)” で取り出す。 そのキーワードリストに対して、”kanji”との編集距離を求め、ある閾値を越えたキーワードだけを抜き出す。

キー 値

(aa)
(ab)
. . (ka) Ka Kappa Katze ka ka’ ka’ba … kanji kanjiban kanjibann … . (za) za za’md za’men za’menn za’meq za’ra za’ru za’rurannto … .

残念な点は次の通り

• 先頭２文字がキーになっているので、先頭２文字にタイプミスがあると曖昧検索に失敗する。 例えば、”kanji” を “knji” に タイプミスすると救えない。

• キーワードリストのサイズが大きい 例えば “(ka)” に対するキーワードリストは1.6MByteある。(汗;)

• そのため、valueのサイズ制限があるKVSには入れることができない。 AmazonのSimpleDBに格納したい。SimpleDBにはvalueが1024バイトまでしか入れられない。

• キーワードリストの更新が重い。 特にTokyoCabinetを使った時はDISK I/Oが発生してしまう。 RedisはDISK I/Oの遅延をしてくれるので、マシではあるが…

トライ木のライブラリを探すが見つからず

世の中には大量のトライ木のライブラリがある。 参考: オープンソースのTrieライブラリまとめ - nokunoの日記

自分が欲しいのは、Key Value Store上にツリーを格納でき、幅優先探索できるもの。 そして、さらには幅優先探索しながら編集距離で探索範囲を最適化できるもの。

ここまでくるとなかなか無い。

自分で実装するなら

次回は、自分で実装するならどういうデータを格納するかを書いてみたい。

#(comment)