一种基于跳表和等间距偏移值的倒排表快速合并方法

鲁娇龙

摘要：信息检索旨在通过一系列的计算过程达到处理用户的查询请求，并返回相关的文档列表以满足其信息需求的目的。检索任务依赖于具体的模型，检索系统主要基于布尔、向量空间、概率等模型。本文在传统跳表基础上结合等间距偏移值策略提出了一种新的倒排表合并方法。这种方法对于倒排表中记录分布较离散的情况具有很好的性能。

关键词：布尔检索；倒排记录表；集合交集；跳表

中图分类号：TP312 文献标识码：A 文章编号：1007-9416（2019）01-0050-02

0 引言

集合合并（set intersection）算法可被应用于多个研究领域[1-2]。例如，在信息检索系统中，搜索引擎利用倒排记录表合并算法返回包含布尔查询中所有关键词的相关文档集。

倒排索引是一种对文档建模的高效结构。它采用只标记包含词项的文档的表示方法，解决了词项-文档矩阵（term-document matrix）存储效率不高的问题[3]。

1 基于跳表的合并方法

使用跳表的合并方法可跳過一些不可能出现在结果集中的部分记录，提升合并效率。在何处放置跳跃指针是影响跳表合并效率的一个关键因素。若指针数偏多，则意味着发生跳跃的机会更多，但可跳跃范围（skip span）就较短。带来的结果就是造成多次记录间的比较，同时为了存储指针地址又增加了存储开销。

假设p1，p2分别为指向两个倒排表的指针，docID（）函数表示指针所指向的文档编号，skip（）函数表示指针的下一个跳跃位置。此时合并会遇到两种情况：一种情况，docID（p1）

2 结合跳表和等间距偏移值的合并方法

传统的基于跳表指针的倒排表合并没有考虑表中记录的整体分布情况。本文提出一种基于跳表指针并结合“等间距偏移值”的合并方法。

对于两张倒排表P1、P2，首先分别计算出各自表中任意两个连续记录间的平均偏移值。记为Offset1和Offset2。计算公式为：Offset=（Max-Min）/（Listlength-1）。其中，Max、Min分别表示记录的最大值和最小值。Listlength表示表长。以图2中的两张倒排表为例，经计算得到表P1的偏移值Offset1=6，表P2的偏移值Offset2=18。

得到偏移值之后开始合并过程。利用指针p1，p2分别指向表中记录，并通过向后移动p1，p2对记录遍历。假设比较完文档ID为3的记录并将其置于结果集Answer中。接着移动指针p1、p2，让p1指向5、p2指向32，二者的差值Difference为27。而表P1的平均偏移值Offset1为6，因此让指针p1向后移动5个位置，指向17。17仍小于32，所以接着移动指针p1，让其指向48。48> 32，p1不能继续向后移动。此时需将表P2中的32和表P1中位于17和48之间的记录（即25、32）进行比较。在25、32之间发现32满足合并条件，因此32被放入结果集Answer中。上述合并过程并没有用到P2表的间距偏移值Offset2。

3 时间复杂度分析

最好情况，一个表的记录分布比较集中，而另一个表的记录分布比较离散（如图1中的表P1、P2的情形）。此时docID（p1）和docID（p2）的差值是若干个等间距偏移值之和，可跳过多个中间记录。合并过程能够在亚线性时间内完成。最坏情况，表中记录分布比较集中，此时如果docID（p1）和docID（p2）的差值小于一个Offset时，则指针每次只能跳跃一个位置，算法“退化”成需要逐个遍历表中记录的情况。此时可跳跃的中间记录数减少，记录的比较次数增多。合并过程需要线性时间。

4 结语

本文提出的倒排表合并方法充分利用倒排记录有序的性质。这种有序性可保证从较小记录跳到较大记录而忽略对中间记录的比较。此方法以任意两个连续记录间的平均等间距偏移值作为跳跃基准，发生跳跃的位置和传统跳表不同。跳跃位置不固定，而是在合并过程中根据记录的分布情况动态决定。和跳表一样，本文提出的方法是实现跳过表中“相异”记录的“求同”操作，因而它只适用于AND查询，而不适用于OR查询的情况。针对倒排表中记录分布较离散的情况，本文方法能够有效提升合并效率。

参考文献

[1] Baeza-Yates，R.（2004）.A fast set intersection algorithm for sorted sequences[J].Proceedings of Combinatorial Pattern Matching（pp.400-408）. Springer BerlinHeidelberg.

[2] Tsirogiannis，D.，Guha，S.，&Koudas，N.（2009）.Improvingthe performance of listintersection[J].Proceedings of the VLDB Endowment，2（1），838-849.

[3] CD.Manning，PRaghavan，HSchütze著.王斌译.信息检索导论[M].北京：人民邮电出版社，2010：26-28.

[4] Sanders，P.，Transier，F.Intersection in integer inverted indices[J].ALENEX2007，pp.71-83.

Abstract：The purpose of Information Retrieval is aimed at processing the users queries and returning them a list of relevant documents through a series of computerized processes to meet their information needs.The retrieval task depends on specific models， and the retrieval system is mainly based on Boolean， vector space， probability and other models. This paper proposed aninverted posting lists set intersection approach in Boolean model based on basic skip list and equidistant offset strategy.This approach has a good performance when the postings are discretelydistributed.

Key words：Boolean retrieval； inverted posting list； set intersection； skip list