倒排索引压缩在桌面搜索引擎中的应用

摘要：在数据储存量急遽增大的今天，桌面搜索工具带给我们的好处是――任何人都可以在极短的时间里，从自己所拥有的海量数据中，找到所需要的东西。桌面搜索引擎采用全文索引技术来完成，由于全文检索系统通常处理的都是海量数据，经过处理生成的索引数据也是很大的，因此采用一定的压缩策略，可以节约存储空间。另外，为了使全文索引更加高效，压缩倒排索引有助于提高查询的吞吐量。

关键词：桌面搜索；全文索引；倒排索引；索引压缩

中图分类号：TP391.3 文献标识码：A文章编号：1007-9599 (2011) 10-0000-02

Inverted Index Compression Application in the Desktop Search Engine

Duan Hongjuan

(Basic Education College of Zhanjiang Normal University,Zhanjiang524037,China)

Abstract:As the results of the rapid growth ofthe volume of electronic data,desktop search application made us search the files and the data on PC efficiently and quickly.The full-text index is the main technique of the desktop search,as the data based on the index files are huge,we must compress the large files to save the space on pression of inverted files will result in an increase in query throughput.

Keywords:Desktop search;Full-text index;Inverted index;Index compression

一、概要

（一）全文检索

尽管目前各类系统都带有文件搜索功能，但往往是一种被称作情报检索的方式，其局限性非常明显，用户往往只能通过文件名来搜索文件，最多再加上文件大小，创建/修改时间等一些条件来限制搜索范围，系统通过逐个扫描匹配完成搜索，这种方式查找速度极慢。

桌面搜索能够改进用户组织和查找存储在个人电脑上的大量数据的能力。文本作为信息的主要载体之一，如何快捷有效地管理和检索文本这种非结构化数据成为当前一项紧迫的研究任务，全文检索技术由此应运而生。

全文检索是指以文本为检索对象，允许用户以自然语言根据资料内容而不仅是外在特征来实现信息检索的手段。全面、准确和快速是衡量全文检索系统的关键指标。人们受到书目索引的启发提出了全文索引的思想，而本文研究的倒排索引则是目前应用最广泛的全文索引之一。

（二）索引压缩的意义

全文检索技术的最主要的一个应用就是搜索引擎，尽管现在搜索引擎一般都是面向Web的，但现在越来越多的成熟搜索产品都开发了桌面搜索工具，并将本地文件的全文检索功能集成进去了，因此从这些角度看来，研究索引压缩算法以改进全文索引的效率是很有意义的。

（三）国内外关于压缩算法的研究

古代的中国文学界早就用“李杜”这样的缩略语指代李白、杜甫。时至今日，在各个学科领域或生活用语中，各形各色的简称出炉，这其实就是一种最简单的数据压缩。

术语“数据压缩”指减少表示给定信息量所需的数据量。数据时传递信息的手段，对相同数量的信息可以以不同数量的数据表示。严格意义上的数据压缩起源于人们对概率的认识。当我们对文字信息进行编码时，如果为出现概率较高的字母赋予较短的编码，为出现概率较低的字母赋予较长的编码，总的编码长度就能缩短不少。远在计算机出现之前，著名的Morse电码就已经成功地实践了这一准则。

迄今，数据压缩在商业程序中实现并被应用在许多技术领域。从信息熵到算术编码，从犹太人到Win RAR，从JPEG到MP3，数据压缩技术的发展史就像是一个写满了“创新”和“突破”的卷轴。

二、索引技术

信息无节制地膨胀，利用压缩技术可以节省大量的磁盘空间。但是，应该如何组织信息，以便有效地进行查询并能迅速提取相关的数据部分？简单压缩技术不能解决这样的问题，因此要引进索引技术。

（一）全文索引技术

目前主流的全文索引方法有倒排索引、署名文件、位图和Pat数组等，它们都各有优缺点，倒排索引模型空间效率较差、检索效率较低、创建过程烦琐；Pat数组无论是创建过程，还是检索过程都严重依赖原文本。此外，有人还提出了一些新的全文索引模型，它们在一定程度上解决上述问题，但就目前来说倒排索引模型的综合性能较好，且应用也比较为成熟。

（二）倒排索引及其构造

倒排索引（Inverted index）是从书目索引中受启发而派生出来的，倒排索引由一系列“单词-指针”对组成。单词实际上是索引的查找键，包括文本集中出现的所有单词（除无用词外）。指针是该单词在文本集中出现的所有位置。因此，从倒排索引可以很快得到任一单词出现在文本集中的哪些文档的哪些位置。

一个完整的倒排文件通常由两部分组成（如图1）：索引头：是一个一维数组，以字符内码为下标，记录各个字符的索引在索引体中的开始位置。索引体：图中的索引体示意图仅为方便理解，实际的索引体是示意图中的各行数据依次首尾连接形成的一维数据流。

图1中的每一行存放一个字符Ci（0

{Ti1，Ni1，[Oi1a，Oi1b…]}，{Ti2，Ni2，[Oi2a，Oi2b…]}，……，{Tim，Nim，[Oima，Oimb…]}其中Tij（0

图1.倒排文件结构图

三、倒排索引的压缩

