第五章索引压缩2014-4-2章节框架•词项统计特性1.Heaps定律2.Zipf定律•词典压缩1.长字符串和词项指针2.按块存储3.前端编码•倒排记录表压缩1.可变字节编码2.γ编码索引压缩的对象IR中两个主要的数据结构：索引压缩的意义1.节省磁盘空间——目标：达到1：4的压缩比例2.增加高速缓存技术的利用率——目标：把常用的条目放入内存存储，减少系统应答时间3.加快数据从磁盘到内存的传输速度——目标：结合高效的解压缩算法提高系统运行速度•本章介绍的解压算法都很高效，可以达到以上目标•索引压缩通常是无损压缩，有损压缩技术在预处理阶段介绍（2.2）本章所用语料库存储所有的（词项ID，文档ID）对需要1.28GB初步处理后的文档集大小为960MB未压缩的文档集词典存储空间为11.2MB未压缩的倒排记录表大小为250MB初步处理后的语料库Heaps定律——词项数目的估计词项数目的估计：Heaps定律M=kTbM是词汇表大小,T是文档集的大小(文档集合中所有词条的个数，即所有文档大小之和)参数k和b的一个经典取值是:30≤k≤100及b≈0.5.Heaps定律通过文档集合中的词条数来估计词汇表大小，词汇表大小会随着文档集的大小增长而增长！Heaps定律结论：随着文档数目的增加，词汇量会持续增长而不会稳定到一个最大值。大规模文档集的词汇量也会非常大。Zipf定律——对词项的分布建模在自然语言的语料库里，一个单词出现的频率与它在频率表里的排名成反比。词项分布的估计：Zipf定律cfi∝(1/i)如果出现最多的词项的出现次数是cf1的话，出现第二多的词项的出现次数就是cf1的一半，出现第三多的词项出现次数会是cf1的1/3，其余均可依此类推。注：cfi是文档频率(collectionfrequency):词项ti在所有文档中出现的次数(不是出现该词项的文档数目df)词典压缩•词典压缩的目的：将词典放入内存•传统的词典存储方式：定长数组M*（20+4+4）=400000*28=11.2MB大量存储空间被浪费，即使是长度为1的词项，我们也分配20个字节；不能处理长度大于20字节的词项；而英语中每个词项的平均长度为8个字符；能否对每个词项平均只使用8个字节来存储?将词典看成单一字符串M*（平均长度+文档频率+倒排记录表指针+词项指针）=400000*（8+4+4+3）=7.6MB按块存储M*（平均长度+文档频率+倒排记录表指针+长度标记+词项指针/k）=400000*（8+4+4+1+3/4）=7.1MBK越大，压缩率越高，但是会牺牲查找速度。每k个词项为一组，每组保留一个词项指针，每词项前用一个字节标记长度。平均时间=查询所需步数/结点个数当所取的k趋于最大，以把词典压缩到最小值：400000*（4+4+1+8）=6.8MB此时词典的查找速度会变得非常慢K的选取必须在压缩和词项查找速度之间保持某种平衡按块存储+前端编码M*（平均长度+文档频率+倒排记录表指针+长度+前缀+词项指针/k）=400000*（4+4+4+1+1+3/4）=5.9MB词典压缩总结倒排记录表压缩•倒排记录表空间远大于词典，至少10倍以上•压缩关键：对每条倒排记录进行压缩•目前每条倒排记录表中存放的是docID.•对于ReutersRCV1(800,000篇文档),当每个docID可以采用4字节（即32位）整数来表示•目标：压缩后每个docID用到的位数远小于20比特•改进要点：采用变长编码方法对间距进行编码。1.按字节压缩——可变字节编码2.按位压缩——γ编码可变字节编码VariableBytecoding设定一个专用位(高位)c作为延续位(continuationbit)。如果间隔表示少于7位，那么c=1，将间隔编入一个字节的后7位中；否则，将低7位放入当前字节中，并将c置0，剩下的位数采用同样的方法进行处理，最后一个字节的c置1（表示结束）。VB编码算法VB解码算法•通过VB编码压缩，可以使语料库索引压缩到116MB，压缩率超过50%。•编码单位的长短和压缩率成反比，和所需的位操作次数成正比。•以字节为单位的压缩率和解压速度之间提供了一个很好的平衡点。γ编码EliasGammacoding一元编码：n的一元编码是在n个1后面加1个0.编码：分别用长度length和偏移offset表示文档间距G。•G的偏移实际上是G的二进制编码，但是其前端的1被去掉。•G的长度是指偏移的长度，用一元编码来表示。偏移部分是⌊log2G⌋位，长度部分需要⌊log2G+1⌋位；因此，全部编码需要2log⌊2G+1⌋位，...
