搜索引擎索引压缩技术

/*版权声明：可以任意转载，转载时请务必标明文章原始出处和作者信息 .*/   
                    
                     搜索引擎索引压缩技术
                    
                     张俊林
                     timestamp:2006-12-15
                    
  建立索引是搜索引擎核心技术之一，建立索引的目的是能够快速的响应用户的查询。搜索引擎最常用的索引数据结构是倒排文档，倒排文档的原理其实相当简单。
     我们拿以下三篇文章作为代表来说明倒排文档，文章内容为：
     D1:“张钰小姐代表了中国广大淫民的根本利益”                    
     D2:”宋祖德先生代表了中国八卦文化的前进方向“
     D3:“郭敬明代表了中国作家抄袭先进生产力的发展要求”
 
     经过分词，过滤高频词后可以构建如下的倒排文档：
    
     张钰 ->D1,1;
     代表->D1,1;D2,1;D3,1;
     宋祖德->D2,1;
     .....
    
     其中，“张钰”代表一个单词，《D1,1》代表了这个单词在D1文档中出现过1次（TF）；为了方便处理，往往会  把单词和文档编号转换为数字形式。     
   说到倒排文档压缩，首先要问一个问题：为什么要进行索引压缩？
   对索引进行压缩有很多好处：比如可以 减少索引占用的磁盘空间和内存；比如可以减少I/O读写量； 比如可以查询响应速度加快；
    为了能够增加压缩效果，一般在进行压缩前先改写索引内容，首先把倒排索引的数值按照大小排序，然后用差值而非实际值表示（d-gap)；这个是每个压缩算法开展前要做的工作；
    目前的压缩方法可以分为固定长度的和变长压缩。
1.固定长度的压缩方法   
  一个典型的方法是比特对齐压缩，这个方法以Byte为编码单元，不像变长压缩编码一般都以bit为编码单元；
  对于要压缩的数字，一般用头两个bits代表长度，其它bit用二进制编码代表数值本身；
  数值范围  头两个bit   压缩大小
  0-63       00         1byte
  64-16k     01         2byte
  16k-4M     10         3byte
  4M-1G      11         4byte
 
  包括定长的和变长的索引压缩都有一个基本假设，就是：要压缩的大多数数值都比较小，所以压缩后占用空间不会多；
  压缩率：10-20% of 原始未压缩索引；
 
2.变长的压缩方法
  a.unary
    对于要压缩的数值N来说，用N+1 个bits来表示，其中前N位是1，最后一位是0作为结束标记。
    比如：
    5：111110
    10：11111111110
   
  b.Elias压缩方法(gamma & delta)
  对于一个要压缩的数值X，用log2(x)分解为两个数值，一个是N=log2(X)，用N个1表示这个部分,另外一个是
  剩余部分k=X-2powor((log2(X))),这部分数值k用二进制编码表示（长度等于N），中间用0隔开；
 
  比如对于数值2，其压缩编码为1 0 0，因为log2(2)=1, 剩余为0；中间插入一个分割0；
    
   比如对于数值10
   N=log2(10)=3   所以第一个部分是：111
   10-2（3）=2    所以第二个部分是：010
   中间用0分割，所以是：111 0 010
  
   c.Golomb压缩方法
    对于一个要压缩的数值X，用公式分解：X=q*b+r+1; (0=<r<b)
    其中，b叫做bucket size,可以根据情况来具体设置。我们假设b=3;
    那么对于要压缩的数值10来说：
    10=3*3+0+1；（q=3,b=3,r=0);
   
    第一部分是对分解因子q进行编码，其编码方法类似于unary编码；比如对于10=3*3+0+1中，
    q=1110；
    第二部分是对于剩余因子r进行编码；仍然采用二进制编码，编码长度为log2(b)取上整数或者log2(b)上整数-1;
    对于上面r=0; 其编码为0;
   
    Golomb相对于Elias方法的好处就在于那个bucket size，这个值是可以设定的，可以根据索引里面
    要压缩的数值的分布来调整bucket size来获得更好的压缩效果；
   
  d.混合使用
  一般对于不同的索引域，其数值的分布是不同的，各有其特点，经过分析数值分布属性，可以采取混合压缩策略。比如D-gap使用Golomb压缩，tf使用Gamma压缩。
    
  采用索引压缩能够带来很多好处，所以实用的搜索引擎都会采用索引压缩技术，但是对索引进行压缩也会带来问题，
 那就是比不压缩需要更多的计算量。