基于多级指引索引的高效技术

摘要介绍了搜索引擎中基于多级指引索引的高效技术。包括索引压缩，置入文件阀值的方法。其中索引压缩介绍了字节对齐压缩、Elias gamma编码、Elias delta编码、Golomb编码、二元插值编码，并对其压缩效率，解压速度以及相对性能做了比较，叙述了在不同的情况下使用不同的编码，以便提高搜索效率。

关键词搜索引擎，多级指引索引，索引压缩，置入文件阀值

1 引言

搜索引擎（Search Engine）是随着Web信息的迅速增加，从1995年开始逐渐发展起来的技术。它是一种Web上的应用软件系统，以一定的策略在Web上发现和收集信息，对信息进行组织和处理，为用户提供Web信息查询服务。

一个搜索引擎由搜索器、索引器、检索器和用户接口等四个部分组成。其中索引器是一个搜索引擎的核心部分，因此索引的好坏直接影响到整个搜索引擎的质量。采用多级指引索引数据结构，尽管建立时需要付出一定代价，但是极大地提高了查询效率。本文在多级指引索引的基础上，介绍了提高效率的策略，其中包括多级指引索引的压缩，置入文件阈值（posting list threshold）的方法。

2 多级指引索引简介

图1 索引多级指引结构

多级指引索引是倒排索引的进化，既满足检索接口的词语-网页结构的需要，又考虑到庞大数据量结构组织的可行性。在词语集设置网页指针，将包含该词语的网页分块放置，减少存储相同词语的空间，根据词语标识符直接找到网页分块首位置，并为下一级指引提供前提；同一个词语在不同网页中出现的位置是变值，设置位置指针可以减少存储相同网页号的空间。

3 多级指引索引的压缩

多级指引索引压缩的目标是通过减少存储需求来降低输入输出。需要压缩的内容包括：词语列表中的词语名，每一个置入文件列表记录（entry）中的词频，每一个置入文件列表记录文档标识符。如果多级指引索引减少存储量，I/O读写置入列表（posting list）的时间就会减少，也就减少了内存、磁盘空间的占用。而一个没有被压缩的多级指引索引通常需要超过30％的空间来存储可压缩的数据，压缩后的数据只占原可压缩数据的10％－15％。但是存在的问题是，要对数据编码解码，增加了CPU时间耗用，考虑到I/O是系统的瓶颈，CPU与I/O之间不断扩大的性能差距，以时间换取空间是可行的。压缩不仅提高查询时的效率，还能加快创建索引，从各方面提升系统性能。

多级指引索引压缩的方法有字节对齐压缩，Elias gamma编码，Elias delta编码，Golomb编码，二元插值编码。

3.1 字节对齐压缩（Byte-Aligned）

字节对齐压缩[1]即对于一个给定的正整数，用一个或多个字节表示。表示该数首字节最左边的两位为长度指示器（length indicator），剩余位可以用来存储实际的数。文档ID不同，记为x，文档ID需要基于x的字节标识码，用前面所说的2bits写下长度指示器。写下x的二进制表示法，如下例：

0-63 00xxxxxx

64-(16K-1) 01xxxxxx xxxxxxxx

16K-(4M-1) 10xxxxxx xxxxxxxx xxxxxxxx

4M-(1G-1) 11xxxxxx xxxxxxxx xxxxxxxx xxxxxxxx

0 00000000

1 00000001

… …

63 00111111

64 01000000 01000000

65 01000000 01000001

字节对齐压缩的优点是容易编码和解码，位操作少，占用CPU时间少，缺点是对很小的整数压缩率低，每个整数最少用一个字节的空间。

3.2 Elias gamma（γ）编码

用γ方法表示文档ID的x的数值：表示2的次幂不超过x的最大值；一个0作为标记位（marker）；取x－余数二进制编码的位。用2 ＋1bits表示x的值，整数越小，则表示它值的位数就越少。大多数词频相对很小。

举个例子：

X=22

=4 24≤x25

4为2的次幂不超过22的最大值，所以得出4位一元码（unary）：1111

x- =22-24=6

用4位二进制数表示余数6：0110

最后的γ编码为：1111 0 0110

……

100

101

11000

11001

11,0,10

11,0,11

11111,0,11111

