Sekkaにトライ木を実装するとしたら ver-1

2012年03月07日

先日の記事「2012-02-25SekkaKVSTRIE* Sekkaにトライ木の実装が必要な理由」の続き。 [Sekka]の曖昧文字列マッチングはかなり手抜きな実装になっている。そこをトライ木で改善できるのではないかという話。 ※ 本記事はKey-Value Store型データベースにトライ木を構築する方法を書いています。ポピュラーなtrieライブラリであるDouble ArrayやLOUDSなどのデータ構造の話では無いので、それを期待されて来られた方はすみません… そのあたりの話は全部次の本に書いてあります。私は買いました。ステマではありませんよ。

問題点

現状の[Sekka]ではローマ字のキーワードが単純な文字列のリストで格納されているだけなので、ユーザが入力したローマ字との編集距離の比較が大量に発生する。例えば、”Kanji” に対する編集距離(Jaro Winkler関数)の呼びだし回数は 113211回 (全文字列サイズデリミタのスペース文字を入れると1.6MByte)となる。また “Ka”という２文字を入力した時と、”Kanji”という５文字を入力した時では同じ回数Jaro Winkler関数が実行される。これはかなりひどい。

Key-Value Stroeの上に実装する理由

通常、トライ木のライブラリはCやJavaなどの言語を使って実装され、整数型の配列やポインタを駆使し(時にはビット演算まで使って)格納データサイズを圧縮することに主眼が起かれていることが多い。しかしここでは、世間の常識に反してプレーンなKey-Value Stroe上に実装してみる。理由は、C言語のtrieライブラリを使うとインストール作業の敷居が上がるのでやりたくないのと、分散ハッシュテーブルを使って曖昧文字列マッチングがスケールアウトする様を見てみたいというのがある。実は、単純に趣味の問題も大きいが…

トライ木

トライ木を使えば、計算しても意味が無い部分ツリーをばっさり枝刈りできると考えた。文字列が短かければそれだけ計算量を減らすことができる。

トライ木の概念

プレフィックス木（Prefix Tree）とも言われるだけあって、検索したい文字列の先頭から1文字づつ比較しながら木を降りていける。幅優先探索も、深さ優先探索もどちら簡単に実装できる。概念図は下記のようなもので、各ノードから子に降りて行くエッジ部分に１文字のアルファベットが付いている。 “A”, “to”, “tea”, “ted”, “ten”, “i”, “in”, “inn” というキー群によるトライ木

上の図はトライ木 - Wikipediaからコピーしてきたもので、これを使って考える。

Key-Value Storeでの実現方法

あるノードの子をたどれるようにするために以下のようなデータ構造を考えることが可能だ。 keyはKey-Value Storeのキー、valueはKey-Value Storeの値とする。キーという用語が二つ出てくるので注意。 Key-Value Storeのキーをkey 、トライ木のキーを「キー」と表記する。なお、扱える文字クラスはアスキーの範囲しか考慮していない。また $ は特別な記号に使っているため $ も使えない。

    *key*      *value*    1   node:$     "i$ t A$"    2   node:i     "n$"    3   node:in    "n$"    4   DATA:i     11    5   DATA:in    5    6   DATA:inn   9    7   node:t     "e o$"    8   DATA:to    7    9   node:te    "a$ d$ n$"   10   DATA:tea   3   11   DATA:ted   4   12   DATA:ten   12   13   DATA:A     15

順番に解説すると1行目の key “node:$” はスーパールートといってツリー全体の根になる。 value側の “i$ t A$” のうち “i$” は $が付いているのでトライのキーとして登録されていることを示す。

keyの “node:” で始まっているものがトライ木のノード、”DATA:”で始まっているものがトライ木に上のキーに対応するデータである。 valueの数字は実際のデータである。そのKey-Value Storeがサポートしたデータならなんでも良い。 13行目は A に対してのデータで数値の15を例として入れてある。(わかりやすいように上の図のノード番号を入れている)

prefix searchの手順

木全体から “in” で始まる単語を探索する場合

1行目の “node:$” のvalueを調べる
1文字目の i がキーワードとして終端している “i$” があるので、iをキーワードとして蓄積する。
iに続くキーワードがまだあるかも知れないので、KVSから”node:i”で引いてノードがあるか調べる。
2行目の “node:i” が見つかるのでvalueを調べる。
2文字目の n がキーワードとして終端している “n$” があるので、inをキーワードとして蓄積する。
inに続くキーワードがまだあるかも知れないので、KVSから”node:in”で引いてノードがあるか調べる。
2行目の “node:in” が見つかるのでvalueを調べる。
3文字目の n がキーワードとして終端している “n$” があるので、innをキーワードとして蓄積する。
innに続くキーワードがまだあるかも知れないので、KVSから”node:inn”で引いてノードがあるか調べる。
ノードが無いので、inn以下のトラバースはしない。
探索結果から、検索文字列 “in”よりも文字列長が短かい “i” を削除したリストをprefixの結果とする。

※ 途中、valueに複数の子ノードが見つかったら、それぞれのエントリを再帰的にトラバースする。

編集距離による絞り込み探索

prefix searchと違う点は文字列が完全一致しているかどうかを調べるかわりに、探索クエリ文字列とトラバース中に見つかったキーワード同士の編集距離が閾値に収まるかで判定する。閾値に収まらないキーワード配下のツリーは探索対象としない。

キーワードの動的な登録

注意する点は、一般的なKVSは複数keyの一貫性のある登録をサポートしていないので、登録中に参照があった場合、おかしな木が見える可能性があること。対策として登録順を工夫する。最初にデータ、次にツリーの葉のほうから根に向かって順に登録していくことで参照時のファントムリードが無いようにできる。 ※ 参考:Tokyo Cabinetは複数エントリの一貫性のある登録(トランザクション)をサポートしている。

キーワードの動的な削除

注意する点は、一般的なKVSは複数keyの一貫性のある削除をサポートしていないので、削除中に参照があった場合、おかしな木が見える可能性があること。対策として削除順を工夫する。最初にツリーの根のほうから葉に向かって順に削除、最後にデータという風に削除していくことで参照時のファントムリードが無いようにできる。 ※ 参考:Tokyo Cabinetは複数エントリの一貫性のある登録(トランザクション)をサポートしている。

というわけで、一度実装してみて問題があれば、訂正記事を書こうと思う。

kiyokaのブログアーカイブ