大規模トライ用のライブラリを開発中

Succinct なトライをサポートする sumire-tries があるにもかかわらず，ここしばらく，大規模なトライ用のライブラリを開発しています．sumire-tries を何度も修正したのは，開発の途中でいろいろと気づいて，それらを反映させていたからです．いわゆるオマケという感じです．

今回の開発目的は，sumire-tries より大規模なトライを扱うことです．そして，新しいライブラリの特徴は，以下のようになっています．

64 ビット環境に最適化
- 32 ビット環境でも使えますが，本来の性能は出ません．
トライのサイズ制限なし
- ノード数の上限は 2^38 = 2700 億です．
一時ファイルの利用
- 主記憶容量を超えるサイズのトライを構築できます．
  - 構築するだけなら主記憶容量を超えても問題ありませんが，メモリ上に展開できないため，検索するときに mmap() を使うことになります．おそらく，遅くて使えたものではないと思います．SSD に載せれば，なんとか使えるかも…？

これらの特徴により，（実用的かどうかはともかく）とても大規模なトライを運用することができます．32GB の主記憶があれば Google n-gram コーパスに含まれるすべての n-gram（30 億件以上）を登録できるほどです．…使い道はないかもしれませんが，とりあえず可能です．

現状での実験結果を貼り付けておきます．

項目
- type
  - std::set
    - std::set です．
  - PodsTrie (PODS: Post-Order Difference Sequence)
    - sumire-tries における BasicTrie の代わりとして，思いつきで実装しました．
  - LobTrie (LOB Level-Order Bitmap)
  - LoudsTrie (LOUDS: Level-Order Unary Degree Sequence)
  - PloudsTrie (PLOUDS, LOUDS++: Partitioned representation of LOUDS)
  - BpTrie (Balanced Parentheses)
  - DfudsTrie (Depth-First Unary Degree Sequence)
- size
  - トライのサイズ（キロバイト単位）
- conversion time
  - ベースになるトライからの変換に要した時間をキー数で割った値（マイクロ秒）
- lookup time
  - 一つのキーを検索するのに要した時間の平均値（マイクロ秒）
    - sort（辞書順）
    - random（ランダム順）

Japanese Wikipedia titles:
ラベル昇順







































































































+



















































                      conversion         lookup time
       type      size       time      sort    random







































































































+



















































   std::set               2.32us    0.83us    2.22us
   PodsTrie   15379kb     1.00us    1.35us    2.01us
    LobTrie   13279kb     0.72us    3.89us    5.73us
  LoudsTrie   13420kb     0.77us    2.45us    4.36us
 PloudsTrie   13407kb     0.80us    2.33us    4.24us
     BpTrie   15672kb     1.29us   14.47us   15.49us
  DfudsTrie   15886kb     1.37us    2.95us    3.81us







































































































+



















































頻度降順







































































































+



















































                      conversion         lookup time
       type      size       time      sort    random







































































































+



















































   std::set               2.32us    0.82us    2.19us
   PodsTrie   15113kb     1.01us    0.75us    1.41us
    LobTrie   13279kb     0.85us    0.89us    2.46us
  LoudsTrie   13420kb     0.89us    1.95us    3.86us
 PloudsTrie   13407kb     0.91us    1.74us    3.57us
     BpTrie   15736kb     1.31us    2.70us    3.81us
  DfudsTrie   15999kb     1.38us    2.28us    3.05us







































































































+



















































English Wikipedia titles:
ラベル昇順







































































































+



















































                      conversion         lookup time
       type      size       time      sort    random







































































































+



















































   std::set               3.47us    0.92us    3.37us
   PodsTrie   92063kb     0.99us    1.40us    2.76us
    LobTrie   78839kb     0.69us    5.38us   10.54us
  LoudsTrie   79677kb     0.71us    2.39us    6.39us
 PloudsTrie   79591kb     0.72us    2.33us    6.81us
     BpTrie   92525kb     1.16us   16.90us   20.57us
  DfudsTrie   94634kb     1.22us    2.90us    4.65us







































































































+



















































頻度降順







































































































+



















































                      conversion         lookup time
       type      size       time      sort    random







































































































+



















































   std::set               3.46us    0.93us    3.38us
   PodsTrie   90630kb     0.99us    0.74us    2.09us
    LobTrie   78839kb     0.78us    0.94us    3.65us
  LoudsTrie   79677kb     0.80us    1.81us    5.72us
 PloudsTrie   79591kb     0.82us    1.67us    6.01us
     BpTrie   92857kb     1.17us    3.08us    5.68us
  DfudsTrie   95272kb     1.23us    2.21us    3.68us







































































































+



















































Japanese 1-grams:
ラベル昇順







































































































+



















































                      conversion         lookup time
       type      size       time      sort    random







































































































+



















































   std::set               2.95us    0.92us    2.80us
   PodsTrie   28656kb     0.80us    1.54us    2.37us
    LobTrie   24263kb     0.53us    5.23us    7.98us
  LoudsTrie   24521kb     0.53us    2.56us    4.69us
 PloudsTrie   24488kb     0.55us    2.49us    4.70us
     BpTrie   28491kb     0.88us   19.19us   20.79us
  DfudsTrie   29059kb     0.94us    3.01us    4.12us







































































































+



















































頻度降順







































































































+



















































                      conversion         lookup time
       type      size       time      sort    random







































































































+



















































   std::set               2.93us    0.92us    2.79us
   PodsTrie   28062kb     0.80us    0.79us    1.66us
    LobTrie   24263kb     0.61us    0.99us    2.77us
  LoudsTrie   24521kb     0.60us    1.84us    3.93us
 PloudsTrie   24488kb     0.62us    1.67us    3.80us
     BpTrie   28628kb     0.88us    3.35us    4.91us
  DfudsTrie   29277kb     0.96us    2.22us    3.24us







































































































+



















































English 1-grams:
ラベル昇順







































































































+



















































                      conversion         lookup time
       type      size       time      sort    random







































































































+



















































   std::set               3.91us    0.91us    3.81us
   PodsTrie   64466kb     0.60us    1.01us    2.09us
    LobTrie   50999kb     0.23us    4.40us    9.03us
  LoudsTrie   51541kb     0.22us    1.37us    2.79us
 PloudsTrie   51374kb     0.23us    1.37us    2.98us
     BpTrie   58818kb     0.37us   12.60us   15.32us
  DfudsTrie   62136kb     0.41us    1.74us    3.10us







































































































+



















































頻度降順







































































































+



















































                      conversion         lookup time
       type      size       time      sort    random







































































































+



















































   std::set               3.90us    0.91us    3.78us
   PodsTrie   63038kb     0.60us    0.56us    1.62us
    LobTrie   50999kb     0.25us    1.06us    3.12us
  LoudsTrie   51541kb     0.23us    0.98us    2.39us
 PloudsTrie   51374kb     0.24us    0.91us    2.46us
     BpTrie   58925kb     0.37us    4.76us    6.91us
  DfudsTrie   62343kb     0.42us    1.28us    2.57us







































































































+

PodsTrie が思いのほか優秀でした．サイズは 20 〜 30% くらい増える程度なので，オススメできそうです．

注意点
- BpTrie と DfudsTrie が大きい上に遅いのは，findclose() の実装が悪いからかもしれません．
- BpTrie が極端に遅いのは，兄弟間の移動で findclose() を使っているからです．

# キー数が 10 億件を超えるようなトライを構築するより，複数のトライに分けて登録する方が妥当だと思います．…という風に考える冷静な自分もいますよ．