Algorithm 版 (精华区)

发信人: ssos (存在与虚无), 信区: Algorithm
标  题: 倒排文件压缩算法
发信站: 哈工大紫丁香 (2001年06月08日21:20:32 星期五), 站内信件

倒排文件压缩算法
中科院计算所99博士生 张磊
zhanglei@mail.ruc.edu.cn
摘要
搜索引擎一般采用倒排文件作为索引机制，在倒排文件中保存词目对应的文档编号的列
表。而如果采用一般的数据类型如长整型来表示文档编号存在如下缺点：存在最大值限
制，占用大量磁盘空间等。因此对倒排文件的压缩势在必行，压缩的倒排文件不仅大大
降低了存储空间的占用，并通过减少磁盘访问次数来减少检索系统的响应时间，这也是
成功的搜索引擎的必备条件。本文对倒排文件的压缩算法进行深入的探讨，给出有效的
解决方案。
关键词：搜索引擎，信息检索，倒排文件
介绍
我们正处于一个信息爆炸的时代，因特网已经渗入人们的日常生活，只需轻轻一揿鼠标
就可以看到各种各样的信息。但是网络的庞大常常让人感到无所适从，人们陷入网络迷
宫，难以找到所需的信息。搜索引擎应运而生，它可以根据用户提出的关键词进行查询
，返回包含这些关键词的页面，甚至还可以按照相关程度对结果进行排序。搜索引擎中
一般包含四部分：人机界面，查询处理器，索引生成器和网络蜘蛛[1]。
索引生成器负责建立词典和倒排文件，提供给查询处理器进行查询。在倒排文件中保存
词目对应的文档编号的列表。如果采用一般的数据类型如长整型来表示文档编号存在如
下缺点：存在最大值限制，占用大量磁盘空间等。通过压缩倒排文件，可以大幅度减小
磁盘空间占用，另外减少磁盘访问次数，从而提高查询性能。
索引结构
对于文本检索来说，最有效的索引结构则是倒排文件：它是一个列表集合，每个词目t对
应一条记录，在记录中列出了包含此词目的所有文档d的标识符。
倒排文件可被视为文档-词目频率矩阵的转置，从(d,t)转换为(t,d)，因为行优先的访问
比列优先的访问更为有效。
索引文件包含三部分：词典（invf.dict），倒排文件（invf）和两者之间的映射文件（
invf.idx）。
invf.dict  invf.idx  invf
t f_t F_t → t#→invf Addr → d0,f0 d1,f1 ... dn,fn
图1 索引文件结构
在词典（invf.dict）中：对于每个不同的词目t，保存
? 词目字符串t
? 包含t的文档总数f_t
? t在整个文档集合中总的出现次数F_t
在映射文件（invf.idx）中：对于每个不同的词目t，保存
? 指向相应倒排列表起始地址的指针
在倒排文件（invf）中：对于每个不同的词目t，保存
? 包含t的每个文档的标识符d（顺序的数值）
? t在每个文档d中的出现频率fd,t，存储为<d, fd,t>的列表。
另外和权重数组Wd一起，就可以满足布尔查询（Boolean Query）和分级查询（Ranked 
Query）的需要。
倒排文件压缩算法
不失一般性，倒排列表可被视为一个递增的整数序列。例如，假设某个词目在8个文档中
出现，对应的倒排列表为：
(8; 3, 5, 20, 21, 23, 76, 77, 78)
对于词目t，它在ft个文档中出现，则对应的倒排列表为：
(ft; d1,d2,...,dft)，
其中dk<dk+1，0<k<ft。定义d-gaps = dk+1-dk，并令d0=0。则上面的倒排列表按步长(
d-gaps)存储为：
(8; 3, 2, 15, 1, 2, 53, 1, 1)
假设文档集合（collection）中共有N个文件，则每个文档标识符最多需要logN个位来存
储。如果采用定长编码则需要预先给定最大标识符，并对每个文档标识符均采用同样长
度的编码表示，这样对于较小的文档标识符就会造成存储空间的浪费。
各种压缩算法会考虑d-gap的概率分布，根据其概率分布来确定编码的长度。压缩算法粗
分为两大类：全局（global）算法和局部（local）算法。
全局算法认为每个倒排列表符合同样的概率分布，而局部算法则认为不同的倒排列表根
据参数符合不同的概率分布，常常用词频（f_t）作为参数。很显然局部算法能够更精确
地反映实际的概率分布，从而取得更高的压缩比。全局算法又分为参数化（parameteri
zed）算法和非参数化（nonparameterized）算法。
算法 发明人
全局算法
非参数化算法
Unary
Binary
γ Elias (1975); Bentley and Yao (1976)
δ Elias (1975); Bentley and Yao (1976)
参数化算法
Bernoulli Golomb (1966); Gallager and Van Voorhis (1975)
Observed frequency
局部算法
Bernoulli Witten, Bell, and Nevill (1992)Bookstein, Klein, and Raita (1992)
Skewed Bernoulli Teuhoal (1978); Moffat and Zobel (1992)
Hyperbolic Schuegraf (1976)
Oberved frequency
Batched frequency Moffat and Zobel (1992)
Interpolative Moffat and Stuiver (1996)
表1 倒排文件压缩算法一览
注：倒排文件压缩常采用局部Bernoulli算法，用Golomb编码来实现[2]。
Unary算法：对于整数x≥1，对应的编码是x-1个1，后跟0。
 x = {前导1的个数} + 1
