搜索引擎的设计(3)：倒排表的设计下
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不够用，下一个异常位置的偏移量超过了2b个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.
下面应该对编码区域进行压缩了，在大多数的实现中，压缩代码多少有些晦涩难懂。一般来说，会对每一种b有一个代码实现，在这里我们举例列出的是b=5的代码实现。
整个过程我们可以想象成codeSection是一条条32位大小的袋子，而codes是一系列待压缩的32位的物品，其中货真价实的就5位，其他都是水分(都是0)，下面要做的事情就是把待压缩的物品一件件拿出来，把有水分挤掉，然后往袋子里面装。
装的时候就面临一个问题，32不是5的整数倍，放6个还空着2位，放7个不够空间，这循环怎么写啊？所以只能以小公倍数32*5=160位为一个处理批次，放在一个循环里面，也即每个循环处理5个袋子，32个物品，使得32个物品正好能放在5个袋子里面。
//bwidth=5
private static int pack(int[] codes, int numOfCodes, int[] codeSection,
int curCode, int bWidth) {
int cur = 0;
// suppose bwidth = 5
// bwidth不一定能被32的整除，所以每32个一组，保证处理完以后，32*bwidth个bit，一定是字对齐的。
while (cur < numOfCodes) {
codeSection[curCode + 0] = 0;
codeSection[curCode + 1] = 0;
codeSection[curCode + 2] = 0;
codeSection[curCode + 3] = 0;
codeSection[curCode + 4] = 0;
//curCode + 0是个袋子，先放codes里面从cur+0到cur+5六个物品后，还空着2位，于是把第七个物品前2位截出来，放进去。0x18二进制11000，作用就是后5位保留前两位，然后右移3位，就把前2位放到了袋子的后2位。
codeSection[curCode + 0] |= codes[cur + 0] << (32 - 5);
codeSection[curCode + 0] |= codes[cur + 1] << (32 - 10);
codeSection[curCode + 0] |= codes[cur + 2] << (32 - 15);
codeSection[curCode + 0] |= codes[cur + 3] << (32 - 20);
codeSection[curCode + 0] |= codes[cur + 4] << (32 - 25);
codeSection[curCode + 0] |= codes[cur + 5] << (32 - 30);
codeSection[curCode + 0] |= (codes[cur + 6] & 0x18) >> 3;
//curCode+1是第二个袋子。刚才第七个物品前2位被截了放在个袋子里，那么首先剩下的3位放在第二个袋子的开头，0x07就是00111，也就是截取后三位。然后再放5个物品，还空着4位，于是第十三个物品截取前四位(0x1E二进制11110)。
codeSection[curCode + 1] |= (codes[cur + 6] & 0x07) << (32 - 3);
codeSection[curCode + 1] |= codes[cur + 7] << (32 - 3 - 5);
codeSection[curCode + 1] |= codes[cur + 8] << (32 - 3 - 10);
codeSection[curCode + 1] |= codes[cur + 9] << (32 - 3 - 15);
codeSection[curCode + 1] |= codes[cur + 10] << (32 - 3 - 20);
codeSection[curCode + 1] |= codes[cur + 11] << (32 - 3 - 25);
codeSection[curCode + 1] |= (codes[cur + 12] & 0x1E) >> 1;
//curCode + 2第三个袋子。先放第十三个物品剩下的1位(0x01二进制00001)，然后再放入6个物品，后空着1位。将第二十个物品的第1位截取出来(0x10二进制10000)放入。
codeSection[curCode + 2] |= (codes[cur + 12] & 0x01) << (32 - 1);
codeSection[curCode + 2] |= codes[cur + 13] << (32 - 1 - 5);
codeSection[curCode + 2] |= codes[cur + 14] << (32 - 1 - 10);
codeSection[curCode + 2] |= codes[cur + 15] << (32 - 1 - 15);
codeSection[curCode + 2] |= codes[cur + 16] << (32 - 1 - 20);
codeSection[curCode + 2] |= codes[cur + 17] << (32 - 1 - 25);
codeSection[curCode + 2] |= codes[cur + 18] << (32 - 1 - 30);
codeSection[curCode + 2] |= (codes[cur + 19] & 0x10) >> 4;
//curCode + 3第四个袋子。先放第二十个物品剩下的4位(0x0F二进制位01111)。然后放5个物品，后还空着3位。将第二十六个物品截取3位放入(0x1C二进制11100)。
codeSection[curCode + 3] |= (codes[cur + 19] & 0x0F) << (32 - 4);
codeSection[curCode + 3] |= codes[cur + 20] << (32 - 4 - 5);
codeSection[curCode + 3] |= codes[cur + 21] << (32 - 4 - 10);
codeSection[curCode + 3] |= codes[cur + 22] << (32 - 4 - 15);
codeSection[curCode + 3] |= codes[cur + 23] << (32 - 4 - 20);
codeSection[curCode + 3] |= codes[cur + 24] << (32 - 4 - 25);
codeSection[curCode + 3] |= (codes[cur + 25] & 0x1C) >> 2;
//curCode + 4第五个袋子。先放第二十六个物品剩下的2位。后这个袋子还剩30位，正好放下6个物品。
codeSection[curCode + 4] |= (codes[cur + 25] & 0x03) << (32 - 2);
codeSection[curCode + 4] |= codes[cur + 26] << (32 - 2 - 5);
codeSection[curCode + 4] |= codes[cur + 27] << (32 - 2 - 10);
codeSection[curCode + 4] |= codes[cur + 28] << (32 - 2 - 15);
codeSection[curCode + 4] |= codes[cur + 29] << (32 - 2 - 20);
codeSection[curCode + 4] |= codes[cur + 30] << (32 - 2 - 25);
codeSection[curCode + 4] |= codes[cur + 31] << (32 - 2 - 30);
//处理下一组
cur += 32;
curCode += 5;
}
int numOfWords = (int) Math.ceil((double) (numOfCodes * 5) / 32.0);
return numOfWords;
}
经过压缩后，整个block的格式如下，整个block被组织成int数组，[]里面的数值为下标：
Header：这部分只占用32位，在这里包含四部分，部分5位，表示b=5。第二部分表示Entry部分的长度，占用了3个32位，也即有三个Entry。第三部分表示编码区域的长度，占用了42个
Entry列表：包含3个entry，每个entry占用32位，前7位表示个异常位置，后25位表示这个entry在异常区域中的起始位置。
编码区域。总共占用42个int，每5个int可以存放32个压缩后的编码(每个编码占用5位)。第三个entry共占用两个int，保存了11个数值占用55位，另外人为补充9个0.
异常区域。在块中，异常区域是从后向前延伸的。其中从74到60的红色部分属于Entry 1，从59到50的黄色部分属于Entry 2，绿色部分属于Entry 3。
当需要读取这个快的时候，便需要对这个块进行解码。
首先通过解析Header来得到全局信息。
接下来需要读取Entry列表，来解析每个Entry中的信息。
然后对于每个Entry进行解码，代码如下：
//解析entry，得到全局信息
int entrycode = entries[i];
int firstExceptPosition = entrycode >> 25;
int curException = entrycode & 0x1FFFFFF;
//进行解压缩，将编码区域5位一个数值解压为一个int数组。Codes就是解压后的数组，tempCodeSection指向编码区域这个Entry的起始位置，numOfCodes是需要解压的数值的个数，bwidth=5.
Unpack(codes, numOfCodes, tempCodeSection, bwidth);
//个循环将异常数值还原
int cur = firstExceptPosition;
while (cur < numOfCodes && curException >= lastException) {
int jump = codes[cur];
codes[cur] = block[curException--];
cur = cur + jump + 1;
}
//第二个循环输出结果并且跳过人为添加的异常数值
for (int j = 0; j < codes.length; j++) {
if (codes[j] > 0) {
output[curOutput++] = codes[j];
}
}
对编码区域的解压方式也正好是压缩方式的逆向过程。是从袋子里面将物品拿出来的时候了。
private static void Unpack(int[] codes, int numberOfCodes, int[] codeSection,
int bwidth) {
int cur = 0;
int curCode = 0;
while (cur < numberOfCodes) {
//从个袋子中，拿出6个物品，还剩2位。
codes[cur + 0] = (codeSection[curCode + 0] >> (32 - 5)) & 0x1F;
codes[cur + 1] = (codeSection[curCode + 0] >> (32 - 10)) & 0x1F;
codes[cur + 2] = (codeSection[curCode + 0] >> (32 - 15)) & 0x1F;
codes[cur + 3] = (codeSection[curCode + 0] >> (32 - 20)) & 0x1F;
codes[cur + 4] = (codeSection[curCode + 0] >> (32 - 25)) & 0x1F;
codes[cur + 5] = (codeSection[curCode + 0] >> (32 - 30)) & 0x1F;
codes[cur + 6] = (codeSection[curCode + 0] << 3) & 0x18;
//个袋子中的2位和第二个袋子中的前3位组成第7个物品。然后接着从第二个袋子中拿出5个物品，剩下4位。
codes[cur + 6] |= (codeSection[curCode + 1] >> (32 - 3)) & 0x07;
codes[cur + 7] = (codeSection[curCode + 1] >> (32 - 3 - 5)) & 0x1F;
codes[cur + 8] = (codeSection[curCode + 1] >> (32 - 3 - 10)) & 0x1F;
codes[cur + 9] = (codeSection[curCode + 1] >> (32 - 3 - 15)) & 0x1F;
codes[cur + 10] = (codeSection[curCode + 1] >> (32 - 3 - 20)) & 0x1F;
codes[cur + 11] = (codeSection[curCode + 1] >> (32 - 3 - 25)) & 0x1F;
codes[cur + 12] = (codeSection[curCode + 1] << 1) & 0x1E;
//第二个袋子的后4位和第三个袋子的前1位组成一个物品，然后在第三个袋子里面拿出6个物品，剩下1位。
codes[cur + 12] |= (codeSection[curCode + 2] >> (32 - 1)) & 0x01;
codes[cur + 13] = (codeSection[curCode + 2] >> (32 - 1 - 5)) & 0x1F;
codes[cur + 14] = (codeSection[curCode + 2] >> (32 - 1 - 10)) & 0x1F;
codes[cur + 15] = (codeSection[curCode + 2] >> (32 - 1 - 15)) & 0x1F;
codes[cur + 16] = (codeSection[curCode + 2] >> (32 - 1 - 20)) & 0x1F;
codes[cur + 17] = (codeSection[curCode + 2] >> (32 - 1 - 25)) & 0x1F;
codes[cur + 18] = (codeSection[curCode + 2] >> (32 - 1 - 30)) & 0x1F;
codes[cur + 19] = (codeSection[curCode + 2] << 4) & 0x10;
//第三个袋子的后1位和第四个袋子的前4位组成一个物品，然后从第四个袋子中拿出5个物品，剩下3位。
codes[cur + 19] |= (codeSection[curCode + 3] >> (32 - 4)) & 0x0F;
codes[cur + 20] = (codeSection[curCode + 3] >> (32 - 4 - 5)) & 0x1F;
codes[cur + 21] = (codeSection[curCode + 3] >> (32 - 4 - 10)) & 0x1F;
codes[cur + 22] = (codeSection[curCode + 3] >> (32 - 4 - 15)) & 0x1F;
codes[cur + 23] = (codeSection[curCode + 3] >> (32 - 4 - 20)) & 0x1F;
codes[cur + 24] = (codeSection[curCode + 3] >> (32 - 4 - 25)) & 0x1F;
codes[cur + 25] = (codeSection[curCode + 3] << 2) & 0x1C;
//第四个袋子剩下的3位和第五个袋子的前2位组成一个物品，然后第五个袋子取出6个物品。
codes[cur + 25] |= (codeSection[curCode + 4] >> (32 - 2)) & 0x03;
codes[cur + 26] = (codeSection[curCode + 4] >> (32 - 2 - 5)) & 0x1F;
codes[cur + 27] = (codeSection[curCode + 4] >> (32 - 2 - 10)) & 0x1F;
codes[cur + 28] = (codeSection[curCode + 4] >> (32 - 2 - 15)) & 0x1F;
codes[cur + 29] = (codeSection[curCode + 4] >> (32 - 2 - 20)) & 0x1F;
codes[cur + 30] = (codeSection[curCode + 4] >> (32 - 2 - 25)) & 0x1F;
codes[cur + 31] = (codeSection[curCode + 4] >> (32 - 2 - 30)) & 0x1F;
cur += 32;
curCode += 5;
}
}
11. Simple Family
另一种多个数值打包在一起，并且是字对齐的编码方式，就是下面我们要介绍的Simple家族。
对于32位机器，一个字是32个bit，我们希望这32个bit里面可以放多个数值。比如1位的放32个，2位的放16个，3位放10个，不过浪费2位，4位放8个，5位放6个，6位放5个，7位和8位都是4个算一样，9位，10位都是放3个，11位，12位一直到16位都是放2个，32位放1个，共10种方法。那么来了32位，我们怎么区分里面是哪种方法呢？在放置真正的数据之前，需要放置一个选择器(selector)，来表示我们是怎么存储的，10种方法4位就够了。
如果这4位另外存储，就不是字对齐的了，所以还是将这4位放在32位里面，这样数据位就剩了28位了。那这28位怎么安排呢？1位的28个，2位的14个，3位的9个，4位的7个，5位的5个，6位和7位的4个，8位和9位的3个，10位到14位的都是2个，15位到28位的都是1个，共9种。如果同样存储2个，当然选长的位数14，所以形成以下的表格：
由于一共9种情况，所以这种编码方式称为Simple-9。
4位selector来表示9，太浪费了，浪费了差不多一半的编码(24=16)，如果少一种情况，8种的话，就少一位做selector，多一位保存数值了，比如去掉selector=e这种情况，所有5位的都保存成7位，这样保存数据就是29位了，很遗憾，29是个质数，除了1和本身不能被任何数整除，多出的一位也往往浪费掉。
于是我们再进一步，用30位来保存数值，这样会有10种情况，而且浪费的情况也减少了。如下面的表格所示：
虽然看起来30比28要好一些，然而剩下的两位如何表示10种情况呢？我们假设文档编号之间的差值不会剧烈抖动，一会儿大一会儿小，而是维持在一个稳定的水平，就算发生突然的变化，变化完毕后也能保持较稳定的水平。所以我们可以采取这样的策略，首先对于个32位，假设selector是某一个数r，比如r=f，6位保存一个数值，那么下一个32位开始的两位表示四种情况：
1) 如果用的位数少，比如3位就够，则selector=r-1=e，也即用5位保存
2) 如果用的位数不变，还是用6位保存，则selector=r
3) 如果用的位数多 ，selector=r+1=g，也即用7位保存
4) 如果r+1=7位放不下，比如需要10位，说明了变化比较突然，于是r取大值j，用30位来保存。
一旦出现了突然的较大变化，则会使用大的selector j，然后随着突然变化后的慢慢平滑，selector还会降到一个文档的值。当然，如果事先经过统计，发现大的文档间隔也不过需要15位，则对于第四种情况，可以使得r=i。
这种用相对的方式来表示10种情况，成为Relative-10。
既然selector只需要2位，那么上面的表格中selector=d和selector=g的没有用的两位，不是也可以成为下一个32位的selector么？这样下一个整个32位都可以来保存数据了。
另外上面表格中每个数值的编码长度一栏为什么会从7跳到10呢？是因为8位，9位，10位都只能保存3个，当然用大的10位了。然而如果没有用的2位可以留给下一个32位做selector，那就有必要做区分了，比如一个值只需要9位，咱们就用9位，三九二十七，剩下的三位中的两位作为下一个32位的selector。另外14位和15位也是这个情况，如果两个14位，就可以剩下两位作为下一个的selector，如果是两个15位就没有给下一个剩下什么。
这样selector由10种情况变成了12种情况，如图下面的表格所示：
如果上一个32位剩下2位作为selector，则当前的32位则可以全部用于保存数据。当然也会有剩余，可留给后来人。那么32位全部用来保存数据的情况下，selector应该如下面表格所示：
这样每个32位都分为两种情况，一种是上一个留下了2位做selector，本身32位都保存数据，另一种是上一个没有留下什么，本身2位做selector，30位做数据。
这种上一个32位为下一个留下遗产，共12种情况的，成为Carryover-12编码。
下面举一个具体的例子，比如我们想编码如下的输入：
int[] input = {5, 30, 120, 60, 140, 160, 120, 240, 300, 200, 500, 800, 300, 900};
首先定义上面的两个编码表：
class Item {
public Item(int lengthOfCode, int numOfCodes, boolean leftForNext) {
this.lengthOfCode = lengthOfCode;
this.numOfCodes = numOfCodes;
this.leftForNext = leftForNext;
}
int lengthOfCode;
int numOfCodes;
boolean leftForNext;
}
static Item[] noPreviousSelector = new Item [12];
static {
noPreviousSelector[0] = new Item(1, 30, false);
noPreviousSelector[1] = new Item(2, 15, false);
noPreviousSelector[2] = new Item(3, 10, false);
noPreviousSelector[3] = new Item(4, 7, true);
noPreviousSelector[4] = new Item(5, 6, false);
noPreviousSelector[5] = new Item(6, 5, false);
noPreviousSelector[6] = new Item(7, 4, true);
noPreviousSelector[7] = new Item(9, 3, true);
noPreviousSelector[8] = new Item(10, 3, false);
noPreviousSelector[9] = new Item(14, 2, true);
noPreviousSelector[10] = new Item(15, 2, false);
noPreviousSelector[11] = new Item(28, 1, true);
}
static Item[] hasPreviousSelector = new Item [12];
static {
hasPreviousSelector[0] = new Item(1, 32, false);
hasPreviousSelector[1] = new Item(2, 16, false);
hasPreviousSelector[2] = new Item(3, 10, true);
hasPreviousSelector[3] = new Item(4, 8, false);
hasPreviousSelector[4] = new Item(5, 6, true);
hasPreviousSelector[5] = new Item(6, 5, true);
hasPreviousSelector[6] = new Item(7, 4, true);
hasPreviousSelector[7] = new Item(8, 4, false);
hasPreviousSelector[8] = new Item(10, 3, true);
hasPreviousSelector[9] = new Item(15, 2, true);
hasPreviousSelector[10] = new Item(16, 2, false);
hasPreviousSelector[11] = new Item(28, 1, true);
}
形成的编码格式如图
假设约定的起始selector为6，也即表3-10的g行。对于个32位，是不会有前面遗传下来的selector的，所以前两位表示selector=1，也即就用原始值6，第g行，接下来应该是4个7位的数值，后剩余两位作为下一个32位的selector。Selector=2，所以用6+1=7，也即表3-11的h行，下面的整个32位都是数值，保存了4个8位的，没有遗留下什么。接下来的32位中，头两位是selector=1，还是第7行，也即第h行，只不过是表3-10中的，所以接下来应该是3个9位，遗留下后两位selector=2，也即是7+1=8行，也即表3-11的第i行，接下来应该是3个10位的。
整个解码的过程如下：
//block是编码好的块，defaultSelector是默认的selector
private static int[] decompress(int[] block, int defaultSelector, int numOfCodes) {
//当前处理到编码块的哪一个int
int curInBlock = 0;
//解码结果
int[] output = new int[numOfCodes];
int curInOutput = 0;
//前一个selector，用于根据相对值计算当前selector的值
int prevSelector = defaultSelector;
int curSelector = 0;
//初的编码表用当然是没有遗留的
Item[] curSelectorTable = noPreviousSelector;
//尚未处理的bit数
int bitsRemaining = 0;
//当前int中每个编码的bit数
int bitsPerCode = curSelectorTable[curSelector].lengthOfCode;
//当前要解码的32位编码
int cur = 0;
//一个循环，当curInBlock > block.length的时候，编码块已经处理完毕，但是还需要等待后一个32位处理完毕，当bitsRemaining大于等于bitsPerCode的时候，说明还有没处理完的编码
while (curInBlock < block.length || bitsRemaining >= bitsPerCode) {
//当bitsRemaining不足一个编码的时候，说明当前的32位处理完毕，应该读入下一个32位了。
if(bitsRemaining < bitsPerCode){
//当bitsRemaining小于2，说明当前32位剩下的不足2位，不够给下一个做selector的，因而下一个selector在下一个32位的头两位。
if(bitsRemaining < 2){
//取下一个32位
cur = block[curInBlock++];
//前两位为selector
int selector = (cur >> 30) & 0x03;
//根据selector的相对值计算当前的selector
if(selector == 0){
curSelector = prevSelector - 1;
} else if (selector == 1){
curSelector = prevSelector;
} else if (selector == 2) {
curSelector = prevSelector + 1;
} else {
curSelector = curSelectorTable.length - 1;
}
prevSelector = curSelector;
//当前32位中数据仅仅占30位
bitsRemaining = 30;
//使用编码表3-10
curSelectorTable = noPreviousSelector;
}
//如果bitRemaining大于等于2，足够给下一个做selector，则解析后两位为selector。
else {
int selector = cur & 0x03;
if(selector == 0){
curSelector = prevSelector - 1;
} else if (selector == 1){
curSelector = prevSelector;
} else if (selector == 2) {
curSelector = prevSelector + 1;
} else {
curSelector = curSelectorTable.length - 1;
}
prevSelector = curSelector;
//取下一个32位，全部用于保存数值
cur = block[curInBlock++];
bitsRemaining = 32;
//使用编码表3-11
curSelectorTable = hasPreviousSelector;
}
bitsPerCode = curSelectorTable[curSelector].lengthOfCode;
}
//在bitRemaing中截取一个编码，解码到输出，更新bitsRemaining
int mask = (1 << bitsPerCode) - 1;
output[curInOutput++] = (cur >> (bitsRemaining - bitsPerCode)) & mask;
bitsRemaining = bitsRemaining - bitsPerCode;
}
return output;
}
12. 跳跃表
上面说了很多的编码方式，能够让倒排表又小又快的存储和解码。
但是对于倒排表的访问除了顺序读取，还有随机访问的问题，比如我想得到第31篇文档的ID。
点，差值编码使得每个文档ID都很小，是个不错的选择。第二点，上面所述的很多编码方式都是变长的，一个挨着一个存储的。这两点使得随机访问成为一个问题，首先因为第二点我们根本不知道第30篇文档在文件中的什么位置，其次就算是找到了，因为第二点，找到的也是差值，需要知道上一个才能知道自己，然而上一个也是差值，难不成每访问一篇文档整个倒排表都解压缩一遍？
看过前面前端编码的同学可能想起了，差值和前缀这不差不多的概念么？弄几个排头兵不就行啦。
如图，上面的倒排表被用差值编码表示成了下面一行的数值。我们将倒排表分成组，比如3个数值一组，每组有个排头兵，排头兵不是差值编码的，这样如果你找第31篇文档，那它肯定在第10组里面的第二个，只需要解压一个组的就可以了。
有了跳跃表，根据文档ID查找位置也容易了，比如要在文档57，在排头兵中可以直接跳过17,34,45，肯定在52的组里，发现52+5=57，一进组就找到了。
当然排头兵如果比较大，也可以用差值编码，是基于前一个排头兵的差值，由于排头兵比较少，反正查找的时候要一个个看，都解压了也没问题。
如果链表比较长，导致排头兵比较多，没问题还可以有多级跳跃表，排头兵还有排头兵，排长上面是连长。这样查找的时候，先查找连长，找到所在的连再查找排长，然后再进组查找。
上面提到的PForDelta的编码方式可以和跳跃表进行整合，由于PForDelta的编码区域是定长的，基本可以满足随机访问，然而对于差值问题，可以再entry中添加排头兵的值的信息，使得128个数值成为一组。
我们姑且称这种方式为跳跃表规则。
相关文章