Succinct なトライの実験 その 6
先日の修正（http://d.hatena.ne.jp/s-yata/20100117）に続いて，sumire-tries の select 関数を効率化しました．今回の変更点は，PopCount 関数の計算結果を有効利用するようにしたことです．
※ このエントリにおいて，PopCount 関数とは，整数を引数として受け取り，その整数をビット列と考えて，1 になっているビットの数を返す関数のことです．
よくある実装として，以下のようなものがあります．
※ UInt32 は 32 ビット符号なし整数のことを表しています．定数に U を付けるべきかとも思いましたが，分かりにくくなるので省略しました．
UInt32 PopCount(UInt32 unit)
{
unit = ((unit & 0xAAAAAAAA) >> 1) + (unit & 0x55555555);
unit = ((unit & 0xCCCCCCCC) >> 2) + (unit & 0x33333333);
unit = ((unit >> 4) + unit) & 0x0F0F0F0F;
unit += unit >> 8;
unit += unit >> 16;
return unit & 0x3F; // ここがポイントになります．
}
最初に述べたように，PopCount 関数の主要な用途は，引数に含まれる 1 の数を求めることなので，これで何の問題もありません．でも，少しもったいないことをしています．
何がもったいないかというと，PopCount 関数の最後で切り捨てている上位 24 ビットのことです．この部分，実は，引数の上位 8, 16, 24 ビットに含まれる 1 の数が保存されています．そして，これらの情報を使うことによって，select 関数を少し効率化できます．
※ unit を 1 バイトずつに分割してみると，上位のバイトから順に，引数の上位 8, 16, 24, 32 ビットに含まれる 1 の数が保存されていることが分かります．
今回は，下位 8, 16, 24 ビットに含まれる 1 の数が欲しかったので，以下のように変更しました．
UInt32 PopCount(UInt32 unit)
{
unit = ((unit & 0xAAAAAAAA) >> 1) + (unit & 0x55555555);
unit = ((unit & 0xCCCCCCCC) >> 2) + (unit & 0x33333333);
unit = ((unit >> 4) + unit) & 0x0F0F0F0F;
unit += unit << 8; // シフトを逆にしました．
unit += unit << 16;
return unit; // 上位 8 ビット以外もまとめて返します．
}
基本的には，PopCount(x) >> 24 として，上位 8 ビットだけを取り出すことになりますが，必要に応じて，他の情報も引き出すことが可能です．
※ 同じ方法を前にもどこかで使ったはずなのですが，忘れていました．
sumire-tries の修正版は既にアップロードしてあります．
以前と同じように実験した結果は以下のようになりました．
| ID | コーパス | キー数 | 平均キー長（bytes） |
|---|---|---|---|
| jawiki | 日本語版 Wikipedia タイトル一覧 | 942,390 | 20.4 |
| enwiki | 英語版 Wikipedia タイトル一覧 | 6,437,567 | 18.6 |
| ja1gms | 日本語版 Google n-gram コーパスの 1-gram | 2,565,427 | 18.8 |
| en1gms | 英語版 Google n-gram コーパスの 1-gram | 13,588,391 | 8.3 |
次の表は，すべてのキーを辞書順に検索するのに要した時間（秒）を示しています．
| ラベル昇順 | jawiki | enwiki | ja1gms | en1gms |
|---|---|---|---|---|
| BasicTrie | 0.84 | 6.36 | 2.81 | 10.29 |
| SuccinctTrie | 3.49 | 33.34 | 12.71 | 57.14 |
| LoudsTrie（旧） | 4.00 | 27.67 | 12.04 | 37.87 |
| LoudsTrie（新） | 3.65 | 25.56 | 11.17 | 36.30 |
| （新）/（旧） | 91.3% | 92.4% | 92.8% | 95.9% |
| LoudsPlusTrie（旧） | 2.77 | 18.56 | 7.84 | 22.16 |
| LoudsPlusTrie（新） | 2.48 | 16.75 | 7.14 | 20.66 |
| （新）/（旧） | 89.5% | 90.2% | 91.1% | 93.2% |
| 出現頻度降順 | jawiki | enwiki | ja1gms | en1gms |
| BasicTrie | 0.36 | 2.60 | 1.04 | 4.81 |
| SuccinctTrie | 0.77 | 5.52 | 2.40 | 13.05 |
| LoudsTrie（旧） | 2.50 | 16.34 | 6.70 | 20.91 |
| LoudsTrie（新） | 2.14 | 14.14 | 5.80 | 19.24 |
| （新）/（旧） | 85.6% | 86.5% | 86.6% | 92.0% |
| LoudsPlusTrie（旧） | 2.13 | 13.65 | 5.48 | 14.89 |
| LoudsPlusTrie（新） | 1.82 | 11.77 | 4.74 | 13.32 |
| （新）/（旧） | 85.4% | 86.2% | 86.5% | 89.5% |
次の表は，すべてのキーをランダム順に検索するのに要した時間（秒）を示しています．
| ラベル昇順 | jawiki | enwiki | ja1gms | en1gms |
|---|---|---|---|---|
| BasicTrie | 1.32 | 12.17 | 4.29 | 20.89 |
| SuccinctTrie | 5.61 | 67.47 | 21.09 | 123.48 |
| LoudsTrie（旧） | 5.99 | 51.48 | 17.54 | 56.50 |
| LoudsTrie（新） | 5.32 | 48.84 | 16.71 | 55.26 |
| （新）/（旧） | 88.8% | 94.9% | 95.3% | 97.8% |
| LoudsPlusTrie（旧） | 4.59 | 47.55 | 13.71 | 44.55 |
| LoudsPlusTrie（新） | 4.31 | 46.46 | 13.28 | 43.61 |
| （新）/（旧） | 93.9% | 97.7% | 96.9% | 97.9% |
| 出現頻度降順 | jawiki | enwiki | ja1gms | en1gms |
| BasicTrie | 0.75 | 6.80 | 2.42 | 13.38 |
| SuccinctTrie | 2.35 | 23.07 | 7.06 | 40.69 |
| LoudsTrie（旧） | 4.41 | 39.85 | 12.54 | 39.56 |
| LoudsTrie（新） | 3.88 | 37.45 | 11.06 | 37.58 |
| （新）/（旧） | 88.0% | 94.0% | 88.2% | 95.0% |
| LoudsPlusTrie（旧） | 3.89 | 41.75 | 11.10 | 36.61 |
| LoudsPlusTrie（新） | 3.70 | 40.52 | 10.69 | 35.18 |
| （新）/（旧） | 95.1% | 97.1% | 96.3% | 96.1% |
先日の実験結果と比べると，検索時間が 2 〜 15% 短縮されています．前回と同様に，select の効率化は，日本語コーパスに対して高い効果を見せています．
他に注目すべき点は，ランダム順の検索において，LoudsTrie と LoudsPlusTrie で短縮率の差が大きいことです．原因としては，LoudsPlusTrie において，ビット列 2 本へのアクセスがボトルネックになっている可能性が考えられます．未検証ですが，実装次第（ビット列の統合）で LoudsPlusTrie は高速化できるかもしれません．
