転置インデックスの圧縮

Managing Gigabytes勉強会で転置インデックスの圧縮の話が出たので実際に圧縮を行った場合にどれくらいのサイズになるかを計測してみた。

利用したデータは英語版Wikidiaの全記事で

文書数	2,872,589
単語数	2,735,620
転置インデックスのポインタの数	397,603,176

ぐらいのサイズのデータです。

無圧縮の転置インデックスのフォーマットは

単語ID,文書数,文書1,....文書N, 単語ID,...

で各項目4byteとなっており、1.5Gぐらいのサイズになっています。

これに対して各圧縮アルゴリズムを適用した結果は

アルゴリズム	無圧縮	Variable Byte Code	unary符号	γ符号	δ符号	Rice Coding	pforDelta(仮)
サイズ	1537MB	497MB	239475MB	474MB	407MB	367MB	455MB
ポインタ辺りのビット数	32.4403	10.4945	5052.43	10.0026	8.59053	7.75678	9.60173

ここでRice CodingというのはGolomb符号の特別な場合でMGの表記で言うとbが2のべき乗のときの符号です。あとbのパラメータはb = 2^1 - 2^31までを全通り試してみて一番よかったものを用いてます。ここで使ったbは5bit使って格納しておくと仮定します。
また、pforDeltaについてですが128個に分割する所とかがよく分かっていないのでとりあえず一単語ごとに圧縮しています。

あと注意としてはこのデータの場合は単語の数も文章の数も21bitで表現できるため、特別な圧縮アルゴリズムを用いなくても1008MBまでは縮められます。
表からはRice Codingの圧縮率がかなりいいこととVByte符号を用いても半分ぐらいには圧縮が可能であるということが分かる。

また、Rice Codingでの最適なbとその単語の平均出現頻度をプロットすると

となり、当たり前ではあるが頻度が高いほどbが小さくてすむということがわかる。

参考文献

[1] Jiangong Zhang, Xiaohui Long, Torsten Suel: Performance of Compressed Inverted List Caching in Search Engines , WWW 2008 , url
[2] γ符号、δ符号、ゴロム符号による圧縮効果 - naoyaのはてなダイアリー

[1]の4.1に5個の圧縮アルゴリズムの解説が述べてある、VByte,PForDelta,Riceの他にSimple9とSimple16という符号の解説が述べられています。また[2]には今回解説をサボった符号化手法に関する説明が述べてあります。

追記：Simple-9のアルゴリズム関して解説を書きました。http://d.hatena.ne.jp/tsubosaka/20090810/1249915586

ソースコード

#include <sstream>
#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

inline int lg(int x){
  return 31 - __builtin_clz(x);
}

inline long unary_enc(int i){
  return i;
}

inline long gamma_enc(int i){
  int x = lg(i);
  return unary_enc(x + 1) + x;
}

long delta_enc(int i){
  if(i == 1)return 1;
  long x = lg(i);
  return x + gamma_enc(x);
}

long vbyte_enc(int i){
  long res = 0;
  do{
    i >>= 7;
    res += 8;
  }while(i);
  return res;
}

struct RiceEncoder{
  int logb;
  RiceEncoder(int i) : logb(i){}
  long operator()(const int i) const
  {
    int b = 1 << logb;
    int q = i / b;
    return logb + unary_enc(q + 1);
  }
};

template <class Encoder>
long bit_len(const vector<int> & ds , Encoder enc){
  //d0の値
  long res = 4;
  for(int i = 1 ; i < ds.size() ; i++){
    int diff = ds[i] - ds[i - 1];
    res += enc(diff);
  }
  return res;
}

long pforDeltaLen(const vector<int> & ds , int b){
  //d0の値
  long res = 4;
  //例外の起こった場所へのポインタ
  res += 4;
  int exceptionNum = 0;
  int prev = -1;
  int powb = 1 << b;
  for(int i = 1 ; i < ds.size() ; i++){
    int diff = ds[i] - ds[i - 1];
    res += b;
    if(diff >= powb){
      exceptionNum++;
      prev = i;
    }else if(prev >= 0 && (i - prev == powb)){
      //ダミー例外
      exceptionNum++;
      prev = i;
    }
  }
  res += exceptionNum * 32;
  return res;
}

void compress(const char * inputFileName){
  ifstream fin(inputFileName , ios::binary);
  long null = 0;
  long vbyte = 0;
  long unary = 0;
  long gamma = 0;
  long delta = 0;
  long rice = 0;
  long pdelta = 0;
  long totalPointer = 0;
  while(!fin.eof()){
    int tid , size;
    fin.read((char*)&tid , sizeof(int));
    fin.read((char*)&size , sizeof(int));
    vector<int> ds;
    int pre = -1;
    int firstd = -1;
    for(int i = 0 ; i < size ; i++){
      int did;
      fin.read((char*)&did, sizeof(int));
      ds.push_back(did);
    }
    null += 2 * 32;
    null += ds.size() * 32;
    vbyte += 2 * 32;
    vbyte += bit_len(ds , & vbyte_enc);
    unary += 2 * 32;
    unary += bit_len(ds , & unary_enc);
    gamma += 2 * 32;
    gamma += bit_len(ds , & gamma_enc);
    delta += 2 * 32;
    delta += bit_len(ds , & delta_enc);
    int rmin = -1;
    for(int b = 1 ; b <= 31 ; b++){
      int r = 2 * 32;
      r += 5; //sizeof(b)
      r += bit_len(ds , RiceEncoder(b));
      if(rmin < 0 || r < rmin){
        rmin = r;
      }
    }
    rice += rmin;
    rmin = -1;
    for(int b = 1 ; b <= 31 ; b++){
      int r = 2 * 32;
      r += 5; //sizeof(b)
      r += pforDeltaLen(ds , b); 
      if(rmin < 0 || r < rmin){
        rmin = r;
      }
    }
    pdelta += rmin;
    totalPointer += ds.size();
  }
  cout << "# of total pointer " << totalPointer << endl;
  cout << "null(MByte)" << (null >> 23) << endl;
  cout << "null(bit per pointer): " << (1.0 * null / totalPointer) << endl;
  cout << "vbyte(MByte)" << (vbyte >> 23) << endl;
  cout << "vbyte(bit per pointer): " << (1.0 * vbyte / totalPointer) << endl;
  cout << "unary(MByte)" << (unary >> 23) << endl;
  cout << "unary(bit per pointer): " << (1.0 * unary / totalPointer) << endl;
  cout << "gamma(MByte)" << (gamma >> 23) << endl;
  cout << "gamma(bit per pointer): " << (1.0 * gamma / totalPointer) << endl;
  cout << "delta(MByte)" << (delta >> 23) << endl;
  cout << "delta(bit per pointer): " << (1.0 * delta / totalPointer) << endl;
  cout << "rice(MByte)" << (rice >> 23) << endl;
  cout << "rice(bit per pointer): " << (1.0 * rice / totalPointer) << endl;
  cout << "pforDelra(MByte)" << (pdelta >> 23) << endl;
  cout << "pforDelta(bit per pointer): " << (1.0 * pdelta / totalPointer) << endl;
}

int main(){
  compress("merge.pointer");
}

実行結果

null(MByte)1537
null(bit per pointer): 32.4403
vbyte(MByte)497
vbyte(bit per pointer): 10.4945
unary(MByte)239475
unary(bit per pointer): 5052.43
gamma(MByte)474
gamma(bit per pointer): 10.0026
delta(MByte)407
delta(bit per pointer): 8.59053
rice(MByte)367
rice(bit per pointer): 7.75678
pforDelra(MByte)455
pforDelta(bit per pointer): 9.60173