C++ DAWG Dictionary Library を公開

darts-clone 0.32f の実装が落ち着いてきたので，Darts とは異なるインタフェースを与えて，別のライブラリとして公開しました．従来通り，C++ のヘッダライブラリとなっています．

• dawgdic - Google Code
  • http://code.google.com/p/dawgdic/

まだドキュメントは整備されていませんが，サンプルコード dawgdic.cc, make-dawgdic.cc とヘッダを見るだけでも，大体の使い方は分かると思います．

• darts-clone との違い
  • 辞書の構築方法
    • 昇順もしくは降順にキーを一つずつ DAWG に登録する（すべてのキーをメモリ上に展開する必要がない）
    • DAWG をダブル配列に変換する
    • DAWG を構築するとき，ハッシュ表のサイズを指定できる
  • 検索機能
    • レコードを参照せずにキーの有無を確認できる
    • 検索するときに入力文字列の長さを求めない
  • commonPrefixSearch と traverse
    • 検索専用のクラス Explorer を使用する
    • バイト単位で探索できる
  • 検索速度
    • g++ 4.3.2 によりコンパイルしたときは darts-clone より少し速いかも

追記（2009-04-23）：キーの登録順序を変えると，構築される辞書が変化します．降順に登録した場合は従来（darts-clone）と同様の辞書になり，昇順に登録した場合は配置順序が逆になります．分かりにくい説明ですが，良い表現が思い浮かばなかったのでご容赦ください．語彙辞書については，どちらの順序で登録しても，それほど影響がないと思います．ただし，ラベルの出現順序に偏りがある場合，登録順序により大きな差が発生するかもしれません．

追記（2009-04-24）：DAWG はトライの共通部分木を併合してできるグラフなので，レコードが重複していない場合，ただのトライになります．このとき，辞書のサイズは Darts の半分程度になるはずです．

追記（2009-04-26）：Google Code の Wiki にてドキュメントを作成しました．