此文已由作者刘超授权网易云社区发布。

欢迎访问网易云社区，了解更多网易技术产品运营经验

选择插入中间数值13，左面需要留一个坑Left=1，右面需要留一个坑Right=1，所以13可以插入在从13到19这7个坑里，共7种选择，需要3bit，编码13-13=0为000。

数值13的插入将倒排表和坑分为两部分，左面<Length=1, Low=12, High=12>，只有一个数值的倒排表要插入唯一的一个坑，右面<Length=1,Low=14,High=20>，只有一个数值的倒排表插入从14到20的坑。

对于<Length=1, Low=12, High=12>，如图，一个数一个坑，不用占用任何bit就可以。

 

对于<Length=1,Low=14,High=20>，如图，只有一个值17，放在14到20之间7个坑中，有7中选择，需要3bit，编码17-14=3为011。

 

综上所述，最终的编码为0111 110 010 0 000 011，共17位。如果用Golomb编码差值<3，5，1，2，1，1，4>，经计算b=2，则编码共18位。差值编码表现更好。

那么解码过程应该如何呢？初始我们知道<Length=7，Low = 1，High=20>，首先解码的是中间的也即第3个数值，由于Left=3，Right=3，则可这个数值必定在从4到17，表示这14种选择需要4位，因而读取最初的4位0111为7，加上Low + Left = 4，第3个数值解码为11。

已知第3个数值为11后，则左面应该有三个数值，而且一定是从1到10，表示为<Length=3, Low=1, High=10>，右面的也应该有三个数值，而且一定是从12到20，表示为<Length=3, low=12, high=20>。

先解码左面<Length=3, Low=1, High=10>，解码中间的数值，也即第1个数值，由于Left=1，Right=1，则这个数值必定从2到9，表示8种选择需要3位，因而读出3位110，为6，加上Low+Left=2，第1个数值解码为8。

数值8左面还有一个数值，在1到7之间，表示7种选择需要3位，读出3位010，为2，加上Low=1，第0个数值解码为3。

数值8右面还有一个数值，在9到10之间，表示2种选择需要1位，读出1位0，为0，加上Low=9，第2个数值解码为9。

然后解码<Length=3, low=12, high=20>，解码中间的数值，也即第5个数值，由于Left=1，Right=1，则这个数值必定从13到19，表示7中选择需要3位，读出3位000，为0，加上low=13，第5个数值解码为13。

数值13左面还有一个数值，在12到12之间，必定是12，无需读取，第4个数值解码为12。

数值13右面还有一个数值，在14到20之间，表示7种选择需要3位，读出3位011，为3，加上low=14，则第6个数值解码为17。

解码完毕。

9. Variable Byte编码

上述所有的编码方式有一个共同点，就是需要一位一位的进行处理，称为基于位的编码(bitwise)。这样一分钱一分钱的节省，的确符合咱们勤俭持家的传统美德，也能节约不少存储空间。

然而在计算机中，数据的存储和计算的都是以字(Word)为单位进行的，一个字中包含的位数成为字长，比如32位，或者64位。一个字包含多个字节(Byte)，字节成为存储的基本单位。如果使用bitwise的编码方法，则意味着在编码和解码过程中面临者大量的位操作，从而影响速度。

对于信息检索系统来讲，相比于存储空间的节省，查询速度尤为重要。所以我们将目光从省转移到快，基于字节编码(Bytewise)是以一个或者多个字节(Byte)为单位的。

最常见的基于字节的编码就是变长字节编码(Variable Byte)，它的规则比较简单，一个Byte共8个bit，其中最高位的1个bit表示一个flag，0表示这是最后一个字节，1表示这个数还没完，后面还跟着其他的字节，另外7个bit是真正的数值。

如图所示，比如编码120，表示成二进制是1111000没有超过7个bit，所以用一个byte就能保存，最高位置0。如果编码130，表示成二进制是10000010，已经有8个bit了，所以需要用两个byte来保存，第一个byte保存第一个bit，最高位置1，接下来的一个byte保存剩下的7个bit，最高位置0。如果数值再大一些，比如20000，则需要三个byte才能保存。

 

变长字节编码的解码也相对简单，每次读一个byte，然后判断最高位，如果是0则结束，如果是1则再读一个byte，然后再判断最高位，直到遇到最高位为0的，将几个byte的数据部分拼接起来即可。

从变长字节编码的原理可以看出，相对于基于位的编码，它是一次处理一个字节的，相应付出的代价就是空间有些浪费，比如130编码后的第一个字节，本来就保存一个1，还是用了7位。

