Succinct なトライの実験 その 4

そろそろドキュメントを用意してソースコードを公開しようと思っていたのですが，大切な実験を一つ忘れていたことを思い出しました．それは，子ノードの順番を変更したとき，検索時間がどのくらい変化するのかを調べるものです．

これまでの実験（2009-10-29 - やた＠はてな日記, 2009-10-30 - やた＠はてな日記, 2009-11-03 - やた＠はてな日記）では，BasicTrie および Succinct なトライについて，子ノードの順番をラベル昇順に固定していました．そのため，後半に配置されるラベルの出現頻度が大きいとき，効率が悪くなるという問題がありました．この問題は，兄弟ノードへの移動時に rank() を用いる SuccinctTrie の検索時間に対して，特に大きな影響を与えることが予想されます．

例えば，A で始まるキーが 20 個，B で始まるキーが 10 個，C で始まるキーが 70 個あるとします．そして，各キーを検索する確率が同じ場合，最初に C を調べるようにしておけば，根から次のノードを探すとき，兄弟ノードへと移動する確率が 30% になります．辞書順に並べておいた場合は 80% なので，大きな差が発生します．

そこで，子ノードをラベル昇順に並べた場合と，子ノードを出現頻度降順に並べた場合について，検索時間の比較実験をおこないました．今回の実験では，BasicTrie, SuccinctTrie, LoudsTrie, LoudsPlus を比較しました．なお，Succinct Bit Vector の実装は HybridSBV に統一してあります．

用いたコーパスは以前の実験と同じであり，以下のようになっています．

ID コーパス キー数 平均キー長（bytes）
jawiki 日本語版 Wikipedia タイトル一覧 942,390 20.4
enwiki 英語版 Wikipedia タイトル一覧 6,437,567 18.6
ja1gms 日本語版 Google n-gram コーパスの 1-gram 2,565,427 18.8
en1gms 英語版 Google n-gram コーパスの 1-gram 13,588,391 8.3

次の表は，すべてのキーを辞書順に検索するのに要した時間（秒）を示しています．

ラベル昇順 jawiki enwiki ja1gms en1gms
BasicTrie 0.84 6.36 2.81 10.29
SuccinctTrie 3.49 33.34 12.71 57.14
LoudsTrie 4.00 27.67 12.04 37.87
LoudsPlusTrie 3.01 19.91 8.43 23.54
出現頻度降順 jawiki enwiki ja1gms en1gms
BasicTrie 0.36 2.60 1.04 4.81
SuccinctTrie 0.77 5.52 2.40 13.05
LoudsTrie 2.50 16.34 6.70 20.91
LoudsPlusTrie 2.35 15.00 6.07 16.31

次の表は，すべてのキーをランダム順に検索するのに要した時間（秒）を示しています．

ラベル昇順 jawiki enwiki ja1gms en1gms
BasicTrie 1.32 12.17 4.29 20.89
SuccinctTrie 5.61 67.47 21.09 123.48
LoudsTrie 5.99 51.48 17.54 56.50
LoudsPlusTrie 4.95 49.66 14.78 46.07
出現頻度降順 jawiki enwiki ja1gms en1gms
BasicTrie 0.75 6.80 2.42 13.38
SuccinctTrie 2.35 23.07 7.06 40.69
LoudsTrie 4.41 39.85 12.54 39.56
LoudsPlusTrie 4.21 43.65 12.39 38.18

全体的に，検索時間が大幅に短縮されています．ランダム順に検索した場合の所要時間を見てみると，子ノードを出現頻度降順に並べ替えたことにより，BasicTrie は 56 〜 64%，SuccinctTrie は 33 〜 42%，LoudsTrie は 70 〜 77%，LoudsPlusTrie は 83 〜 88% に短縮されたことが分かります．

SuccinctTrie における短縮効果が高い理由としては，冒頭で述べたように，兄弟ノードへの移動に rank() を用いていることがまず挙げられます．さらに，多分木を二分木に変換してから Level-order に配置するため，（本来の）兄弟ノードがメモリ上で離れたところに配置されるという特徴が影響を大きくしているものと考えられます．

LoudsTrie, LoudsPlusTrie については，子ノードへの移動に使用する select() がボトルネックになるため，他のトライと比べて影響が小さくなっているようです．LoudsTrie における検索時間の短縮幅が LoudsPlus における短縮幅より大きいのは，ラベルの取得に rank() を用いていることが理由です．

※ LoudsTrie については，兄弟ノードへの移動はインクリメントのみで実現しているものの，ラベルの取得に rank() を使っています．

今回の実験では，子ノードの並べ替えによって検索時間を短縮できることに加え，SuccintTrie の検索速度を LoudsTrie, LoudsPlusTrie 以上にできることが分かりました．しかし，出現頻度に偏りがなければ並べ替えても意味がありませんし，（キーの有無を確認する用途などで）移動先となる子ノードが存在しない場合，すべての子ノードを調べることになるので，検索時間の短縮効果は薄くなります．また，兄弟ノード同士が離れて配置されるという特徴があるため，SuccinctTrie を mmap() と組み合わせて用いる場合，メモリ上に主要部分がキャッシュされるまでの検索性能には期待できません．

これまでの実験結果を簡単にまとめてしまうと，「どのトライを選択すべきなのか」は「状況による」ということになります．

追記（2009-11-09）：DFUDS については，子ノードの並べ替えに関する論文があるようです（詳細は未確認）．