第6讲 索引压缩 Index compression 授课人：高曙明 信息检索与Web搜索 第6讲 索引压缩 Index compression 授课人：高曙明 *改编自“现代信息检索”网上公开课件（http://ir.ict.ac.cn/~wangbin）

索引压缩 什么是索引压缩？ 压缩分类： 是指用较少的比特存储原始索引数据 无损压缩：压缩之后所有原始信息都被保留 有损压缩：压缩之后会丢掉一些信息 2

为什么要压缩? 大规模文档集的索引数据巨大，进行压缩具有以 下优点： 减少磁盘空间 (节省开销) 加快从磁盘到内存的数据传输速度 (加快检索速度) [读压缩数据到内存+在内存中解压]比直接读入未压缩数据要 快很多 前提: 解压速度很快 增加内存存储内容 (加快检索速度) 比如，可以尽可能将词典放入内存 3

样本文档集 Reuters RCV1 原始统计数据 词项的统计特性分析 N L M T 文档数目 每篇文档的词条数目 词项数目(= 词类数目) 每个词条的字节数 (含空格和标点) 每个词条的字节数 (不含空格和标点) 每个词项的字节数 无位置信息索引中的倒排记录数目 800,000 200 400,000 6 4.5 7.5 100,000,000 样本文档集 Reuters RCV1 原始统计数据 4

预处理对词典大小和无位置信息倒排记录数目影响很大！ 预处理后的统计数据 预处理对词典大小和无位置信息倒排记录数目影响很大！ 5

词项数目的估计—Heaps定律 Heaps定律: M = kTb M 是词汇表大小, T 是文档集的大小(所有词条的 个数) 参数k 和b 的一个经典取值是: 30 ≤ k ≤ 100 及 b ≈ 0.5. Heaps定律在对数空间下是线性的 推论：词汇表大小会随着文档集的大小增长而增长！ 6

Heaps定律在RCV1上的表现 k = 101.64 ≈ 44 b = 0.49 图中通过最小二乘法拟合出 的直线方程为： log10M =0.49 ∗ log10T + 1.64 即：M = 101.64T 0.49 k = 101.64 ≈ 44 b = 0.49 7

词项的分布 — Zipf定律 Zipf定律: cfi 是第 i 常见的词项ti的文档集频率(collection frequency)， 即词项ti在所有文档中出现的次数 于是，如果最常见的词项(the)出现cf1 次，那么第二常见 的词项 (of)出现次数为 第三常见的词项 (and) 出现次数为 另一种表示方式: cfi = cik 或 log cfi = log c +k log i (k = −1) 8

Zipf定律在RCV1上的表现 拟合度不是非常高 但可以发现： 高频词项很少， 低频罕见词项很多 9

词典压缩 进行词典压缩的必要性： 最好能将词典放入内存，以提高查询效率 满足一些特定领域特定应用的需要，如手机、 机载计算机上的应用 保证快速启动 与其他应用程序共享资源 10

定长数组方式下的词典存储 空间需求： 20 字节 4 字节 4 字节 空间需求： 20 字节 4 字节 4 字节 对Reuters RCV1语料: (20+4+4)*400,000 = 11.2 MB 11

定长方式的不足 英语中每个词项的平均长度为8个字符 因此，对所有词项采用固定的20个字节存储造成 空间浪费 即使是长度为1的词项，我们也分配20个字节 不能处理长度大于20字节的词项，如 HYDROCHLOROFLUOROCARBONS SUPERCALIFRAGILISTICEXPIALIDOCIOUS 理想方案：对每个词项平均只使用8个字节来存储 12

基于单一字符串的压缩方法 将整部词典作为一个字符串存储 每个词项存一个定位指针 两指针之间的字符构成一个词项 13

单一字符串方式下的空间消耗 每个词项的词项频率需要4个字节 每个词项指向倒排记录表的指针需要4个字节 每个词项平均需要8个字节 指向字符串的指针需要3个字节 (8*400000个位置需 要log2（8 * 400000） < 24 位来表示) 空间消耗: 400,000 × (4 +4 +3 + 8) = 7.6MB (而定 长数组方式需要11.2MB) 14

将长字符串中的词项进行分组变成大小为k的块（即k个词项为一组） 按块存储的压缩方法 每个块存一个指针 字符串中存词项的 长度 以k=4个词项为一 块，则每个词项节 省12B-7B=5B 整个词典节省 0.5MB 将长字符串中的词项进行分组变成大小为k的块（即k个词项为一组） 15