变长字节编码作为基于字节的编码方式，的确比基于位的编码方式表现出来较好的速度。在Falk Scholer的论文《Compression of Inverted Indexes For Fast Query Evaluation》中，很好的比较了这两种类型的编码方式。

如图所示，图中的简称的意思是Del表示Delta编码，Gam表示Gamma编码，Gol表示Golomb编码，Ric表示Rice编码，Vby表示Variable Bytes编码，D表示文档ID，F表示Term的频率Term Frequency，O表示Term在文档中的偏移量Offset。GolD-GamF-VbyO表示用Golomb编码来表示文档ID，用Gamma编码来表示Term频率，用Vby来表示偏移量。

文中对大小两个文档集合进行的测试，从图中我们可以看出变长字节编码虽然在空间上有所浪费，然而在查询速度上却表现良好。

 

10. PFORDelta编码

变长字节编码的一个缺点就是虽然它是基于byte进行编码的，但是每解码一个byte，都要进行一次位操作。

解决这个问题的一个思路就是，将多个byte作为一组(Patch)放在一起，将Flag集中起来，作为一个Header保存每个数值占用几个byte，一次判断一组，我们称为Signature block，如图所示。

 

对于Header中的8个bit，分别表示接下来8个byte的flag，前三个0表示前三个byte各编码一个数值，接下来1表示下一个byte属于第四个数值，然后接下来的1表示下一个byte也属于第四个数值，接下来0表示没有下一个byte了，因而110表示的三个byte编码一个数值。最后10表示最后两个byte编码第五个数值。

细心的同学可能看出来了，Header里面就是一元编码呀。

那么再改进一下，在Header里面咱们用二进制编码，每两位组成一个二进制码，这个二进制数表示每一个数值的长度，长度的单位是一个byte，这样两位可以表示32个bit，基本可以表示所有的整数。00表示一个byte，01表示2个byte，10表示3个byte，11表示4个byte，这种方式称为长度编码(Length Encoding)，如图。

 

如果数比较大，32位不够怎么办？用三位，那总共8位也不够分的啊？于是有人改变思路，Header里面的8位并不表示长度，而是8个flag，每个flag表示是否能够压缩到n个byte，n是一个参数，0表示能，则压缩为n个byte，1表示不能，则用原来的长度表示。这种方法叫做Binary Length Encoding。如同所示。

 

这里参数n=2，也即如果一个32位整数能压缩为2个byte，则压缩，否则就用全部32位表示。比如第三个数字，其实用三位就能够表示的，但是由于不能压缩成为2个byte，也是用完整的32位来表示的。

Binary Length Encoding已经为将数值分组打包(Patch)压缩提供了一个很好的思路，就是将数值分为两大部分，可以压缩的便打包处理，太大不能压缩的可单独处理。这种思想成为PForDelta编码的基础。

然而Binary length Encoding是将能压缩的和不能压缩的混合起来存储的，这其实是不利于我们批量压缩和解压缩的，必须一个数值一个数值的判断。

而PForDelta做了改进，将两部分的分开存储。试想如果m个数值都是压缩成b个bit的，就可以打包在一起，这样批量读出m*b个bit，一起解压便可。而其他不可压缩的，我们放在另外的地方。只要我们通过参数，控制b的大小，使得能压缩的占多数，不能压缩的占少数，批量处理完打包好的，然后再一个个料理不能打包的残兵游勇。可压缩部分我们成为编码区域(Code Section)，不可压缩的部分我们成为异常区域(Excepton Section)。

当然分开存储有个很大的问题，就是不能保持原来数值列表的顺序，而我们要压缩的倒排表是需要保持顺序的。如同所示。

 

一个最直接的想法是，如图(a)，在原来异常数值(Exception Value)出现的位置保留一个指针，指向异常区域中这个数值的位置。然而一个很大的问题就是这个指针只能占用b个bit，往往不够一个指针的长度。

另外一个替代的方法是，如图(b)，我们如果知道第一个异常数值出现的位置(简称异常位置)，并且知道异常区域的起始位置，我们可以在b个bit里面保存下一个异常位置的偏移量(因为偏移量为0没有意义，所以存放0表示距离1，存放i表示距离i+1)，由于编码区域是密集保存的，所以b个bit往往够用。解压缩的时候，我们先批量将整个编码区域解压出来，然后找到第一个异常位置，原本放在这个位置的数值应该是异常区域的第一个值，然后异常位置里面解压出3，说明第二个异常位置是当前位置加4，找到第二个异常位置后，原本放在这个位置的数值应该是异常区域的第二个值，以此类推。这个将异常位置串起来的链表我们称为异常链。

