Doclist压缩方法简介

本文是作者在学习doclist压缩时的一点总结，希望以尽可能简单明了的方式描述各个算法的思想和适用场景，帮助同学们理解和比较。本文并不涉及具体的算法实现，代码请大家自行google。这里需要强调的是“所谓的改进顺序”只是作者yy出来方便理解记忆，并不反应真实的压缩方法发展历程。

1.什么是doclist？

倒排表的基本组成部分，看例子：

Computer： 10,35,100,170,370,29000,30000,30010

表示computer这个词出现在编号（docid）为10,35,100,170,37029000,30000,30010的doc中，10,35,100,170,370,29000,30000,30010即为doclist，在下文中作者会多次使用这个例子来演示压缩算法以及计算压缩比，但请注意这个例子是作者虚构的，所以按照例子得到的结论并不能代表每个算法的真实优劣。

在搜索引擎倒排索引中需要大量保存这类数据，如何高效的存储和访问成为一个搜索引擎性能高低的关键。对一个压缩方法的效果进行评估主要看以下3个方面：1. 压缩速度，2.压缩比3.解压缩速度。可以认为这3个是互相影响和制约的，一般来说压缩速度越慢，压缩比越高，解压缩也越慢。而对搜索引擎来说这3个因素中最关注的是3和2，可以适当放宽的是1.为什么？因为doclist压缩只有一次即建索引的时候，而每次查询都需要解压缩；压缩比高则索引越小，更多的索引可以放内存，查询速度自然更快。

2.最naive的方法：定长int

方法：使用定长的int来精确记录每一个docid

小改进1：由于docid为不可能为负数，可以使用uint来保存

小改进2：根据docid的取值范围选择u16，u32，u64

小改进3：根据docid的取值范围选择合适的bit数N，N>=logMAXDocid，这样每个数只需要N个bit。这里有一个内存访问对齐的问题，每次取一个数效率不高，怎么办？一次取32（64）个数，自然就是对齐的了嘛。

3.改进1：Variable Byte

定长int方案的问题：小的docid需要使用和大的docid一样的存储空间，这是很不划算的。

改进目标：小的docid使用少的存储空间

改进方法：每个byte的第一位为flag，表示是否继续使用下一个byte，剩下7位为有效位，所有的有效位组成数字的2进制表示。

改进效果：小数字使用的byte明显减少

继续上面的例子：

4.改进2：存delta

改进1的最主要的问题：因为每个byte的可用bit少了1/8,大数字要占用更多的byte。就是上面29000,30000,30010的情况，本来2个byte可以保存的数现在需要3个byte了。直接导致在小数字省下3个byte的情况下总byte数和u16方式保存一样。

改进目标：在保证信息不丢失的情况下减少大数字的出现概率

改进方法：考虑到docid的有序特性，可以只保存和前一个docid的delta。以上面的例子来说明：

改进效果：大数字出现次数明显减少，压缩效果提升明显

5.改进3：unary code

问题： 存delta时，小数字变多，尤其是高频词，delta很小，按照byte粒度来编码浪费太大

改进目标：高效的存储小数字

改进方法：对数字N 编码为n个1，后面跟一个0

小改进：由于Delta取值范围[1,max-min]，对数字N编码为n-1个1，后面跟一个0

改进效果：很小的数字编码效率极高。

6.改进4：Group VarInt

问题：unary code只适合很小的数字，大数字相当不划算，看10的编码就知道了，更不用说100了。最终unary code是配合其他编码方式一起使用。从目前来看还是Variable Byte能兼顾大小数字。前面我们主要关注的是压缩比，但是从解压缩性能的角度看Variable Byte有一个问题，对每个byte的flag bit进行判断会导致cpu预测失败，打乱整个流水线的执行，从而使解压缩效率降低。

改进目标：减少解压缩时的判断

改进方法：4个数为1组，第一个byte里面每2个bit记录一个数的byte数，后续byte全是payload

改进效果：解压缩4个数，如果采用Variable Byte则最少4次判断，最多16次判断。而GroupVarInt只需要对第一个byte的每种组合进行switch判断，这样一次判断就可以解压缩4个数。但是从压缩率的角度看每个数字现在都需要多存2个bit，如果小数字比较多（<=127)则压缩率不如Variable Byte。

7.改进5：γ code

问题：小数字按照byte来编码比较浪费，例子中：10,25,65,70 这四个数采用Variable Byte需要4个byte。

改进目标：每个数按照bit来编码

