Succinct なトライの実験 その 2

昨日の実験結果（2009-10-29 - やた＠はてな日記）は assert() が有効な状態で計測していたため，assert() を無効にした状態で再計測しました．また，Google n-gram コーパスを用いた結果を追加してあります．

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.88	6.60	2.92	10.72
TernaryTrie	0.36	2.36	1.06	3.16
DaTrie	0.14	0.86	0.34	0.95
SuccinctTrie	3.19	29.42	12.35	51.47
LoudsTrie	5.77	43.1.0	16.81	46.39
LoudsPlusTrie	4.87	35.68	13.48	33.00

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

	jawiki	enwiki	ja1gms	en1gms
BasicTrie	1.34	11.82	4.44	21.53
TernaryTrie	0.80	7.20	2.63	12.87
DaTrie	0.64	5.72	2.18	8.95
SuccinctTrie	5.25	62.27	21.46	124.62
LoudsTrie	7.77	75.56	24.82	73.1
LoudsPlusTrie	6.65	67.09	20.18	58.98

最後に，トライのサイズ（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
SuccinctTrie	19,591	119,686	39,171	115,119
LoudsTrie	19,591	119,686	39,171	115,119
LoudsPlusTrie	19,591	119,686	39,171	115,119

assert() を無効にしたことにより，前回の実験結果と比べて検索時間が短縮されています．Google n-gram コーパスに対する Succinct なトライの検索時間を除けば，前回の実験結果と同様の傾向が確認できます．

Google n-gram コーパスについては，SuccinctTrie と LoudsTrie, LoudsPlusTrie の関係が一部逆転しています．とくに，英語版のコーパスを用いた場合，LoudsPlusTrie は SuccinctTrie より明らかに短時間で検索できています．

英語版 Google n-gram コーパスの特徴は，「キーが短く」，「キーが多い」ことです．そのため，前回の感想において述べた「分岐の多いトライを表現する場合には（LoudsTrie, LoudsPlusTrie の方が）有利になる」という予想が正しかったことを示す実験結果になっています．

※ 深さによって探索範囲を狭めるなどの簡単な工夫で LoudsTrie, LoudsPlusTrie の検索時間を短縮できると思いますが，未確認です．