年越し C++ な年末年始でした

昨年末の投稿から引き続いて，多層トライをライブラリ化していました．現在，ソースコードはほとんど完成していますが，ライブラリの名前はまだ決まっていません．パトリシア（PATRICIA: Practical Algorithm To Retrieve Information Coded In Alphanumeric）のようにネタに走ってみるのもいいかな，なんて思いつつ…．

以下，少し前におこなった実験の結果です．最新版と比べるとサイズに数十バイト程度の誤差がありますけど，ほぼ無視できるので，そのままになっています．

• #tries: 辞書を構成するトライの数
• #nodes: ノード数の合計
• size: 辞書のサイズ
• build: 構築時間（us/key）
• restore: キーの ID から文字列を復元するのに要した時間（us/key）
• lookup: 完全一致検索に要した時間（us/key）
• find: 入力文字列の前方部分と一致するキーの検索に要した時間（us/key）
• predict: 入力文字列で始まるキーの検索に要した時間（us/key）
  • breadth: 幅優先に探索した場合
  • depth: 深さ優先に探索した場合

検索時間については，すべてのキーを入力として検索をおこない，所要時間（std::clock() による計測）をキー数で割った結果を示しています．

参考として ux-trie で構築される辞書のサイズも載せています．日英 Wikipedia のタイトルのように，単語やちょっとしたフレーズをメンバとするキー集合ではサイズが 2-3 割引になりました．今回のライブラリが得意なキー集合であれば，検索は遅くなるものの，もっと小さくできます．いわゆる時間と空間のトレードオフというやつです．

日本語 Wikipedia タイトル（jawiki-20101102-all-titles-in-ns0.gz）

#keys: 1146584
total length: 23809474

For sorted input















































































































































-







































































#tries   #nodes      size   build restore  lookup    find predict predict
                                                          breadth   depth
                  [bytes]    [us]    [us]    [us]    [us]    [us]    [us]















































































































































-







































































     1  1564294   9850325   3.079   1.238   1.334   1.378   1.613   2.198
     2  2087639   7056536   3.410   2.381   2.564   2.555   2.808   5.320
     3  2264302   6522294   3.471   2.739   2.930   2.957   3.201   6.550
     4  2340155   6348600   3.550   2.835   3.026   3.044   3.288   6.838
     5  2380365   6274757   3.558   2.878   3.087   3.087   3.349   7.030
     6  2404298   6241633   3.602   2.887   3.079   3.114   3.340   7.056
     7  2419801   6221894   3.558   2.904   3.114   3.140   3.384   7.134
     8  2430547   6212488   3.602   2.922   3.114   3.131   3.358   7.126
     9  2438328   6206625   3.576   2.922   3.131   3.148   3.393   7.178















































































































































-







































































For randomly ordered input















































































































































-







































































#tries   #nodes      size   build restore  lookup    find predict predict
                                                          breadth   depth
                  [bytes]    [us]    [us]    [us]    [us]    [us]    [us]















































































































































-







































































     1  1564294   9850325   4.204   2.241   2.721   2.800   3.131   3.986
     2  2087639   7056536   4.465   3.698   4.326   4.378   4.675   7.596
     3  2264302   6522294   4.518   4.082   4.745   4.771   5.154   8.887
     4  2340155   6348600   4.614   4.169   4.832   4.849   5.163   9.114
     5  2380365   6274757   4.596   4.300   4.997   5.041   5.338   9.437
     6  2404298   6241633   4.640   4.265   4.928   4.971   5.259   9.376
     7  2419801   6221894   4.605   4.378   5.067   5.120   5.416   9.620
     8  2430547   6212488   4.649   4.300   4.954   4.989   5.294   9.445
     9  2438328   6206625   4.614   4.378   5.085   5.111   5.425   9.629















































































































































-







































































参考：ux-trie 9652162 bytes

英語 Wikipedia タイトル（enwiki-20100622-all-titles-in-ns0.gz）

#keys: 7967237
total length: 152373294

For sorted input















































































































































-







































































#tries   #nodes      size   build restore  lookup    find predict predict
                                                          breadth   depth
                  [bytes]    [us]    [us]    [us]    [us]    [us]    [us]















































































































































