marisa-trie の高速化と実験結果
Version 0.1.0 と Version 0.1.1 の検索時間を比較するついでに，索引の実装を少し修正したもの（Version 0.x.x）もまとめて比較してみました．Version 0.x.x については，索引のサイズが約 2 倍になったことにより，辞書のサイズが 2-4% 大きくなっています．
- 実装の種類
- Version: 0.1.0
- Version: 0.1.1
- 無駄な rank() の呼び出しを取り除いたもの
- Version: 0.x.x
- rank/select 索引のブロックを小さくしたもの（索引により多くの領域を割り当てたもの）
- キー集合
- 内容：日本語 Wikipedia のタイトル一覧
- キー数：1,146,584
- キー長の合計：23,809,474 bytes
（追記 2011-02-18）検索時間の単位は [us/key] です．後，% 表示しているのは，Version 0.1.0 を 100% とした場合の値です．
キー集合の配列：昇順
------+---------+---------+-------+-------+-------+-------+-------+-------
#tries #nodes size build restore lookup find predict predict
breadth depth
[bytes] [us] [us] [us] [us] [us] [us]
------+---------+---------+-------+-------+-------+-------+-------+-------
Version: 0.1.0
1 1564294 9850414 3.332 1.334 1.395 1.500 1.605 1.692
2 2087639 7056713 3.611 2.433 2.573 2.678 2.791 2.878
3 2264302 6522559 3.759 2.756 2.948 3.061 3.166 3.271
------+---------+---------+-------+-------+-------+-------+-------+-------
Version: 0.1.1
1 1564294 9850414 3.332 0.994 1.151 1.238 1.317 1.430
74.5% 82.5% 82.5% 82.1% 84.5%
2 2087639 7056713 3.611 1.840 1.997 2.119 2.198 2.320
75.6% 77.6% 79.1% 78.8% 80.6%
3 2264302 6522559 3.759 2.102 2.285 2.407 2.486 2.599
76.3% 77.5% 78.6% 78.5% 79.5%
------+---------+---------+-------+-------+-------+-------+-------+-------
Version: 0.x.x
1 1564294 10045986 3.314 0.820 0.959 1.055 1.099 1.212
61.5% 68.7% 70.3% 68.5% 71.6%
2 2087639 7301365 3.585 1.474 1.605 1.718 1.770 1.884
60.6% 62.4% 64.2% 63.4% 65.5%
3 2264302 6783795 3.733 1.692 1.832 1.962 2.006 2.119
61.4% 62.1% 64.1% 63.4% 64.8%
------+---------+---------+-------+-------+-------+-------+-------+-------
キー集合の配列：ランダム順
------+---------+---------+-------+-------+-------+-------+-------+-------
#tries #nodes size build restore lookup find predict predict
breadth depth
[bytes] [us] [us] [us] [us] [us] [us]
------+---------+---------+-------+-------+-------+-------+-------+-------
Version: 0.1.0
1 1564294 9850414 4.492 2.285 2.756 2.939 3.070 3.175
2 2087639 7056713 4.683 3.724 4.265 4.483 4.561 4.692
3 2264302 6522559 4.849 4.117 4.683 4.884 4.989 5.102
------+---------+---------+-------+-------+-------+-------+-------+-------
Version: 0.1.1
1 1564294 9850414 4.500 1.971 2.433 2.608 2.704 2.843
86.3% 88.3% 88.7% 88.1% 89.5%
2 2087639 7056713 4.683 3.122 3.611 3.803 3.899 4.029
83.8% 84.7% 84.8% 85.5% 85.9%
3 2264302 6522559 4.840 3.436 3.933 4.134 4.230 4.352
83.5% 84.0% 84.6% 84.8% 85.3%
------+---------+---------+-------+-------+-------+-------+-------+-------
Version: 0.x.x
1 1564294 10045986 4.500 1.744 2.207 2.390 2.442 2.590
76.3% 80.1% 81.3% 79.5% 81.6%
2 2087639 7301365 4.683 2.704 3.157 3.349 3.401 3.541
72.6% 74.0% 74.7% 74.6% 75.5%
3 2264302 6783795 4.832 2.991 3.445 3.663 3.707 3.837
72.6% 73.6% 75.0% 74.3% 75.2%
------+---------+---------+-------+-------+-------+-------+-------+-------お試しのつもりで比較実験に加えた Version 0.x.x ですが，空間効率と時間効率のバランスを考えると，Version 0.1.1 より有用かもしれません．辞書の互換性が失われてしまうので，もう少し検討してから正式版として採用するかどうかを決めようと思います．