然而如果很不幸，b个bit不够用，下一个异常位置的偏移量超过了2^b个bit。如图(c)，b=2，然而下一个异常位置距离为7，2位放不开，我们就需要在距离为4的位置人为插入一个异常位置，当前位置里面写11，异常位置里面写7-4-1=2，当然异常区域中也需要插入一个不存在的数值。这样做的缺点是增加了无用的数值，降低了压缩率，为了减少这种情况的出现，所以实践中b不要小于4。

这就是PForDelta的基本思路。PForDelta，全称Patched Frame Of Reference-Delta，其中压缩后的n个bit，称为一个Frame，Patched就是将这些Frame进行打包，Delta表示我们打包压缩的是差值。

PForDelta是将数值分块(Block)存储的，一块中可以包含百万个数值，大小可以达到几个Megabyte，一般的方法是，在内存中保存一个m个Megabyte的缓存区域(Buffer)，然后不断的读取数据，将这个缓存区域按照一定的格式填满，便可以写入硬盘，然后再继续压缩。

块内部的格式如图所示。

 

块内部分为四个部分，在图中这四个部分是分开画的，其实是一个部分紧接着下一个部分的。编码区域和异常区域之间可能会有一些空隙，下面介绍中会讲到为什么。在图中的例子里面，我们还假设32bit足够保存原始数值。

第一部分是Header，里面保存了这个块的大小，比如1M，大小应该是32或者64的整数倍。另外保存了压缩的数值所用的bit数为b。

第二部分是Entry point的数组，有N项，每一个Entry管理128个数值。每一项32位，其中前7位表示这个Entry管理的128个数值中第一个异常位置，后25位保存了这128个数值的异常区域的起始位置。这个数组的存在是为了在一个块中随机访问。

第三部分是编码区域(Code Section)，存放了一系列压缩为b个bit的数值，每128个被一个entry管理，总共有128*N个数值，数值是从前向后依次排放的。在这个部分中，异常位置是以异常链的形式串起来的。

第四部分是异常区域(Exception Section)，存放不能压缩，以32个bit存储原始数值的部分。这一部分的数值是从后往前排放的。由于每128个数值中异常数值的个数不是固定的，所以仅仅靠这部分不能确定哪些属于哪个entry管理。在一个entry中，有指向起始位置的指针，然后根据编码区域中的异常链，依次一个一个找异常数值。

编码区域是从前往后增长的，异常区域是从后往前增长的，在缓存块中，当中间的空间不足的时候，就留下一段空隙。为了提高效率，我们希望解压缩的时候是字对齐(word align)的，也即希望一次处理32个bit。假设Header是占用32个bit，每个Entry也是32个bit，异常区域是32个bit一个数值的，然而编码区域则不是，比如5个bit一个数值，假设一共有100个数值，则需要500个bit，不是32的整数倍，最后多余20个bit，则需要填充12个0，然后使得编码区域字对齐后再存放异常区域。索性我们的设计中，一个entry是管理128个数值的，所以最后一定会是32的整数倍，一定是字对齐的，不需要填充，可以保证写入硬盘的时候，编码区域和异常区域是紧密相邻的。

PForDelta的字对齐和批量处理，意味着我们已经从一个bit一个bit处理的个人手工业时代，到了机械大工业时代。如图。在硬盘上是海量的索引文件，是由多个PForDelta块组成的，在压缩和解压过程中，需要有一部分缓存在内存中，然后其中一个块可以进入CPU Cache，每块的结构都是32位对齐的，对于32位机器，寄存器也是32位的。于是我们可以想象，CPU就像一个卓别林扮演的工人，来了32个bit，处理完毕，接着下一个32位，流水作业。

 

下面咱们就通过一个例子，具体看一下PForDelta的压缩和解压方法。

我们假设有以下266个数值：

Input = [26, 24, 27, 24, 28, 32, 25, 29, 28, 26, 28, 31, 32, 30, 32, 26, 25, 26, 31, 27, 29, 25, 29, 27, 26, 26, 31, 26, 25, 30, 32, 28, 23, 25, 31, 31, 27, 24, 32, 30, 24, 29, 32, 26, 32, 32, 26, 30, 28, 24, 23, 28, 31, 25, 23, 32, 30, 27, 32, 27, 27, 28, 32, 25, 26, 23, 30, 31, 24, 29, 27, 23, 29, 25, 31, 29, 25, 23, 31, 32, 32, 31, 29, 25, 31, 23, 26, 27, 31, 25, 28, 26, 27, 25, 24, 24, 30, 23, 29, 30, 32, 31, 25, 24, 27, 31, 23, 31, 29, 28, 24, 26, 25, 31, 25, 26, 23, 29, 29, 27, 30, 23, 32, 26, 31, 27, 27, 29, 23, 32, 28, 28, 23, 28, 31, 25, 25, 26, 24, 30, 25, 28, 26, 28, 32, 27, 23, 31, 24, 25, 31, 27, 31, 24, 24, 24, 30, 27, 28, 23, 25, 31, 27, 24, 23, 25, 30, 23, 24, 32, 26, 31, 28, 25, 24, 24, 23, 28, 28, 28, 32, 29, 27, 27, 29, 25, 25, 32, 27, 31, 32, 28, 27, 32, 26, 23, 26, 31, 24, 32, 29, 27, 27, 25, 31, 31, 24, 23, 32, 30, 28, 29, 29, 28, 32, 26, 26, 27, 27, 29, 24, 25, 31, 27, 30, 28, 29, 27, 31, 25, 26, 26, 30, 31, 29, 30, 31, 26, 24, 29, 28, 25, 30, 24, 25, 23, 24, 32, 23, 32, 24, 27, 28, 29, 27, 31, 28, 29, 29, 32, 25, 26, 27, 29, 23, 26]

