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

魯嬌龍

摘要：信息檢索旨在通過一系列的計算過程達到處理用戶的查詢請求，并返回相關的文檔列表以滿足其信息需求的目的。檢索任務依賴于具體的模型，檢索系統主要基于布爾、向量空間、概率等模型。本文在傳統跳表基礎上結合等間距偏移值策略提出了一種新的倒排表合并方法。這種方法對于倒排表中記錄分布較離散的情況具有很好的性能。

關鍵詞：布爾檢索；倒排記錄表；集合交集；跳表

中圖分類號：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