压缩倒排文件有助于提高查询的吞吐量，因为读和解压一个已压缩的倒排索引很可能比读一个未压缩的倒排索引节省I/O时间。

（一）倒排索引压缩技术概述

一个倒排索引通常由字典表文件（dictionary file）和记录文件（postings file）

两部分组成。字典文件记录了文本集中出现的每个单词及其倒排列表在记录文件中的位置和大小等信息。一个单词对应的倒排列表可以表示为：

n表示单词在n个文档中出现，di为文档ID，fi为单词在文档di中出现的词频，是单词出现在某个文档中的位置列表。事实上，一个倒排列表可拆分为三部分：

1.一个文档ID序列（1≤i≤n）。

2.n个位置序列。

3.一个词频序列。

其中，第1和第2两个序列都是递增的整数序列。鉴于这种递增的特性，可以用间隔di+1-di和pik+1-pik来代替序列中的值，那么上边三个整数序列就转化为如下形式：

1.一个文档ID间隔序列。

2.n个位置间隔序列。

3.一个词频序列。

转化成间隔后，没有损失任何信息，因为初始倒排列表总是可以通过计算间隔的和还原，此外，还给序列的取值带来了两个影响：样本空间缩小、概率分布不均衡性扩大，因此预示着存在基于概率分布的高效压缩方法。目前己经提出了一些模型描述整数值的概率分布，适用于对以上任一序列的压缩。这些模型可以分成两类：

1.全局模型，所有序列使用相同的压缩参数。

2.局部模型，对于不同序列，其压缩参数是不同的，这个参数通常是单词的出现频率。局部模型的压缩效率一般高于全局模型，且在解码速度方面也很有优势，但实现更复杂。

（二）非参数化模型

非参数化模型是一种全局模型，其编码本身隐含了整数序列中数值的概率分布，这种隐含概率分布的特性使非参数化模型不但能用于静态整数序列的压缩，而且也适用于动态整数序列的压缩。非参数化模型依编码长度的可变性分为定长编码和变长编码两类。理想编码长度l（x）和数值的概率Pr（x）之间的香农关系（l（x）=-logPr（x））可以用来确定任一编码方法所隐含的概率分布。

1.定长编码。最简单的全局模型是定长编码，它的压缩效率有限。定长编码隐含的概率模型是：Pr（x）=1/N（N为整数序列的最大值），即整数值在数值空间上均匀分布，每个数值的编码长度均为l（x）=[logN]。

2.变长编码（Variable Byte Coding）。可变字节编码是一种变长编码，它是一种字节对齐的编码方式。将整数转化成二进制后，以7位为单位对其分段，每段前加一位成为8位，恰好用一个字节表示，这一位为0表示该段是最后一段，为1表示还有后续段。由于计算机多以字节为操作单位，字节对齐的编码往往更能发挥硬件的优势，所以可变字节编码的压缩和解压速度都较快。

3.一元编码（Unary Coding）。一元编码也属于变长编码，它将一个整数x编码成x-1个1位，其后紧跟一个0位，如3的编码为110，因此对值为x的整数，其编码就需要x位，编码长度l（x）=x。一元编码倾向于值很小的整数，但这种倾向太极端了。一元编码易于编码和解码。

4.γ编码（Gamma Coding）。γ编码可表示为：对于整数x，将其编码为前后两部分，前缀部分值为1+[logx]，用一元编码表示，需1+[logx]位；后缀部分值为x-2[logx]，用定长编码表示，需1+[logx]位，所以编码长度l（x）=1+2[logx]。

5.δ编码（Delta Coding）。进一步的发展是δ编码，其编码的前缀部分采用γ编码，而不是一元编码，后缀部分保持不变。对于较小的值，δ编码比γ编码长，但随着值的增大，情况就相反了。δ编码同γ编码一样易于编码和解码。

（三）分析评价

对于以上列出的种种压缩编码方法，可以从是否支持动态更新、压缩率、解压速度三方面来评价它们。

如果压缩后的索引在动态更新时，必须先解压才能调整索引，最后还要重新压缩，那么我们认为这种压缩的动态性很差，或者说，这种压缩是不支持动态性的。能支持动态整数序列的只有非参数化模型中列出的编码方法，主要有：δ编码、γ编码、可变字节编码。其中可变字节编码的压缩率较低，但解压时间和压缩时间都有压倒性的优势，因为它是字节对齐的编码，能充分的发挥硬件的速度。γ编码只适合压缩很小的整数，但换做大整数就得不偿失了。δ编码在表示小数值时比γ编码长，但对于较大的数情况就相反了。总的来说δ编码无论是解压速度还是压缩率都优于γ编码。

参考文献：

[1]朱虹,吴林.倒排索引压缩及在RDBMS全文检索中的实现[J].华中科技大学学报,2005,4

[2]邓攀,刘功申.一种高效的倒排索引存储结构[J].计算机工程与应用,2008,31

[3]刘兴宇.基于倒排索引的全文检索技术研究[J].2004,5:13-21

[4]骆新,陈睿.数据压缩实用技术[M].学苑出版社,1993

[5]林晶.全文检索模型的检索性能研究[J].电脑知识与技术,2010,4