研究生课程：现代信息检索-第3讲 索引压缩
《现代信息检索》课程笔记：第3讲 索引压缩
第3讲 索引压缩
压缩
举例：将长编码串用短编码串来代替：111111111111111111➡18个1
为什么要压缩?
- 减少磁盘空间占用（节省开销）
- 增加内存存储内容（加快速度）
- 加快从磁盘到内存的数据传输速度（同样加快速度）
- 读压缩数据到内存+在内存中解压，比直接读入未压缩数据到内存要快很多
为什么在IR中需要压缩?
- 占用更少的硬盘空间
- 更经济，节省空间
- 将更多数据载入内存
- 加快处理速度（内存中读写很快）
- 减少从磁盘读入内存的时间
- 大型搜索引擎将相当比例的倒排记录表都放入内存（硬盘？）
IR中压缩的两个基本要求：无损压缩和随机访问
压缩的一个基本问题：对齐，即建立不同压缩单元之间的分界标识
有损压缩：丢弃一些信息-很多常用的预处理步骤可以看成是有损压缩
无损压缩：所有信息都保留-索引压缩中通常都使用无损压缩
词项统计量
词典压缩中词典的大小即词汇表的大小是关键
词汇表大小会随着文档集的大小增长而增长，没有办法估计数量。
存在一个经验规律可以进行估计：
Heaps定律：
Heaps定律在对数空间下是线性的。
在容许拼写错误或者对拼写错误自动纠错的情况下，Heaps定律的效果如何？
- 存在拼写错误：会增加词项数目
- 自动纠错：总体词项数目趋于正常
- 对效果有一定影响，但是除非存在大量拼写错误，否则不会有显著影响。
倒排记录表压缩中词项的分布情况是关键
我们还需要知道在文档集中有多少高频词项和低频词项
Zipf定律：第
实际统计中可以发现拟合度并不是很高，但是可以发现高频词项很少，低频罕见词项很多。
词典压缩
一般而言，相对于倒排记录表，词典所占空间较小。但是我们想将词典放入内存，另外满足一些特定领域特定应用的需要，如手机、机
载计算机上的应用或要求快速启动等需求。因此，压缩词典也很重要。
定长数组方式下的词典存储：每个词项需要20（字符串）+4（词频）+4（指向倒排索引表的指针）=28个字节。
不足之处：
- 大量存储空间被浪费
- 即使是长度为1的词项，我们也分配20个字节，但是英语中每个词项的平均长度为8个字符
- 不能处理长度大于20字节的词项
将整部词典看成单一字符串：4（词频）+4（指向倒排索引表的指针）+3（指向字符串的指针，按照实际大小决定，例如8*400000个位置需要$log_2(8 * 400000)< 24 $位来表示）+8（每个字符串平均需要8个字节）=19个字节
按块存储，假设块大小k=4，此时每4个词项只需要保留1个词项指针，但是同时需要增加4个字节（比较短，1个字节就可以）来表示每个词项的长度，因此每4个词项需要3+4=7B，比之前的节省了12-7=5B
但是不采用块存储方式下的词项查找是典型的二叉查找，而采用块存储方式下的词项查找需要进行顺序查找，块如果太大会影响效率。
每个块当中，会有公共前缀，可以采用前端编码方式继续压缩。
哪些前缀应该用于前端编码？需要在哪些方面有所权衡？
- 同一个单词的不同形式适合使用这种前端编码
- 没有什么公共前缀的话，压缩效果不太好，而且还会导致检索速度下降
倒排记录表压缩
倒排记录表空间远大于词典，压缩关键是对每条倒排记录进行压缩
关键思想：存储 docID间隔而不是 docID本身
设计一个变长编码(variable length encoding)：可变长编码对于小间隔采用短编码而对于长间隔采用长编码
可变字节(VB)码：设定一个专用位 (高位) c作为延续位(continuation bit)，如果间隔表示少于7比特，那么c置1，将间隔编入一个
字节的后7位中；否则将高7位放入当前字节中，并将c置0，剩下的位数采用同样的方法进行处理，最后一个字节的c置1（表
示结束）
- 除字节外，还可以采用不同的对齐单位：比如32位(word)、16位及4位(nibble)等等
- 如果有很多很小的间隔，那么采用可变字节码会浪费很多空间，而此时采用4位为单位将会节省空间
一元码：将n表示成n个1和最后一个0
基于位的编码：
- 将G (Gap, 间隔) 表示成长度(length)和偏移(offset)两部分
- 偏移对应G的二进制编码，只不过将首部的1去掉（因为所有的编码第一位都是1）
- 长度部分给出的是偏移的位数，采用一元编码
- 手动计算的时候先计算偏移，再根据偏移计算长度
偏移部分是
编码是前缀无关的，也就是说一个合法的
组变长整数编码：
- 按块存储，每块大小为5-17个字节，存放4个整数编码
- 每块首字节：4个2位的二进制长度，
- 使用
字节（在4–16之间）存放4个整数
Simple9编码：每块4字节，前4位标识块内结构，剩余28位存储若干个数字，每个数字占用相同的位数。