Succinct なトライの実験 その 7（LoudsTrie の修正）

sumire-tries の LoudsTrie に問題を見つけたため，修正しました．

# 修正回数が多すぎますね，本当に…．申し訳ありません．

修正版は既にアップロードしてあります．

• http://code.google.com/p/sumire-tries/

今回の修正したのは，LoudsTrie の find_child() において，ラベルを取得する度に無駄な rank() を呼び出していたという，性能面で致命的な問題です．

以前と同様の設定で実験したところ，以下の結果が得られました．

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（旧）	3.65	25.56	11.17	36.30
LoudsTrie（新）	2.61	17.40	7.44	21.66
（新）/（旧）	71.5%	68.1%	66.6%	59.7%
LoudsPlusTrie	2.48	16.75	7.14	20.66
出現頻度降順	jawiki	enwiki	ja1gms	en1gms
BasicTrie	0.36	2.60	1.04	4.81
SuccinctTrie	0.77	5.52	2.40	13.05
LoudsTrie（旧）	2.14	14.14	5.80	19.24
LoudsTrie（新）	1.92	12.29	5.03	14.03
（新）/（旧）	89.7%	86.9%	86.7%	72.9%
LoudsPlusTrie	1.82	11.77	4.74	13.32

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

ラベル昇順	jawiki	enwiki	ja1gms	en1gms
BasicTrie	1.32	12.17	4.29	20.89
SuccinctTrie	5.61	67.47	21.09	123.48
LoudsTrie（旧）	5.32	48.84	16.71	55.26
LoudsTrie（新）	4.45	41.04	12.91	43.25
（新）/（旧）	83.6%	84.0%	77.3%	78.3%
LoudsPlusTrie	4.31	46.46	13.28	43.61
出現頻度降順	jawiki	enwiki	ja1gms	en1gms
BasicTrie	0.75	6.80	2.42	13.38
SuccinctTrie	2.35	23.07	7.06	40.69
LoudsTrie（旧）	3.88	37.45	11.06	37.58
LoudsTrie（新）	3.80	35.33	10.27	32.61
（新）/（旧）	97.9%	94.3%	92.9%	86.8%
LoudsPlusTrie	3.70	40.52	10.69	35.18

LoudsTrie の検索時間がかなり短縮された結果，ランダム順の検索時間では LoudsPlusTrie を追い抜きました．キーワード検索が目的であれば，LoudsPlusTrie を使う理由は薄いかもしれません．

ただし，実装による改善の余地は LoudsPlusTrie の方が大きいと思います．