Succinct なトライの実験
実験の概要
Succinct な木構造を用いてトライを実装すると，コンパクトな辞書を構築できます．しかし，検索速度の面では，その他のデータ構造に劣るという欠点を持ちます．そこで，いくつかのトライを C++ で実装し，ちょっとした性能テストをしてみました．今回のテストで実装したトライは，以下のとおりです．
- BasicTrie
- 各ノードに「一つ目の子ノードの ID」，「兄弟ノードが存在するか」，「ラベル」を持たせたトライ
- 兄弟ノードが隣接するように配置
- 探索時，子ノードを線形探索して移動先を決定
- 各ノードに「一つ目の子ノードの ID」，「兄弟ノードが存在するか」，「ラベル」を持たせたトライ
- TernaryTrie
- BasicTrie の各ノードに「子ノードの数」を加えたトライ
- 探索時，子ノードを二分探索して移動先を決定
- DaTrie
- ダブル配列によるトライ
- 探索時，ラベルにより移動先を一意に決定
- SuccinctTrie
- 「一つ目の子ノードを左の子」，「兄弟ノードを右の子」とする二分木に変換したトライ
- 「左の子を持つかどうか」，「右の子を持つかどうか」を 0/1 で表した簡潔データ構造
- 子ノードへの移動，兄弟ノードへの移動ともに rank() が必要
- 「一つ目の子ノードを左の子」，「兄弟ノードを右の子」とする二分木に変換したトライ
- LoudsTrie
- Level-Order Unary Degree Sequence (LOUDS) によるトライ
- 子ノードへの移動に rank() と select() が必要，兄弟ノードへの移動は単純にインクリメント
- Level-Order Unary Degree Sequence (LOUDS) によるトライ
- LoudsPlusTrie
- LOUDS の改良版にあたる LOUDS++ によるトライ
- 子ノードへの移動に rank() と select() が必要，兄弟ノードへの移動は単純にインクリメント
- LOUDS の改良版にあたる LOUDS++ によるトライ
※ rank() は O(1), select() は O(log_n) の実装（Tx の実装を簡略化したもの）になっています．select() の実装次第で性能が大きく変化します．
実験結果
実験では，各トライを構築した後，登録したキーを辞書順およびランダム順で検索してみました．用いたコーパスと実験結果は以下のとおりです．
| ID | コーパス | キー数 |
|---|---|---|
| jawiki | 日本語版 Wikipedia タイトル一覧 | 942,390 |
| enwiki | 英語版 Wikipedia タイトル一覧 | 6,437,567 |
次の表は，すべてのキーを辞書順に検索するのに要した時間（秒）を示しています．
| jawiki | enwiki | |
|---|---|---|
| BasicTrie | 1.67 | 12.52 |
| TernaryTrie | 0.51 | 3.53 |
| DaTrie | 0.18 | 1.08 |
| SuccinctTrie | 4.13 | 35.39 |
| LoudsTrie | 7.41 | 55.17 |
| LoudsPlusTrie | 5.52 | 40.31 |
次の表は，すべてのキーをランダム順に検索するのに要した時間（秒）を示しています．
| jawiki | enwiki | |
|---|---|---|
| BasicTrie | 2.11 | 17.32 |
| TernaryTrie | 0.92 | 7.98 |
| DaTrie | 0.66 | 5.86 |
| SuccinctTrie | 6.3 | 72.06 |
| LoudsTrie | 9.36 | 86.22 |
| LoudsPlusTrie | 7.3 | 71.02 |
最後に，トライのサイズ（kB）を示します．
| コーパス ID | jawiki | enwiki |
|---|---|---|
| BasicTrie | 49,917 | 300,576 |
| TernaryTrie | 79,867 | 480,921 |
| DaTrie | 80,007 | 481,323 |
| SuccinctTrie | 19,591 | 119,686 |
| LoudsTrie | 19,591 | 119,686 |
| LoudsPlusTrie | 19,591 | 119,686 |
Succinct なトライの検索時間は，BasicTrie と比べて 2.5 〜 5.0 倍になっています．TernaryTrie や DaTrie と比較した場合，条件によっては 10 倍に達することもあり，検索速度では劣るという当初の予想を示す結果となりました．一方で，Succinct なトライのサイズは，TernaryTrie や DaTrie の 1/4 程度になっています．
※ rank() の実装で手抜きをしたり，任意の符号なし 31-bit 整数をレコードとして持てるように実装したりしているため，Tx と比べて Succinct なトライのサイズがかなり大きくなっています．また，BasicTrie については，各ノードを 5bytes で表現する実装となっており，TernaryTrie と DaTrie については，各ノードを 8bytes で表現する実装となっています．
実験結果に対する感想
Succinct なトライは小さいけど遅いという予想は当たりましたが，予想外のこともいくつかありました．
まず，TernaryTrie と DaTrie の検索時間について，思っていたほどの差が出ていません．ただし，前方一致検索やテキストからのキーワード抽出に利用する場合，トライの根付近を探索する割合が増えるため，差が大きくなるものと予想されます．
次に，Succinct なトライについて，SuccintTrie がもっとも高速になりました．select() の実装がよくないとしても，兄弟ノードへの移動に rank() が必要な SuccinctTrie は遅くなると思っていたため，予想外でした．LoudsTrie と LoudsPlusTrie については，論文の内容，およびに実装したときの印象どおりの結果になっています．
ただし，LoudsTrie, LoudsPlusTrie については，長さが短い順にキーを提示する処理を高速に実現できるという特長があります．また，単純なインクリメントで兄弟ノードへの移動を実現できるため，トライの根付近を探索する場合や，分岐の多いトライを表現する場合には有利になると考えられます．
おそらく，select() の実装を高速なものに置き換えてやれば，LoudsTrie, LoudsPlusTrie の方が SuccinctTrie よりも高性能になるでしょう．
※ 実験に用いたソースコードは近いうちに公開する予定です．
追記
追記（2009-10-29）：辞書順とランダム順の検索時間を示す表が逆になっていたのを修正しました．
追記（2009-11-5）：実験結果の続き（2009-10-30 - やた＠はてな日記, 2009-11-03 - やた＠はてな日記, 2009-11-05 - やた＠はてな日記）があります．
追記（2009-11-7）：ソースコードは，Google Code（http://code.google.com/p/sumire-tries/）にアップロードしました．
追記（2010-1-17）：実験結果の続き（2010-01-17 - やた＠はてな日記）があります．