Elias Gamma Encoding(γ)总结：Gamma编码对于一元码很小的小整数是有效的，但是对于存储15个以上的整数效率就降低。

3.3 Elias Delta(δ)编码

Delta编码实际上是Gamma编码的延伸，其中整数x由两部分表示，1＋位由Gamma编码得出，之后标记位，接下来是x的二进制编码，其中x的最高位取反。Delta编码在表示小的整数的时候需要更多的空间存储，但对于压缩大整数是有效的。

3.4 Golomb编码

在Golomb编码中，整数x由两部分组成：商和余数。商q是由q= 得出的，余数r是由r=x-q*k-1计算出来的，这里的k是Golomb编码的基础。

如果rp,可被存储为位，反之则需要位，这里的p是一个中心点（pivot point）,是由－k得到的。

当rp时，Golomb编码是由q个0，一个1，r（用二进制表示）组成的；当r=p时，它是由q个0，一个1，r+p（用二进制表示）组成的。例如，k=3,整数9就可由00,1,11表示。

选择k对整个编码来讲是至关重要的。如果选的不合适，编码会变得很大而且解码也需要很长时间。这里可以考虑0.69*mean(a),a为整型数组。

值

…

商

…

余数

…

编码

100

101

110

111

0100

…

00111

000100

000101

000110

000111

…

通过比较，可以将这三种编码方式结合起来，Golomb编码用于文档编号，Gamma编码用于词频，Delta编码用于表示偏移量。

3.5 二元插值编码（Binary Interpolative coding）

二元插值编码利用相邻元素关系，应用于单调递增整数序列。如果在单调序列X1中，对于给定的整数xi，我们知道它的前一个整数是xi-1，后一个整数是xi+1, 由此我们知道存储xi所需要的最大位数。因为xi一定是在[xi-1＋1，xi+1－1]的范围内，所以需要的最大比特数为㏒2（xi+1－xi-1－2），编码需要前面的xi-1和xi+1，所以序列X2可由原始的X1的第二个数开始与X1序列对应，编码可以递归的方法。

进一步优化的方法是根据整数序列的平均游程长度（mean run length）,对位向量编码增加参数，称作局部模式。比较简单的一种方法是一个整数序列的个数是Pw，则它的平均游程长度是N/Pw，设b=0.69N/Pw，则取VG=(b,b,b,…)作压缩向量，前缀用一元编码，后缀是二进制编码（占用个位）。

在非全文索引当中，置入文件由文档号d和文档词频f组成，一个（d,f）平均可以用一个字节表示；单词t的置入文件可以根据t的IDF(Inverse Document Frequency)推算出来。

在全文索引中，单词出现的位置信息占据索引数据的主要部分，所以忽略文档号d和文档词频f。用变长压缩算法，单词出现的位置可以用少于8bit的位表示。设全部文档分词后的单词总数是TN，那么单词t总的出现次数是TN×TF(Term Frequency),它的置入文件的平均长度小于TN×TF字节。

3.6 多级指引索引压缩总结

根据文献[10]这几种压缩方法的压缩效率，解压速度以及相对性能的比较如表一所示：

图3

其中bpo－每个事件(occurrence)的比特数，bpr－每个记录的比特数，cpo－每个事件的周期数，cpr－每条记录的周期数。

我们可以假设1.4GB的多级指引文件列表通过最高效的方案（根据表1）被压缩，载入与解压的总代价

U≈T+EnA+dn,其中U是总时间，T是寻道时间（seek time），EnA是读需要的时间，dn是在内存中解压的时间，n是被读取的已压缩整数的量。

当n很大时，寻道时间就可以忽略，解压方案的性能P由读和解压时间来决定，P≈EA＋d；

当n趋于0的时候，性能完全取决于寻道时间，P≈T，P≈T＝（M-C）*R+C。

其中M表示测量的磁盘平均寻道时间，C是时钟周期固定寻道时间，R是压缩后的文件占压缩前的比率。

通过这个式子计算可得出当编码的整数数目很小的时候，二元插值编码性能最好，但是在速度上Golomb编码要超过其它的编码，当数目越来越大的时候，变长字节编码是最高效的。如图4示（其中横坐标表示记录数，纵坐标表示时钟周期数）。

图4几种压缩方式的比较

