第6讲 索引压缩 Index compression 授课人：高曙明

Presentation on theme: "第6讲 索引压缩 Index compression 授课人：高曙明"— Presentation transcript:

1 第6讲 索引压缩 Index compression 授课人：高曙明
信息检索与Web搜索 第6讲 索引压缩 Index compression 授课人：高曙明 *改编自“现代信息检索”网上公开课件（

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

17 前端编码技术(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

18 Reuters RCV1词典压缩情况总表 18

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

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

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

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

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

24 VB编码的解码算法 24

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

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

27 ϒ编码的例子 27

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

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

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

31 Reuters RCV1索引压缩总表 31

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

33 课后作业 见课程网页: