Darts と Darts-clone 0.32g を比べるために,辞書の構築時間とサイズ,および検索にかかる時間を計測しました.大雑把にまとめると,辞書のサイズ,検索時間ともに Darts-clone の方が優秀ということになります.
Darts-clone による検索が高速な理由としては,辞書が小さくなることによって,キャッシュの利用効率が向上したことが考えられます.このことは,辞書がキャッシュに収まるかどうかという状況において Darts と Darts-clone の違いが顕著になっていることから確認できます.また,キーをランダム順に検索したときの所要時間からも確認できます.
もう 1 つの理由として考えられるのは,終端ノードの有無をフラグとして各ノードに持たせていることが挙げられます.このフラグは,終端文字による遷移の確認を省略するための工夫であり,特に commonPrefixSearch()
において高い効果を発揮します.
ただし,Darts-clone ではオフセットやラベルの取り出しに論理演算を必要とするため,わずかながらオーバーヘッドが大きくなっています.また, traverse()
を繰り返し呼び出す場合, traverse()
をインライン化できず,検索時間が悪化することがあるようです.
注意:検索時間については,辞書とキャッシュのサイズ,キャッシュとメモリのレイテンシ,検索するキーの偏り,コンパイラによるインライン化など,影響する要素がとても多く,環境によっては大きく変化する可能性があります.
実験では,いくつかのキー集合に対する辞書を Darts と Darts-clone により構築し,サイズと構築時間を調べた後,各キーを辞書順に検索するのに要する時間と,ランダム順に検索するのに要する時間を計測しました. traverse()
については,各キーを 1 バイトずつ traverse()
に渡して探索するのに要した時間になっています.
※ 計測には Darts-clone に付属のツール darts-benchmark を使用しました.
実験環境の OS は 64-bit 版 Ubuntu 9.04 で,コンパイラは gcc 4.3.3 です.
PC 型番 | CPU 型番 | CPU 周波数 |
---|---|---|
Dell Precision T3400 | Core 2 Quad Q9550 | 2.83GHz |
実験には,日本語と英語のキー集合に加えて,7 桁郵便番号を使用しました.
ID | 出典 | 内容 | キー数 | サイズ [bytes] |
補足 |
---|---|---|---|---|---|
JA1 | ipadic-2.6.3 | 見出し語 | 159,442 | 2,892,008 | 漢字かな混じり |
JA2 | 日本語版 Wikipedia | タイトル | 865,489 | 18,439,874 | タイトル一覧 |
JA3 | 日本語版 Google N-gram | 形態素 | 2,565,427 | 50,784,220 | unigram のみ |
EN1 | !WordNet-3.0 | 英語 | 147,306 | 1,839,597 | 英単語 |
EN2 | 英語版 Wikipedia | タイトル | 5,716,820 | 111,542,495 | タイトル一覧 |
EN3 | 英語版 Google N-gram | 単語 | 13,588,391 | 125,937,836 | unigram のみ |
DIG | 郵便番号辞書 | 7 桁郵便番号 | 118,559 | 948,472 | 2008 年 6 月 30 日更新版 |
各コーパスの詳細については,以下の URL で確認することができます.
- JA1: https://ja.osdn.net/projects/ipadic/
- JA2: https://dumps.wikimedia.org/jawiki/
- JA3: https://googlejapan.blogspot.com/2007/11/n-gram.html
- EN1: https://wordnet.princeton.edu/
- EN2: https://dumps.wikimedia.org/enwiki/
- EN3: https://googleresearch.blogspot.com/2006/08/all-our-n-gram-are-belong-to-you.html
- DIG: https://www.post.japanpost.jp/zipcode/download.html
実験の結果は,以下のようになりました.
- 辞書のサイズ:キロバイト単位
- 構築時間:ナノ秒単位
- 辞書の構築に要した時間をキー数で割った値を示しています.
- 検索時間:ナノ秒単位
- キーを 1 つ検索するのに要した時間の平均値を示しています.
no values は,Darts-clone において,すべてのキーに 0 を関連付けたときの実験結果を示しています.no values 以外は,関連付ける値を指定しなかったときの結果を示しています.
- 辞書サイズ
[KB]
と構築時間[ns/key]
corpus | version | size | build() |
---|---|---|---|
JA1 | Darts | 7,023 | 828 |
Darts-clone | 3,336 | 368 | |
no values | 1,272 | 690 | |
JA2 | Darts | 84,911 | 2,950 |
Darts-clone | 40,004 | 1,326 | |
no values | 14,981 | 2,441 | |
JA3 | Darts | 162,689 | 2,035 |
Darts-clone | 76,778 | 1,181 | |
no values | 25,578 | 1,797 | |
EN1 | Darts | 7,526 | 1,426 |
Darts-clone | 3,527 | 747 | |
no values | 1,293 | 950 | |
EN2 | Darts | 513,873 | 2,518 |
Darts-clone | 240,634 | 1,058 | |
no values | 88,129 | 2,701 | |
EN3 | Darts | 406,358 | 927 |
Darts-clone | 193,324 | 421 | |
no values | 65,628 | 899 | |
DIG | Darts | 2,153 | 337 |
Darts-clone | 1,067 | 337 | |
no values | 106 | 253 |
構築時間については,Darts-clone の方が Darts より短くなっています.ただし,関連付ける値として各キーにユニークな値を指定した場合,Darts-clone の構築時間は,以下のように遅くなります.
corpus | JA1 | JA2 | JA3 | EN1 | EN2 | EN3 | DIG |
---|---|---|---|---|---|---|---|
build() [ns/key] |
1,196 | 5,942 | 4,728 | 2,037 | 6,666 | 2,001 | 843 |
値の指定によって構築時間が大きく変化する理由は,Darts-clone が辞書のデータ構造として Directed Acyclic Word Graph (DAWG) を採用するからです.DAWG は値の重複率が高いトライを圧縮するのに適したデータ構造ですが,DAWG を構築してからダブル配列に変換する必要があります.特に,値に重複がない場合,トライと DAWG は同じになるので,構築の手間が増えるだけになってしまいます.そのため,現在の実装(0.32g)では,値の指定がない場合,すなわち値が重複しないことが明らかな場合は,DAWG を経由することなくダブル配列を構築するようにしています.結果として,ユニークな値を指定したときの構築時間が最も長くなります.
上述の通り,no values で辞書が小さくなっている理由も DAWG です.DAWG はトライの共通部分木を併合して得られるグラフなので,関連付ける値が同じキーのみを併合することができます.つまり,各キーに値を関連付ける必要がないときや,関連付ける値の種類が少ないときは,Darts-clone を使うことで,辞書のサイズをさらに抑えることができます.
- 検索時間(辞書順)
[ns/key]
corpus | version | exactMatchSearch() | commonPrefixSearch() | traverse() |
---|---|---|---|---|
JA1 | Darts | 48.9 | 64.8 | 45.5 |
Darts-clone | 33.1 | 43.8 | 52.8 | |
no values | 31.1 | 41.8 | 51.1 | |
JA2 | Darts | 98.4 | 135.3 | 119.1 |
Darts-clone | 94.6 | 125.0 | 144.6 | |
no values | 107.2 | 134.0 | 157.7 | |
JA3 | Darts | 88.1 | 131.2 | 109.1 |
Darts-clone | 85.8 | 109.1 | 126.7 | |
no values | 92.8 | 117.9 | 135.1 | |
EN1 | Darts | 70.0 | 99.4 | 90.2 |
Darts-clone | 54.7 | 78.0 | 97.0 | |
no values | 54.3 | 78.0 | 96.6 | |
EN2 | Darts | 90.9 | 128.9 | 124.3 |
Darts-clone | 88.5 | 118.1 | 140.6 | |
no values | 101.0 | 131.3 | 155.3 | |
EN3 | Darts | 51.9 | 72.5 | 63.3 |
Darts-clone | 40.5 | 56.7 | 70.3 | |
no values | 44.2 | 60.3 | 75.1 | |
DIG | Darts | 18.8 | 26.8 | 43.3 |
Darts-clone | 24.2 | 42.6 | 36.2 | |
no values | 24.1 | 36.2 | 35.7 |
- 検索時間(ランダム順)
[ns/key]
corpus | version | exactMatchSearch() | commonPrefixSearch() | traverse() |
---|---|---|---|---|
JA1 | Darts | 170.4 | 223.4 | 209.1 |
Darts-clone | 76.2 | 91.1 | 104.5 | |
no values | 60.5 | 75.4 | 86.0 | |
JA2 | Darts | 620.8 | 822.4 | 774.6 |
Darts-clone | 516.4 | 533.9 | 578.3 | |
no values | 488.1 | 502.3 | 546.5 | |
JA3 | Darts | 693.8 | 845.9 | 810.8 |
Darts-clone | 584.7 | 608.1 | 627.6 | |
no values | 561.3 | 576.9 | 608.1 | |
EN1 | Darts | 228.5 | 307.0 | 285.7 |
Darts-clone | 111.3 | 139.9 | 157.4 | |
no values | 93.0 | 122.4 | 137.1 | |
EN2 | Darts | 796.9 | 977.1 | 967.8 |
Darts-clone | 674.2 | 717.7 | 756.5 | |
no values | 731.6 | 772.0 | 817.1 | |
EN3 | Darts | 545.3 | 646.1 | 635.8 |
Darts-clone | 453.3 | 512.2 | 525.4 | |
no values | 457.7 | 500.4 | 519.6 | |
DIG | Darts | 40.2 | 57.0 | 83.5 |
Darts-clone | 43.9 | 64.9 | 60.7 | |
no values | 37.5 | 48.2 | 49.9 |