Simple-9について解説
前回に引き続き転置インデックスの圧縮を実装してみる。今回紹介するのは[2]で提案されているSimple-9というアルゴリズムである。
Simple-9は32bitのwordにできるだけ数字を詰めていくという圧縮アルゴリズムである。例えば2bitの数が16個ならんでいれば32bitで表現できる。しかし、実際は大きい数字も出現するため数字の長さの情報も格納する必要がある。Simple-9では4bitを用いて残りの28bitがどう詰められているかを表す。
28bitの表し方としては
| 上位bit | 符号の個数 | 符号のビット長 |
|---|---|---|
| 0000 | 28 | 1 |
| 0001 | 14 | 2 |
| 0010 | 9 | 3 |
| 0011 | 7 | 4 |
| 0100 | 5 | 5 |
| 0101 | 4 | 7 |
| 0110 | 3 | 9 |
| 0111 | 2 | 14 |
| 1000 | 1 | 28 |
の9通りがあり、これがSimple-9の名前の由来となっている。
例えば ( 3 , 5 , 0 , 0 , 2 , 4 , 0 , 6 , 0 , 12 , 19 , 0 , 11 , 19)という列は最初の9つの数はすべて3ビットで表されるため
0010,011,101,000,000,010,100,000,110,000
と表現され、次の5つの数はいずれも5bitで表現できるため
0100,(000)01100,10011,00000,01011,10011
と表現される。括弧でくくったのは32 - 4 - 5 * 5 = 3で使っていないビットの部分を表している。
追記(08/11)：この例では前から貪欲にエンコードを決定しているが実はこれでは最適にはならない。たとえば
2^13 0が28個
のような29 * 4 byteのデータの場合、前から貪欲にとると
(2^13 0) (0が14個) (0が9個) (0が4個)
となり4 * 4 = 16byte必要だが、実は
(2^13) (0が28個)
とすれば2 * 4 = 8byteで圧縮できる。最適なパターンを見つける方法は動的計画法を用いることにより線形時間で計算できる。しかし、実験したところ最適アルゴリズムは貪欲なものと比べて0.2%ほどしか圧縮率が改善しなかったためDPを用いた場合は入力を一旦最後まで見ないとエンコーディングができないため、貪欲のものの場合が実用的には優れているといえる。
エンコードのコードは次のようになる
// vector<unsigned int> ds : ある単語に対する差分表現の転置リスト // return : 圧縮結果 vector<unsigned int> encode(const vector<unsigned int> & ds){ int bit_len[] = { 1 , 2 , 3 , 4 , 5 , 7 , 9 , 14 , 28 }; int code_num[] = { 28 , 14 , 9 , 7 , 5 , 4 , 3 , 2 , 1 }; vector<unsigned int> output; int i = 0; while(i < ds.size()){ for(unsigned int selector = 0 ; selector < 9 ; selector++){ unsigned int res = 0; int cn = code_num[selector]; if( i + cn - 1 >= ds.size())continue; int bl = bit_len[selector]; int lim = 1 << bl; int j; for(j = 0 ; j < cn; j++){ if(ds[i + j] >= lim){ break; }else{ res = (res << bl) + ds[i + j]; } } if(j == cn){ res |= selector << 28; output.push_back(res); i += cn; break; } } } return output; }
復号のコードは次のようになる
vector<unsigned int> decode(const vector<unsigned int> & enc){ vector<unsigned int> output; for(int i = 0 ; i < enc.size() ; i++){ unsigned int ei = enc[i]; unsigned int selector = ei >> 28; unsigned int low = ei & 0xfffffff; switch(selector){ case 0: //length of each code 1 , # of codes 28 for(int j = 0 ; j < 28; j++){ output.push_back(1 & (low >> (27 - j))); } break; case 1: (中略) break; case 4: //length of each code 5 , # of codes 5 output.push_back((low >> 20) & 0x1f); output.push_back((low >> 15) & 0x1f); output.push_back((low >> 10) & 0x1f); output.push_back((low >> 5) & 0x1f); output.push_back(low & 0x1f); break; case 5: (中略) break; case 8: //length of each code 28 , # of codes 1 output.push_back(low); break; } } return output; }
コードを見るとswitchで分岐した後はbit演算だけで復号ができることが分かる(case 0のところでfor文を用いているがこれに関しては展開して28個書き並べればよい)
Simple-9の圧縮結果を前回のものと比較すると
| アルゴリズム | 無圧縮 | Variable Byte Code | unary符号 | γ符号 | δ符号 | Rice Coding | Simple-9 |
|---|---|---|---|---|---|---|---|
| サイズ | 1537MB | 497MB | 239475MB | 474MB | 407MB | 367MB | 448MB |
| ポインタ辺りのビット数 | 32.4403 | 10.4945 | 5052.43 | 10.0026 | 8.59053 | 7.75678 | 9.4665 |
でVariable Byte Codeと比べて50MBほど圧縮できていることが分かる。またword単位で処理するので処理系によってはVariable Byte Codeより高速である。
参考文献
[1] Jiangong Zhang, Xiaohui Long, Torsten Suel: Performance of Compressed Inverted List Caching in Search Engines , WWW 2008 , url
[2] Vo Ngoc Anh, Alistair Moffat: Inverted Index Compression using Word-Aligned Binary Codes, Information Retrieval, 8(1):151-166, 2005
