Darts clone 0.32g beta5 公開

darts-clone

トライと STL コンテナの比較（トライ（ダブル配列，簡潔データ構造）と STL コンテナ - ny23の日記）を見て，Darts clone の構築時間は長すぎると思ったので，各キーに関連付ける値を指定しないときは，DAWG を経由しないでダブル配列を構築するように改良しました．

http://code.google.com/p/darts-clone/

改良により，値を指定しない場合について，構築時間が以下のように短縮されています．単位は ns/key（ナノ秒単位／キー）です．コーパスなどの詳細が必要な方は，性能評価（http://code.google.com/p/darts-clone/wiki/Evaluation）をご覧ください．

corpus* JA1 JA2 JA3 EN1 EN2 EN3 DIG
0.32g beta4* 1,196 5,942 4,728 2,037 6,666 2,001 843
0.32g beta5* 368 1,326 1,181 747 1,058 421 337

改良前と比べると，構築時間は 16 〜 40% 程度になっています．ダブル配列を構築するだけなので，未使用要素のリンクと探索範囲の限定を組み合わせていることもあり，Darts より高速に辞書を構築できるようになりました．

実験結果を公開してくださっている ny23 さんに感謝です．

# ずーっと前のバージョンでは DAWG を経由しないようになっていたはずなのですが，手間がかかるのとコードが汚くなるので止めてしまった記憶があります．