Binary算法：（x, b）其中x为要编码的值，x∈[1, b]
计算编码的位长度_B_nbits
 ,
x = x – 1
如果 (x < _B_thresh) 则 _B_nbits = _B_logofb –1;
  否则 { _B_nbits = _B_logofb;  x = x + _B_thresh; }
输出x的二进制位流（位长度为_B_nbits）
γ算法：  编码分为两部分，第一部分(Cu)是 对应的Unary编码，第二部分(Cb)是 的二
进制表示。Cb的位数=Cu的位数-1。
 x = 2(Cu-1) + Cb
δ算法：  编码分为两部分，第一部分(Cu)是 对应的γ编码，第二部分(Cb)是 的二进
制表示。
Golomb算法：编码分为两部分，第一部分是(q + 1)对应的Unary编码，其中 ，第二部分
是r = x – qb – 1对应的Binary编码。
 x = r + qb +1
Gap x 编码算法
 Unary γ δ Golomb
    b=3 b=6
1 0 0 0 0 0 0 00
2 10 10 0 100 0 0 10 0 01
3 110 10 1 100 1 0 11 0 100
4 1110 110 00 101 00 10 0 0 101
5 11110 110 01 101 01 10 10 0 110
6 111110 110 10 101 10 10 11 0 111
7 1111110 110 11 101 11 110 0 10 00
8 11111110 1110 000 11000 000 110 10 10 01
9 111111110 1110 001 11000 001 110 11 10 100
10 1111111110 1110 010 11000 010 1110 0 10 101
表2 编码示例
全局Bernoulli模型
很显然为了使模型具有更好的适应性并获得更高的压缩比，就需要利用倒排文件中的指
针密度。假设已知总指针个数为f，除以索引词目个数N和总文档个数n的乘积，就给出了
任意文档中包含任意词目的概率为 。
在此假设之下，间距x出现的概率就等于词目不出现x-1次的概率，即 ，其中p为词目在
任意文档中出现的概率。它符合几何分布，即每个可能的词目-文档对的出现概率与p无
关。如果采用算术编码方法，所需累积概率如下：
1966年南加州大学的Solomon Golomb提出了Golomb编码算法。对于某个参数b，任意的整
数x>0被编码为两部分：第一部分是(q + 1)对应的Unary编码，其中 ，第二部分是r = 
x – qb – 1对应的Binary编码。编码示例请参见表2。
Gallager和Van Voorhis给出以下结论：如果b的选取满足
  (1)