改进方法：把一个数的编码分为2个部分，1.length，即bit数 2.value；length部分由unary code来编码；value记录数字2进制表示时移除第一个1之后的部分

8.改进6：δ code

问题：通过上面的例子可以看出γ code的压缩比不尽如人意，主要原因是γ code的length 压缩效率不高

改进目标：提高length部分的压缩比率

改进方法：length部分使用γ code再次编码

可以看到压缩比有提高。

9.改进7：Simple 9

问题：δ code 中length的2次压缩导致解压会变慢，能不能不存length？

改进目标：不存length

改进方法：32bit 分两块，4个bit记录后面28bit的使用方式，即模式。后续28个bit实际存数字。Simple9的意思就是有9个简单的模式，即1*28bit，2*14bit，3*9bit，4*7bit，5*5bit，7*4bit，9*3bit，14*2bit，28*1bit

前4个数满足4*7bit的模式，所以只需要32bit即可存储。杯具的是28630这个数，只能用1*28bit的模式来存，导致200这个数也只能用1*28的模式来存。

10.改进8：Simple16

问题：Simple9还有bit的浪费。第一，4个bit可以表示16种模式，simple9用了9种。第二，3*9bit，5*5bit，9*3bit 这三种模式下没有完全利用28个有效位。

改进目标：绝不放过任何一个bit

改进方法：扩展为16个状态

举例：5*5-》3*6+2*5，2*5+3*6

添加2*10+8，8+16等模式

此时200,28630就可以采用8+16的模式在32bit里搞定了，压缩效果优于simple9.

11.改进9：PForDelta

问题：后续数字的组合不是所有的情况都能充分利用simple16。即某些情况下模式里的bit不能完全利用。上面的例子，由于有28630的存在，需要15个bit，在simple9的情况下必须使用28bit来存。统计发现doclist里面存在突变的情况，我们称之为异常数，而这种情况正是simple9，simple16的软肋。

改进目标：对异常数进行特殊处理，保证正常数的高效存储，

改进方法：

1. 一次处理一批docid，目前常用的选择是128。想想看为啥？
2. 找到一个数字N，90%以上的数字可以用N个bit存储
3. 128*N bit构成一个数组，正常数直接存储，异常数对应位置存下一个异常值的offset，需要额外记录第一个异常数的offset，通过这个值和异常值位置的值可以找到全部异常数。
4. 对异常numb单独存储在数组后，可以简单使用用定长int

10,25,65,70,200,28630,1000,100取N=8异常值为 28630,1000这两个数字存在数组后面



改进效果：多个论文说明PForDelta压缩比率和解压缩速度都相当牛B，目前是多个搜索引擎的不二选择。

12.改进10：NewPFD

问题：如果异常值刚好在128个数的尾部，N bit不能存下下一个异常的offset会出现什么情况呢？1.增大N，考虑到N的放大效应（N*128）这样压缩比必然受到影响。2.强制添加异常值，即把正常值当做异常值来保存。异常值的特殊处理会导致解压缩效率的降低。

改进目标：异常值出现在任何位置都不需要特殊处理

改进方法：

1. 数组的N bit保存存异常值的低N bit
2. 溢出的部分和异常值的位置链表存在数组后面，由于数字会比较小，采用S9或者S16进行编码

这里简单说明一下解压缩的过程，首先取出数组得到8个数的值。然后根据第一个异常的offset知道第6个数是异常，取第一个异常的值111和对应位置的214进行合并，得到原始值28630；然后读取111后下一个异常值的offset：1，知道第7个值也是异常值，取3和对应位置的232合并，得到原始值1000。

111，1,3这部分一般采用Simple9或者Simple16进行压缩，这里就不演示了。

13.有个小插曲，

PForDelta 或者NewPFD在异常值越少的情况下压缩效果越好。研究表明如果对doc进行预排序，以网页搜索为例如果把类似主题或者相同网站的网页组织在一起，文本倒排的doclist采用PForDelta 或者NewPFD压缩比随机组织会有较大提升。其中的原因你们懂得。

14.换个思路看压缩方法：Golomb code & Rice code

也换个例子：5,10,16,22,25,37,39,43

这样任何数字就变成了绿色的2部分。第一部分可以用unary code编码，第二部分因为取值范围固定，可以用定长bit来保存。具体编码大家参考前面的内容就应该很容易搞定。

这个算法最tricky的是如何选择b，还好已经有论文告诉我们取b=0.69*average最优。Rice code是对Golomb code的优化，即取2的幂。这个优化主要是解压缩效率的提升，想想看为什么？