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

魯嬌龍

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

關(guān)鍵詞：布爾檢索；倒排記錄表；集合交集；跳表

中圖分類號：TP312 文獻(xiàn)標(biāo)識碼：A 文章編號：1007-9416（2019）01-0050-02

0 引言

集合合并（set intersection）算法可被應(yīng)用于多個研究領(lǐng)域[1-2]。例如，在信息檢索系統(tǒng)中，搜索引擎利用倒排記錄表合并算法返回包含布爾查詢中所有關(guān)鍵詞的相關(guān)文檔集。

倒排索引是一種對文檔建模的高效結(jié)構(gòu)。它采用只標(biāo)記包含詞項(xiàng)的文檔的表示方法，解決了詞項(xiàng)-文檔矩陣（term-document matrix）存儲效率不高的問題[3]。

1 基于跳表的合并方法

使用跳表的合并方法可跳過一些不可能出現(xiàn)在結(jié)果集中的部分記錄，提升合并效率。在何處放置跳躍指針是影響跳表合并效率的一個關(guān)鍵因素。若指針數(shù)偏多，則意味著發(fā)生跳躍的機(jī)會更多，但可跳躍范圍（skip span）就較短。帶來的結(jié)果就是造成多次記錄間的比較，同時為了存儲指針地址又增加了存儲開銷。

假設(shè)p1，p2分別為指向兩個倒排表的指針，docID（）函數(shù)表示指針?biāo)赶虻奈臋n編號，skip（）函數(shù)表示指針的下一個跳躍位置。此時合并會遇到兩種情況：一種情況，docID（p1）

2 結(jié)合跳表和等間距偏移值的合并方法

傳統(tǒng)的基于跳表指針的倒排表合并沒有考慮表中記錄的整體分布情況。本文提出一種基于跳表指針并結(jié)合“等間距偏移值”的合并方法。

對于兩張倒排表P1、P2，首先分別計(jì)算出各自表中任意兩個連續(xù)記錄間的平均偏移值。記為Offset1和Offset2。計(jì)算公式為：Offset=（Max-Min）/（Listlength-1）。其中，Max、Min分別表示記錄的最大值和最小值。Listlength表示表長。以圖2中的兩張倒排表為例，經(jīng)計(jì)算得到表P1的偏移值Offset1=6，表P2的偏移值Offset2=18。

得到偏移值之后開始合并過程。利用指針p1，p2分別指向表中記錄，并通過向后移動p1，p2對記錄遍歷。假設(shè)比較完文檔ID為3的記錄并將其置于結(jié)果集Answer中。接著移動指針p1、p2，讓p1指向5、p2指向32，二者的差值Difference為27。而表P1的平均偏移值Offset1為6，因此讓指針p1向后移動5個位置，指向17。17仍小于32，所以接著移動指針p1，讓其指向48。48> 32，p1不能繼續(xù)向后移動。此時需將表P2中的32和表P1中位于17和48之間的記錄（即25、32）進(jìn)行比較。在25、32之間發(fā)現(xiàn)32滿足合并條件，因此32被放入結(jié)果集Answer中。上述合并過程并沒有用到P2表的間距偏移值Offset2。

3 時間復(fù)雜度分析

最好情況，一個表的記錄分布比較集中，而另一個表的記錄分布比較離散（如圖1中的表P1、P2的情形）。此時docID（p1）和docID（p2）的差值是若干個等間距偏移值之和，可跳過多個中間記錄。合并過程能夠在亞線性時間內(nèi)完成。最壞情況，表中記錄分布比較集中，此時如果docID（p1）和docID（p2）的差值小于一個Offset時，則指針每次只能跳躍一個位置，算法“退化”成需要逐個遍歷表中記錄的情況。此時可跳躍的中間記錄數(shù)減少，記錄的比較次數(shù)增多。合并過程需要線性時間。

4 結(jié)語

本文提出的倒排表合并方法充分利用倒排記錄有序的性質(zhì)。這種有序性可保證從較小記錄跳到較大記錄而忽略對中間記錄的比較。此方法以任意兩個連續(xù)記錄間的平均等間距偏移值作為跳躍基準(zhǔn)，發(fā)生跳躍的位置和傳統(tǒng)跳表不同。跳躍位置不固定，而是在合并過程中根據(jù)記錄的分布情況動態(tài)決定。和跳表一樣，本文提出的方法是實(shí)現(xiàn)跳過表中“相異”記錄的“求同”操作，因而它只適用于AND查詢，而不適用于OR查詢的情況。針對倒排表中記錄分布較離散的情況，本文方法能夠有效提升合并效率。

參考文獻(xiàn)

[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著.王斌譯.信息檢索導(dǎo)論[M].北京：人民郵電出版社，2010：26-28.

[4] Sanders，P.，Transier，F(xiàn).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