LOUDS++(9): trie - doarサイズ縮小版の比較追加
LOUDS(LOUDS++)とは直接は関係ない。
八回目にLOUDS++に試したこと(+α)をdoarにも適用してみたので、その結果。
試したこと
以下の二つ。
どちらもデータサイズを縮小することを目的とした変更。
- 無分岐ノードの削除
- 八回目にLOUDS++のtrieで試したものと基本的には全く同じ
- 無分岐(= 兄弟がいない)ノードに相当する文字はTAIL配列内に格納される
- キーのID保持方法変更
- doarはキーの終端に対応するノードが、そのキーのIDを保持していた
- TAIL配列内にあるキーの末尾文字列の開始位置は、キーのIDを添字として配列内に格納
- キー数 x 32bit 分の領域を消費
- それを、キーの終端に対応するノードが、直接TAIL配列内の末尾文字列の開始位置を持つように変更
- doarはキーの終端に対応するノードが、そのキーのIDを保持していた
doarの実装はLOUDS++とは違い、どこかでソースコードの説明をしていたりはしないので、今回の修正もソースコードの掲載は省く。
※ 作成物は何らかの形で公開する予定だが、その方法は未定。まとめている余裕がないので、ソースコードの公開は取り合えず中止(2010/07/12)
結果
データサイズ | 検索所要時間(秒) | |
louds-trie (五回目) | 74MB | 32.1372s |
louds-trie-tail (六回目) | 52MB | 17.0782s |
louds-trie-less-node | 52MB | 13.4044s |
louds-trie-less-node-opt | 52MB | 11.6995s |
doar | 94MB | 3.19229s |
doar2 | 61MB | 4.54477s |
tx | 67MB | 51.556s |
darts | 416MB | 3.35106s |
もともとのdoarやdartsよりは遅いが*2、LOUDS版に比べれば、だいぶ高速。
これだとtrieの実装としてLOUDSを選択する意義はあまりないような気がする。
まあ実際に使う際にどんな実装が良いかは、入力キーセットやtrieに対してどのような操作を求めるか*3で変わってくるので、結局のところはケースバイケースだと思うけど。