Succinct なトライの実験 その 3

先週の実験結果（2009-10-29 - やた＠はてな日記 と 2009-10-30 - やた＠はてな日記）では，select() の遅い実装を用いていたため，SuccinctTrie の方が LoudsTrie, LoudsPlusTrie より高速に検索できていました．一方，今回の実験結果では，Succinct Bit Vector の実装を変更したことにより，LoudsPlusTrie がもっとも優秀な検索速度を実現できています．

今回の実験でテストした Succinct Bit Vector (SBV) の実装は，以下のとおりです．

  • BasicSBV
    • rank(32 * n) を「rank(256 * m)」と「rank(256 * m + 32 * k) - rank(256 * m)」の組み合わせとして保存したもの
      • rank() については，保存されている rank() と pop_count() を利用
      • select() については，保存されている rank() を用いて二分探索
    • 元のビット列が n bits のとき，1.375n bits
  • SimplifiedSBV（以前の実験で使っていたもの）
    • rank(32 * n) を単純に 32-bit 整数として保存したもの
      • rank() については，保存されている rank() と pop_count() を利用
      • select() については，保存されている rank() を用いて二分探索
    • 元のビット列が n bits のとき，2n bits
  • HybridSBV
    • BasicSBV に加えて，select_1(256 * n) と select_0(256 * n) を保存したもの
      • rank() については，BasicSBV と同じ
      • select() については，保存されている select() を用いて探索範囲を狭める以外，BasicSBV と同じ
    • 元のビット列が n bits のとき，1.5n bits

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

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.59 2.90 10.69
TernaryTrie 0.36 2.38 1.05 3.12
DaTrie 0.14 0.88 0.35 0.91
SuccinctTrie 3.49 33.16 12.90 57.30
LoudsTrie 5.61 41.02 16.33 46.15
LoudsPlusTrie 4.56 32.88 12.69 31.28
SuccinctTrie 3.17 28.99 12.41 51.75
LoudsTrie 6.14 43.95 17.05 46.67
LoudsPlusTrie 5.01 35.40 13.42 32.60
SuccinctTrie 3.50 33.27 12.86 57.29
LoudsTrie 4.04 27.79 12.08 38.13
LoudsPlusTrie 2.96 19.78 8.32 23.52

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

jawiki enwiki ja1gms en1gms
BasicTrie 1.37 11.96 4.37 19.94
TernaryTrie 0.80 7.14 2.37 11.71
DaTrie 0.65 5.78 1.95 8.21
SuccinctTrie 5.36 67.70 20.22 121.94
LoudsTrie 7.43 66.85 21.61 65.70
LoudsPlusTrie 6.31 59.07 18.18 53.00
SuccinctTrie 5.21 60.53 19.58 112.66
LoudsTrie 8.19 75.32 23.81 70.99
LoudsPlusTrie 6.86 65.55 19.14 57.20
SuccinctTrie 5.39 66.84 20.03 121.82
LoudsTrie 5.82 51.49 17.37 56.61
LoudsPlusTrie 4.82 49.13 14.14 45.58

最後に，トライのサイズ（kB）を示します．

jawiki enwiki ja1gms en1gms
BasicTrie 49,917 300,576 95,424 241,556
TernaryTrie 79,867 480,921 152,679 386,490
DaTrie 80,007 481,266 153,561 386,640
BasicSBV 17,472 107,105 35,299 106,980
SimplifiedSBV 19,591 119,686 39,171 115,119
HybridSBV 17,896 109,621 36,073 108,608

SBV の実装を BasicSBV, HybridSBV に置き換えたことにより，トライのサイズが小さくなり，LoudsTrie, LoudsPlusTrie の検索時関が短縮されています．SimplifiedSBV から BasicSBV, HybridSBV への置き換えによる検索時間の短縮は効果が大きく，HybridSBV を用いた場合，すべてのコーパスについて，LoudsPlusTrie は SuccinctTrie より優れた検索性能を発揮しています．

LoudsTrie, LoudsPlusTrie において，SimplifiedSBV より BasicSBV を用いたときの方が高速に検索できている理由としては，select() 内部の二分探索におけるキャッシュ・ヒット率の向上が有力です．SuccinctTrie については SimplifiedSBV を用いたときの方が高速であることから，SimplifiedSBV の方が rank() を高速に実現できると考えられますし，とくに他の理由も見当たりません．

結論として，今回の実験で用いた Succinct なトライの中では，LoudsPlusTrie がもっとも優秀なようです．トライによる照合がシステム全体のボトルネックにならない状況では，メモリ節約につながるので，利用を検討してみるとよいかもしれません．高速な SBV の実装を用いれば，検索時間をさらに短縮することも可能です．