总结起来，在多级指引文件信息检索的过程中，处理长的多级指引文件是一个瓶颈，所以随着多级指引文件的增加而提高性能是一个好的解决方法。当多级指引文件小的时候，吞吐量由磁盘寻道时间决定，这个时间是与磁盘文件的长度相关的。减少文件的长度就会减少磁盘寻道的长度，选择基于最小化文件的压缩是最好的（例如Golomb）。随着文件长度的不断增加，磁盘寻道时间变得不那么重要，吞吐量与解压速度密切相关，所以变长字节编码最合适。如果磁盘空间需要额外的开销，推荐用Golomb压缩算法，使用Golomb算法可以使文件压缩的更小并且解压速度比gamma和delta算法更快。由Moffat和Zobel提出的使用Golomb算法表示文档号gamma算法表示词频的方法不如使用Golomb同时表示文档号和词频高效。

4 置入文件阈值（Posting list threshold）

置入文件阈值也称Topdocs，实际上是一种有损压缩（lossy compression）,就是说有的信息可能被丢弃。

这个算法的主要思想是，对多级指引索引I进行修剪，每一个词语t对应n个文档d，将那些权值A(d,t)很小并且对系统准确性影响很小的文档进行修剪，只保存权值最高的k篇（TOP K）。

算法描述：

为了评价Topdocs算法对精确率的影响，我们应用TREC(Text Retrieval Conference)的官方结果，下表说明了提交给TREC运行的准确度，结果显示P@10(threshold为10)在索引修剪之后基本上没什么变化，并且在平均精确率（MAP）上的差别是可以忽略的。

索引大小

修剪率(%)

MAP

P@10

3.53GB

0.211

0.362

0.05

3.15GB

10.7

0.207

0.362

0.1

2.9GB

17.8

0.205

0.360

TREC实验结果说明Topdocs方法有可能会丢掉索引中的一些重要信息，但是却可以和包括全部索引的查询效果一样好。用这种方法，网络搜索引擎通过转移那些对搜索结果没什么影响的数据来减少存储大量索引的负担，避免了检索整个置入文件，显着的提高了效率。实验结果证明可以减少40％的索引空间，并且可以达到相同的，只是在MAP上有点降低，同时也不适用于布尔查询。

5 总结

基于多级指引索引的两种不同的高效策略，实际上是有损压缩与无损压缩的包含的两个范畴。它们都是为了提高查询索引效率，也就是提高搜索引擎的检索效率。不管是那一种方法，都有其优点与弊端，但这两种不同的高效策略并不矛盾，可以综合应用，为进一步优化索引结构、提高效率服务。

参考文献

[1] Scholer F,Wiliams H,iannis J.Compression of inverted indexes for fast query evaluation [ J ].ACM Transactions on Information Systems,2002 (8):222 —229

P. Elias. Universal codeword sets and representations of the integers. IEEE Transactions on Information Theory,IT-21(2):194-203, Mar. 1975.

Grossman, Frieder, Goharian. Information Retrieval Compression. 2002.

Navarro G, Moura E, Neubert M. Adding compression to block addressing inverted indexes[J]. Information Retrieval, 2000, 3(1): 49-77

Vo Ngoc Anh and Alistair Moffat in the paper "Inverted Index Compression using Word-Aligned Binary Codes", Information Retrieval 8(1):151-166, January 2005

Moffat and L. Stuiver. Binary interpolative coding for effective index compression. Information Retrieval, 3(1):25–47, July 2000.

Peter Fenwick. Punctured Elias Codes for variable-length coding of the integers. 1996(12)

Jim Meany. Gomoly Coding Notes.2005(10)

David Carmel, Einat Amitay, Miki Herscovici, Yoelle Maarek, Yael Petruschka, Aya Soffer. Juru at TREC 10—Experiments with Index Pruning. IBM Labs, Haifa University, Haifa 31905, Israel.

[10] Aandrew Trotman. Compressing Inverted Files. Information Retrieval, 6, 5–19, 2003

[11] 涂新辉,何婷婷,罗景. 一种全文检索系统的设计与实现. 计算机工程.2005.9

[12] 闫宏飞. 可扩展Web信息搜集和检索系统. 北京大学网路与分布式实验室,2002(9)

学术参考网 · 手机版
https://m.lw881.com/

首页