読者です 読者をやめる 読者になる 読者になる

LOUDS++(9): trie - doarサイズ縮小版の比較追加

algorithm

LOUDS(LOUDS++)とは直接は関係ない。
八回目にLOUDS++に試したこと(+α)をdoarにも適用してみたので、その結果。

試したこと

以下の二つ。
どちらもデータサイズを縮小することを目的とした変更。

  • 無分岐ノードの削除
    • 八回目にLOUDS++のtrieで試したものと基本的には全く同じ
    • 無分岐(= 兄弟がいない)ノードに相当する文字はTAIL配列内に格納される
  • キーのID保持方法変更
    • doarはキーの終端に対応するノードが、そのキーのIDを保持していた
      • TAIL配列内にあるキーの末尾文字列の開始位置は、キーのIDを添字として配列内に格納
      • キー数 x 32bit 分の領域を消費
    • それを、キーの終端に対応するノードが、直接TAIL配列内の末尾文字列の開始位置を持つように変更
      • キーのIDはbit-vectorを使って表現
      • ノード数 x 1.5bit*1 分の領域を消費
      • ノード数は入力キーセットによって変動。経験的には、キー数 x 2 くらいにみておけば、それほどズレがないような気がする。
      • IDをbit-vectorで表現する方法は、trieをセット的に用いる場合(つまり、キーに紐付くIDが不要な場合)は、もともとのdoarの実装よりも検索速度が速くなる(TAIL配列へのアクセスに、末尾文字列の開始位置を格納した配列を経由する必要がなくなるので)

doarの実装はLOUDS++とは違い、どこかでソースコードの説明をしていたりはしないので、今回の修正もソースコードの掲載は省く。
※ 作成物は何らかの形で公開する予定だが、その方法は未定。まとめている余裕がないので、ソースコードの公開は取り合えず中止(2010/07/12)

結果

データサイズ検索所要時間(秒)
louds-trie (五回目)74MB32.1372s
louds-trie-tail (六回目)52MB17.0782s
louds-trie-less-node52MB13.4044s
louds-trie-less-node-opt52MB11.6995s
doar94MB3.19229s
doar261MB4.54477s
tx67MB51.556s
darts416MB3.35106s
doar2が今回の追加分。
もともとのdoarやdartsよりは遅いが*2、LOUDS版に比べれば、だいぶ高速。
これだとtrieの実装としてLOUDSを選択する意義はあまりないような気がする。
まあ実際に使う際にどんな実装が良いかは、入力キーセットやtrieに対してどのような操作を求めるか*3で変わってくるので、結局のところはケースバイケースだと思うけど。

*1:bit-vectorの実装による。1.5bitは四回目の実装からrank操作に不要なフィールドを除外した場合の数値。

*2:ただし、無分岐ノードの削除を行わなければ、これらと同程度の検索速度となる。その場合のデータサイズは76MB。

*3:例えばdoarは親ノードを辿ることが出来ない。また、途中のノードからの検索再開といった操作も、実装が複雑になるので外してある