根据上面说过的原理，足够需要三个entry来管理。

首先在索引过程中，这些数值是一个个到来的，经过初步的统计，发现数值32是最大的，并且占到总数的10%多一点，所以我们可以将32作为异常数值。其他的数值都在0-31之间，用5个bit就可以表示，所以b=5。

下面我们就可以开始压缩了，我们是一个entry一个entry的来压缩的，所以128个数值为一组，代码如下：

//存放编码区域压缩前数值

int[] codes = new int[128];

//记录每个异常数值的位置，miss[i]表示第i个异常数值的位置

int[] miss = new int[numOfExceptions];

int numOfCodes = 0;

int numOfExcepts = 0;

int numOfJump = 0;

//第一个循环，构造编码区，并且统计异常数值位置

//每128个数值一组，或者不够128则剩下的一组

while(from < input.length && numOfCodes < 128){

//统计从上次遇到异常数值开始，遇到的普通数值的个数

numOfJump = (input[from] > maxCode)?0:(numOfJump+1);

//如果两个异常数值之间的间隔太大，则必须认为插入一个异常数值。maxJumpCode是指b=5的情况下能表示的最大间隔31。之所以判断numOfExcepts > 0，是因为第一个异常位置用7个bit保存在entry里面，所以在哪里都可以。

if(numOfJump > maxJumpCode && numOfExcepts > 0){

codes[numOfCodes] = -1;

miss[numOfExcepts] = numOfCodes;

numOfCodes++;

numOfExcepts++;

numOfJump = 0;

}

//编码区域的构造。这个地方是最简单的情况，就是input的数值直接进入编码区域，这里还可以用其他的编码方式(比如用Golomb)进行一次编码。

codes[numOfCodes] = input[from];

//只有遇到异常数值的时候numOfExcepts才加一

miss[numOfExcepts] = numOfCodes;

numOfExcepts += (input[from] > maxCode)?1:0;

numOfCodes++;

from++;

}

//构造完编码区域后，可以对entry进行初始化，7位保存第一个异常位置，25位保存异常区域的起始位置。

int prev = miss[0];

entries[curEntry++]=prev << 25 | (curException & 0x1FFFFFF);

//第二个循环，构造异常链和异常区域

exceptionSection[curException--] = codes[prev];

for(int i=1; i < numOfExcepts; i++){

int cur = miss[i];

codes[prev] = cur - prev - 1;

prev = cur;

exceptionSection[curException--] = codes[cur];

}

codes[prev] = numOfCodes - prev - 1;

//最后将编码区域压缩，其中codes是压缩前的数值，numOfCodes是数值的个数，codeSection是一个int数组，用于存放压缩后的数值，curCode是当前codeSection可以从哪个位置开始写入，bwidth=5

curCode += pack(codes, numOfCodes, codeSection, curCode, bwidth);

整个过程是两次循环构造未压缩的编码区域和异常区域，如下面的表格所示。表格中每一列中上面的数值是input，下面的数值是未压缩编码区域数值，其中黄色的部分便是异常位置：

Entry 1的未压缩编码区域

Entry 2的未压缩编码区域，其中第214个异常位置和第248个异常位置中间隔了33个位置，无法用5个bit表示，于是在第216个位置人为插入一个异常位置，就是红色的部分。

Entry 3的未压缩编码区域，本来input中只有266个数值，这里又添加两个0数值(绿色的部分)是为什么呢？因为每个数值压缩后将占用5个bit，如果只有11个数值的话共55位，而要求字对齐的话，需要64位，因而需要人为添加9个0.

11.1—11.15云计算基础服务全场5折起

免费体验云安全(易盾)内容安全、验证码等服务

更多网易技术、产品、运营经验分享请点击。