两种方式下的词项查找 二分查找 先二分查找，再线性查找（在块内部） 16

前端编码技术(Front coding) 基本思想：通过省略词项之间公共前缀实现压缩 举例 按块存储压缩后的某个块 (k = 4) ⇓ 8 a u t o m a t a 8 a u t o m a t e 9 a u t o m a t i c 10 a u t o m a t i o n ⇓ . . . 可以采用前端编码方式继续压缩为： 8 a u t o m a t ∗ a 1 ⋄ e 2 ⋄ i c 3 ⋄ i o n 17

Reuters RCV1词典压缩情况总表 18

倒排记录表压缩 问题分析 主要存储内容：doc ID 需要采用多少位表示 doc ID? 对于Reuters RCV1，可以采用log2 800,000 ≈ 19.6 < 20 位来表示每个docID 如何压缩 doc ID 的表示？ 19

采用间隔编码的压缩方法 倒排记录表的一个特点： doc IDi+1=doc IDi +(doc IDi+1- doc IDi ) 自第二个记录开始，可以只存储间隔 通常间隔较小（特别是高频词） 显然，对doc ID 采用间隔编码可以压缩空间 20

变长编码 目标 为了实现上述目标，需要设计一个变长编码(variable length encoding) 对于 ARACHNOCENTRIC 及其他罕见词项, 对每个间 隔仍然使用20比特 对于THE及其他高频词项，每个间隔仅仅使用很少的 比特位来编码 为了实现上述目标，需要设计一个变长编码(variable length encoding) 可变长编码对于小间隔采用短编码而对于长间隔采用 长编码 21

可变字节(VB)码 基本思想：利用整数个字节对间距编码，字节的 数目根据具体的间距确定，一个表中的所有倒排 记录作为一字节流存放 举例 被很多商用/研究系统所采用 22

VB 编码算法 将字节的第一位设置为延续位，用于标识间距编码的结束 如果间隔表示少于7比特，那么c 置 1，将间隔编入一个字节 的后7位中 否则：将低7位放入当前字节中，并将c 置 0，剩下的位数采 用同样的方法进行处理，最后一个字节的c置1（表示结束） 23

VB编码的解码算法 24

ϒ编码 是一种基于位的变长编码 最简单的位编码：一元码 将 n 表示成 n 个1和最后一个0 比如： 3的一元码是 1110 40的一元码是 11111111111111111111111111111111111111110 70的一元码是： 1111111111111111111111111111111111111111111111111 1111111111111111111110 25

ϒ编码方法 将G 表示成长度(length)和偏移(offset)两部分 偏移对应G的二进制编码，只不过将首部的1去掉 长度部分给出的是偏移的位数 长度部分采用一元编码: 1110 举例: 13的ϒ编码 13 → 1101 → 101 = 偏移 G=13 (偏移为 101), 长度部分为 3 13的整个ϒ编码是1110101 26

ϒ编码的例子 27

ϒ编码的长度 偏移部分是 ⌊log2 G⌋ 比特位 长度部分需要 ⌊log2 G⌋ + 1 比特位 ϒ 编码的长度均是奇数 ϒ 编码在最优编码长度的2倍左右 28

ϒ 编码的性质 ϒ 编码是前缀无关的，从而保证了解码的唯一性。 编码在最优编码的2或3倍之内 上述结果并不依赖于间隔的分布，是通用性 (universal)编码 ϒ 编码是无参数编码，不需要通过拟合得到参数 29

ϒ 编码的对齐问题 机器通常有字边界 – 8, 16, 32 位 按照位进行压缩或其他处理可能会较慢 可变字节码通常按字边界对齐，因此可能效率 更高 除去效率高之外，可变字节码虽然额外增加了 一点点开销，但是在概念上也要简单很多 30

Reuters RCV1索引压缩总表 31

参考资料 《信息检索导论》第5章 http://ifnlp.org/ir 有关字对齐二元编码的原文Anh and Moffat (2005); 及 Anh and Moffat (2006a) 有关可变字节码的原文Scholer, Williams, Yiannis and Zobel (2002) 更多的有关压缩 (包括位置和频率信息的压缩)的细 节参考Zobel and Moffat (2006) 32

课后作业 见课程网页: http://www.cad.zju.edu.cn/home/smgao/IR