Succinct なトライの実験その 5 - やた＠はてな日記

実験に用いた LoudsPlusTrie（LOUDS++）のソースコードにミスを発見しました．子ノードへの移動に用いる関数 child() において rank() を無駄に呼び出すという誤りにより，以前の実験結果（2009-10-29 - やた＠はてな日記, 2009-10-30 - やた＠はてな日記, 2009-11-03 - やた＠はてな日記）では，検索時間が少し長くなっていました．

sumire-tries の修正版を既にアップロードしてあります．

そして，修正後の実験結果を以下に示します．

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

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.36	2.81	10.29
SuccinctTrie	3.49	33.34	12.71	57.14
LoudsTrie	4.00	27.67	12.04	37.87
LoudsPlusTrie（旧）	3.01	19.91	8.43	23.54
LoudsPlusTrie（新）	2.77	18.56	7.84	22.16
（新）/（旧）	92.0%	93.2%	93.0%	94.1%
出現頻度降順	jawiki	enwiki	ja1gms	en1gms
BasicTrie	0.36	2.60	1.04	4.81
SuccinctTrie	0.77	5.52	2.40	13.05
LoudsTrie	2.50	16.34	6.70	20.91
LoudsPlusTrie（旧）	2.35	15.00	6.07	16.31
LoudsPlusTrie（新）	2.13	13.65	5.48	14.89
（新）/（旧）	90.6%	91.0%	90.3%	91.3%

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

ラベル昇順	jawiki	enwiki	ja1gms	en1gms
BasicTrie	1.32	12.17	4.29	20.89
SuccinctTrie	5.61	67.47	21.09	123.48
LoudsTrie	5.99	51.48	17.54	56.50
LoudsPlusTrie（旧）	4.95	49.66	14.78	46.07
LoudsPlusTrie（新）	4.59	47.55	13.71	44.55
（新）/（旧）	92.7%	95.8%	92.8%	96.7%
出現頻度降順	jawiki	enwiki	ja1gms	en1gms
BasicTrie	0.75	6.80	2.42	13.38
SuccinctTrie	2.35	23.07	7.06	40.69
LoudsTrie	4.41	39.85	12.54	39.56
LoudsPlusTrie（旧）	4.21	43.65	12.39	38.18
LoudsPlusTrie（新）	3.89	41.75	11.10	36.61
（新）/（旧）	92.4%	95.6%	89.6%	95.9%

以前の実験結果と比べると，LoudsPlusTrie の検索時間が 4 〜 10% 程度短縮されています．また，日本語コーパスと英語コーパスで比べてみると，日本語コーパスを対象としているときに，より検索時間を短縮できています．

日本語コーパスに対する検索時間の短縮効果が高い理由としては，平均的にキーが長く，キーの総数が少ないという特徴により，child() を呼び出す割合が高くなったからと考えられます．

追記（2009-01-09）：考察において，「キーの総数が多いという特徴」となっていた部分を「キーの総数が少ないという特徴」に修正しました．