kiyoka.2012_02_25 RSSPLAIN

Related pages: !kiyoka.blog.list kiyoka.2012_03_07 kiyoka.2012_03_03 !kiyoka.blog.2012_03 !kiyoka.blog.2012_02
555545555555555555555555555255355555555555555555555
5

[Sekka][KVS][TRIE] Sekkaにトライ木の実装が必要な理由

5

 

5

Sekkaの曖昧文字列マッチングはかなり手抜きな実装になっているので直したい。

5

トライ木EXTを実装すべき時かもと思いはじめてきた。

4
 400px-Trie_example.svg
5

 

5

残念なデータ構造

5

Sekkaの辞書は、Tokyo CabinetやRedisなどKey-Value Storeに格納されるが、次のような残念なデータ構造になっている。

5

例えば、"kanji" というローマ字をキーに曖昧検索をする場合は、先頭2文字 "ka" のキーワードリストを キー "(ka)" で取り出す。

5

そのキーワードリストに対して、"kanji"との編集距離を求め、ある閾値を越えたキーワードだけを抜き出す。

5

 

5
 キー   値
5
 
5
 (aa)   
5
 (ab)   
5
 .
5
 .
5
 (ka)   Ka Kappa Katze ka ka' ka'ba ... kanji kanjiban kanjibann ...
5
 .
5
 (za)   za za'md za'men za'menn za'meq za'ra za'ru za'rurannto  ...
5
 .
5

 

5

残念な点は次の通り

5
先頭2文字がキーになっているので、先頭2文字にタイプミスがあると曖昧検索に失敗する。
5

例えば、"kanji" を "knji" に タイプミスすると救えない。

5

 

5
キーワードリストのサイズが大きい
2

例えば "(ka)" に対するキーワードリストは1.6MByteある。(汗;)

5

 

5
そのため、valueのサイズ制限があるKVSには入れることができない。
3

AmazonのSimpleDBに格納したい。SimpleDBにはvalueが1024バイトまでしか入れられない。

5

 

5
キーワードリストの更新が重い。
5

特にTokyoCabinetを使った時はDISK I/Oが発生してしまう。

5

RedisはDISK I/Oの遅延をしてくれるので、マシではあるが…

5

 

5

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

5

世の中には大量のトライ木のライブラリがある。

5
 参考:
5
 オープンソースのTrieライブラリまとめ - nokunoの日記EXT
5

 

5

自分が欲しいのは、Key Value Store上にツリーを格納でき、幅優先探索できるもの。

5

そして、さらには幅優先探索しながら編集距離で探索範囲を最適化できるもの。

5

 

5

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

5

 

5

自分で実装するなら

5

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

5

 

5

 

5

#(comment)