Darts-clone 0.32g beta 公開

随分と放置したままになっていましたが，「ヘッダを #include するだけでは使えない」，「traverse() を繰り返し呼び出したとき余計に時間がかかる」という難点（2009-11-12 - やた＠はてな日記）を解決した（つもりの）バージョンをついに公開いたしました．

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

Darts-clone 0.32g beta のアーカイブでは，ディレクトリ include の中に darts.h があります．dawgdic から独立させたので，コピーして #include するだけで使えるはずです．

注意：インストール（make install）すると，darts.h, mkdarts, darts を上書きしてしまいます．

# 最近は，darts-clone.h を darts.h に変更することすら面倒に感じるようになりまして…．

mkdarts と darts にはオプションを指定できるようにしました．キーと同時に値を指定できるため，少し便利かもしれません．試してみたい方は，キーの後にタブと値を記述したファイルを作成し，mkdarts に対して -t オプションとともに渡してください．

Usage: mkdarts [Options...] [Lexicon] [Dictionary]

  -h  display this help
  -s  sort lexicon before insertion
  -t  use tab separated values

Usage: darts [Options...] [Dictionary] [Lexicon]

  -h  display this help
  -t  drop tab separated values

後，darts-benchmark というコマンドを追加してみました．名前の示すとおり，簡単な性能テストをおこないます．いつものコーパスで試したところ，以下のような結果になりました．

■ Japanese Wikipedia titles

without -t（各キーに固有の値を割り当てた場合）



















































































































































+









































































     size    build  exactMatchSearch  commonPrefixSearch          traverse
                     sorted   random    sorted    random   sorted   random



















































































































































+









































































  40004kb   5974ns  103.2ns  520.0ns   137.9ns   541.2ns  148.6ns  573.0ns



















































































































































+









































































with -t（すべてのキーに 0 を値として割り当てた場合）



















































































































































+









































































     size    build  exactMatchSearch  commonPrefixSearch          traverse
                     sorted   random    sorted    random   sorted   random



















































































































































+









































































  14981kb   2451ns  114.6ns  495.2ns   151.6ns   516.4ns  160.7ns  551.8ns



















































































































































+










































































■ 1-grams from Japanese Google n-gram corpus

without -t（各キーに固有の値を割り当てた場合）



















































































































































+









































































     size    build  exactMatchSearch  commonPrefixSearch          traverse
                     sorted   random    sorted    random   sorted   random



















































































































































+









































































  76778kb   4756ns   92.8ns  588.6ns   124.7ns   615.9ns  133.8ns  631.5ns



















































































































































+









































































with -t（すべてのキーに 0 を値として割り当てた場合）



















































































































































+









































































     size    build  exactMatchSearch  commonPrefixSearch          traverse
                     sorted   random    sorted    random   sorted   random



















































































































































+









































































  25578kb   1789ns   99.4ns  561.3ns   132.5ns   576.9ns  139.0ns  604.2ns



















































































































































+










































































■ English Wikipedia titles

without -t（各キーに固有の値を割り当てた場合）



















































































































































+









































































     size    build  exactMatchSearch  commonPrefixSearch          traverse
                     sorted   random    sorted    random   sorted   random



















































































































































+









































































 240634kb   6721ns   95.5ns  689.7ns   132.0ns   720.8ns  149.1ns  756.5ns



















































































































































+









































































with -t（すべてのキーに 0 を値として割り当てた場合）



















































































































































+









































































     size    build  exactMatchSearch  commonPrefixSearch          traverse
                     sorted   random    sorted    random   sorted   random



















































































































































+









































































  88129kb   2684ns  109.5ns  734.7ns   147.6ns   768.9ns  163.1ns  821.7ns



















































































































































+










































































■ 1-grams from English Google n-gram corpus

without -t（各キーに固有の値を割り当てた場合）



















































































































































+









































































     size    build  exactMatchSearch  commonPrefixSearch          traverse
                     sorted   random    sorted    random   sorted   random



















































































































































+









































































 193324kb   2004ns   43.8ns  449.6ns    65.5ns   512.9ns   72.5ns  535.8ns



















































































































































+









































































with -t（すべてのキーに 0 を値として割り当てた場合）



















































































































































+









































































     size    build  exactMatchSearch  commonPrefixSearch          traverse
                     sorted   random    sorted    random   sorted   random



















































































































































+









































































  65628kb    879ns   46.7ns  447.4ns    69.2ns   498.2ns   77.3ns  518.8ns



















































































































































+

Succinct なトライと比べると，辞書のサイズほど，ランダム順の検索時間に差がないような…．でも，辞書順の検索時間を比べてみると，それっぽい差が確認できます．入力データの偏りが大きくなるとキャッシュミスが減るので差が大きくなるということでしょう．

辞書順に検索するような用途がないのと同様に，ランダム順に検索するような用途もありませんから，中間くらいの差になると考えればよいのかもしれません．…と思ったまではよいものの，辞書順とランダム順で 5 〜 10 倍も差があるので，ほとんど参考にならないことにすぐさま気づかされました．