多層トライの実験結果 - やた＠はてな日記

概要

ux-trie に影響されて，複数のトライを使った辞書の実験をしてみました．具体的には，「トライの数」，「TAIL の有無」，「ノード順序（ラベル順・頻度順）」を切り替えて，辞書のサイズや構築・検索にかかる時間を比較しました．

実験に使ったソースコードは公開するつもりですが，パッケージ化したり，ドキュメントを用意したり…ということを考えると，しばらく先になると思います．

トライの数

トライの数というのは，辞書を構成するトライの数です．通常の辞書であれば，トライの数は 1 になります．ux-trie であれば，トライの数はデフォルトで 2 つになります．

（追記 2010-12-24）トライを複数にすると，TAIL に相当する部分をトライとして持つことになります．トライが 2 つの場合，1 つ目のトライは TAIL を持たせたときのトライと同じになり，2 つ目のトライは TAIL に格納される文字列集合を逆順（"abc" -> "cba"）にして保存したトライになります．検索は，1 つ目のトライを根から探索して，終端から 2 つ目のトライにジャンプし，2 つ目のトライを根に向かって探索するという手順になります．次に，トライを 3 つにすると，1 つ目のトライはそのままで，2 つ目のトライを前半・後半に分割することになります．ただし，3 つ目のトライについては，文字列集合を逆順にせず，そのまま格納します．例えば，"abcdefg" というキーが "abc", "de", "fg" に分割される場合，1 つ目のトライには "abc"，2 つ目のトライには "gf"，3 つ目のトライには "ed" が登録されます．検索においては，1 つ目のトライを根から探索（"abc"）して，終端から 2 つ目のトライにジャンプし，そこから 3 つ目のトライにジャンプして，3 つ目のトライを根に向かって探索（"de"）した後，2 つ目のトライを根に向かって探索（"fg"）するという手順をとります．

トライを増やすとノード数は少なくなり，全体のサイズも小さくなる傾向があります．その代わり，構造が複雑になるので，検索は遅くなってしまいます．ただし，TAIL 無しの辞書からキーをランダム順に検索する場合，トライの数が多い方が速くなるという結果になりました．末尾の照合でキャッシュが効きやすくなったことが原因だろうと思います．

サイズ・時間の両面から見て，トライの数を 3 より大きくすることにはほとんど意味がないようです．ただし，キー集合がより大規模になれば，トライの数を 4 以上にする意味が出てくるかもしれません．

TAIL の有無

TAIL の有無というのは，最終分岐以降のノードを文字列として保存するかどうかです．実際には，最終分岐以降にノードが 1 つしかない場合，トライ・TAIL 間の連結にかかる空間コストの方が大きくなるので，文字列化を取り止めるようになっています（ux-trie と同じ）．

TAIL を用いるとノード数は少なくなり，全体のサイズも小さくなる傾向があります．また，トライを探索するより TAIL と照合する方が簡単なので，トライの数が 1 つの場合，検索時間は大幅に短縮されます．トライの数を増やすと検索時間の短縮効果は薄くなるようです．

ノード順序（ラベル順・頻度順）

ノード順序というのは，トライを構築するときにノードをラベル昇順に整列したか，頻度降順に整列したかを示しています．例えば，"ab", "ac" というキーがあれば，"a" の頻度は 2，"ab" と "ac" の頻度は 1 と考えます．

頻度順にすると，構築時間は長くなるものの，検索時間も短くなります．

結果

日本語・英語 Wikipedia のタイトル一覧を入力として，辞書のサイズ，構築時間に検索時間を調査しました．検索時間については，キーの完全一致検索にかかる時間になっています．また，キーの順序については，キー昇順とランダム順を試しました．

比較対象として ux-trie 0.12 を入れてみました．新しく実装してみたトライもコンセプトは同様なのですが，トライ・TAIL 間のリンク方法，rank/select 用の索引構造などの違いにより，それなりに異なる結果になっています．索引構造が速度重視になっているため，検索時間は大幅に短縮されています．

英語 Wikipedia タイトル一覧

キー数は 7,967,237，サイズは 160,340,531bytes です．

        | without TAIL         | with TAIL
 #tries | #nodes [k] size [kb] | #nodes [k] size [kb]







































































































-



















































      1 |     67,829    89,025 |     18,004    61,392
      2 |     25,674    53,175 |     20,981    52,013
      3 |     23,040    51,146 |     21,481    50,827
ux-trie |                      |               53,277

             | label order  search [s] | freq order   search [s]
 #tries TAIL | build [s] sorted random | build [s] sorted random





























































































































-






























































      1  off |     58.31  21.37  63.35 |     67.78  18.48  57.31
          on |     75.88  15.64  41.43 |     78.44  12.41  37.49
      2  off |    107.93  24.15  53.97 |    111.70  21.18  48.27
          on |    108.84  22.89  52.67 |    110.83  19.53  48.22
      3  off |    111.85  24.12  53.86 |    114.39  20.77  47.85
          on |    111.73  23.63  53.32 |    113.80  20.23  48.75
ux-trie      |    106.05 104.50 144.35 |

日本語 Wikipedia タイトル一覧

キー数は 1,146,584，サイズは 24,956,058bytes です．

        | without TAIL         | with TAIL
 #tries | #nodes [k] size [kb] | #nodes [k] size [kb]







































































































-



















































      1 |     11,164    14,653 |      2,722    10,293
      2 |      4,699     8,827 |      3,381     8,522
      3 |      4,031     8,335 |      3,530     8,236
ux-trie |                      |                8,787

             | label order  search [s] | freq order   search [s]
 #tries TAIL | build [s] sorted random | build [s] sorted random





























































































































-






























































      1  off |      4.98   3.17   7.20 |      6.81   2.86   6.84
          on |      7.23   2.21   4.26 |      7.39   1.78   3.82
      2  off |      9.90   3.51   6.18 |     10.65   3.15   5.82
          on |     10.57   3.41   5.67 |     10.56   2.80   5.37
      3  off |     10.32   3.48   6.10 |     11.50   3.21   5.63
          on |     10.93   3.58   5.93 |     10.99   2.94   6.00
ux-trie      |     11.11  13.80  16.59 |

まとめ

速度重視であれば，トライ 1 つに TAIL を組み合わせるのがよさそうです．一方，サイズ重視であれば，実装は面倒になるものの，トライを 3 つ以上にしてしまうのも有効なようです．ノードの順序については，ラベル順にしておく特別な理由がないのであれば，頻度順にしておいた方がよさそうです．