这种编码算法就能够生成一般几何分布的最优自由前缀编码，其概率为p。而且用Golom
b算法可以单步计算Huffman编码，而这是传统Huffman无法做到的。对公式(1)求解，可
以得到
  (2)
其中A是极小倒排文件编码所需的平均二进制位数。不同概率分布对应的b的取值范围如
下表所示：
b “1”的概率
1 0.3820 ≤ p ≤ 1.0000
2 0.2452 ≤ p ≤ 0.3819
3 0.1809 ≤ p ≤ 0.2451
4 0.1434 ≤ p ≤ 0.1818
5 0.1188 ≤ p ≤ 0.1433
6 0.1014 ≤ p ≤ 0.1187
7 0.0885 ≤ p ≤ 0.1013
8 0.0785 ≤ p ≤ 0.0884
9 0.0705 ≤ p ≤ 0.0784
10 0.0640 ≤ p ≤ 0.0704
表2 不同概率分布对应的b的取值范围
假设 ，公式(2)可以简化如下：
   (3)
根据此公式就可以计算出词目对应的b值。
局部Bernoulli模型
如果已知词目t的词频为ft，就可以对每个倒排列表使用Bernoulli模型。对于常见的词
目可以用很小的b进行编码，而对于罕见词目则采用较大的b进行编码。在TREC中，只出
现一次的词目对应的b≈500,000，编码为19，20或21位。而如果一个词目在大约10%的文
档中出现，那么b=7，编码为3位。它和全局模型相比有很大改善：全局模型中b=2,036，
对应编码为11位——1位用于最小的unary编码，10位用于最小的binary编码。非常常见
的词目对应的b为1。当b=1时，编码就与unary编码相同，也就是采用二进制位向量来存
储倒排列表，出现该词的文档用1表示，未出现此词的文档用0表示。
性能评价
在性能评价中采用如下四个样本文档集合，文档总数从31101到741856，所占存储空间从
4.33M到2.07G，以满足不同的信息检索需求。
  文档集合
  Bible GNUbib Comact TREC
文档总数 N 31,101 64,343 261,829 741,856
词目总数 F 884,994 2,570,906 22,805,920 333,338,738
不同词目的总数 n 8,965 46,488 36,660 535,346
索引指针数 f 701,412 2,226,300 12,976,418 134,994,414
存储空间(M)  4.33 14.05 131.86 2070.29
表3 样本文档集合
采用不同压缩算法，对以上样本文档集合进行倒排文件索引，平均每个指针占用的二进
制位数如下表所示：
压缩算法 每个指针占用的位数
 Bible GNUbib Comact TREC
全局算法
Unary 262 909 487 1918
Binary 15 16 18 20
Bernoulli 9.86 11.06 10.90 12.30
γ 6.51 5.68 4.48 6.63
δ 6.23 5.08 4.35 6.38
Observed frequency 5.90 4.82 4.20 5.97
局部算法
Bernoulli 6.09 6.16 5.40 5.84
Interpolative 5.24 3.98 3.87 5.18
表4 压缩效率
从表4中可以看出，Interpolative编码给出了最高的压缩效率，而采用Golomb编码的Be
rnoulli模型比Interpolative编码略差，但却易于实现，因此是一个很好的选择。这两
种算法在压缩及解压时所需的计算资源（内存，CPU）和binary编码处于同一个数量级。

参考文献
[1] Nahur Fonseca, Rodolfo Resende and Wagner Meira, Dynamic Aspects of Docu
ments of the Brazilian Web, 2000
[2] Alistair Moffat and Timothy C. Bell, Manage Gigabytes, 1999

--

   
<<社会契约论>>是一本好书,应当多读几遍
风味的肘子味道不错,我还想再吃它      

※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 202.118.230.220]