-







































































     1 10858494  56785483   4.589   1.246   1.334   1.389   1.615   2.722
     2 13455220  43480109   4.952   2.419   2.562   2.601   2.845   8.234
     3 14130999  41304371   5.080   2.695   2.838   2.892   3.133   9.250
     4 14382789  40635601   5.043   2.707   2.876   2.916   3.143   9.530
     5 14500733  40389216   5.058   2.737   2.907   2.947   3.173   9.655
     6 14565402  40279838   5.059   2.748   2.917   2.961   3.186   9.712
     7 14604900  40232844   5.064   2.750   2.921   2.962   3.188   9.673
     8 14631026  40203351   4.914   2.739   2.912   2.953   3.176   9.693
     9 14649248  40188911   4.916   2.740   2.913   2.957   3.181   9.714















































































































































-







































































For randomly ordered input















































































































































-







































































#tries   #nodes      size   build restore  lookup    find predict predict
                                                          breadth   depth
                  [bytes]    [us]    [us]    [us]    [us]    [us]    [us]















































































































































-







































































     1 10858494  56785483   5.515   3.191   3.743   3.887   4.284   5.850
     2 13455220  43480109   5.779   4.940   5.656   5.786   6.172  12.205
     3 14130999  41304371   5.845   5.234   5.981   6.114   6.492  13.530
     4 14382789  40635601   5.869   5.313   6.070   6.210   6.578  13.874
     5 14500733  40389216   5.885   5.364   6.116   6.263   6.626  14.035
     6 14565402  40279838   5.885   5.396   6.140   6.283   6.653  14.113
     7 14604900  40232844   5.895   5.417   6.148   6.290   6.660  14.154
     8 14631026  40203351   5.893   5.427   6.160   6.290   6.672  14.182
     9 14649248  40188911   5.899   5.421   6.156   6.284   6.666  14.168















































































































































-







































































参考：ux-trie 56525288 bytes

MeCab 辞書（mecab-ipadic-2.7.0-20070801.tar.gz）

アーカイブを展開して，見出し語の切り出しなどはおこなわず，*.csv をそのままキー集合としました．新しいライブラリで大きな効果を得られるキー集合です．

トライの数を増やすことで，検索時間がかなり悪化してしまうものの，辞書のサイズを大幅に削減できます．トライが 1 つの検索時間と 9 つの検索時間を比べると 10 倍くらいになっていますが，それでも 20 マイクロ秒以内におさまっているので，使い道はあると思います．

#keys: 392126
total length: 30775421

For sorted input















































































































































-







































































#tries   #nodes      size   build restore  lookup    find predict predict
                                                          breadth   depth
                  [bytes]    [us]    [us]    [us]    [us]    [us]    [us]















































































































































-







































































     1   568175  30078153   3.545   1.224   1.275   1.275   1.454   1.607
     2  1183728  22534659   6.350   2.805   2.780   2.780   3.009   3.188
     3  1730237  15987969   8.237   5.126   5.202   5.202   5.432   5.661
     4  2050722  13196876   8.926   7.829   8.059   8.084   8.237   8.518
     5  2262289  11821534   9.614  10.124  10.379  10.379  10.558  10.915
     6  2418108  10384699   9.997  11.552  11.909  11.909  12.062  12.419
     7  2528235   8996206  10.252  12.674  13.108  13.083  13.185  13.593
     8  2594671   8402321  10.430  13.567  14.001  14.026  14.179  14.536
     9  2638735   8073085  10.481  14.307  14.766  14.817  14.868  15.327















































































































































-







































































For randomly ordered input















































































































































-







































































#tries   #nodes      size   build restore  lookup    find predict predict
                                                          breadth   depth
                  [bytes]    [us]    [us]    [us]    [us]    [us]    [us]















































































































































-







































































     1   568175  30078153   4.412   1.760   2.015   2.066   2.295   2.474
     2  1183728  22534659   7.294   4.004   4.463   4.437   4.718   4.947
     3  1730237  15987969   9.232   6.962   7.778   7.753   8.008   8.263
     4  2050722  13196876   9.946  10.073  11.144  11.144  11.297  11.654
     5  2262289  11821534  10.634  12.572  13.746  13.771  13.924  14.307
     6  2418108  10384699  11.017  14.128  15.454  15.403  15.582  16.015
     7  2528235   8996206  11.297  15.301  16.704  16.704  16.831  17.265
     8  2594671   8402321  11.476  16.296  17.724  17.775  17.851  18.285
     9  2638735   8073085  11.578  17.112  18.642  18.642  18.744  19.178















































































































































-







































































参考：ux-trie 28085349 bytes