[發(fā)明專利]用于對倒排索引進(jìn)行壓縮的文檔序號重排方法及其系統(tǒng)

有效

• 申請?zhí)枺?/td>: 201210401317.7
• 申請日: 2012-10-19
• 公開（公告）號: CN102929988A
• 公開（公告）日: 2013-02-13
• 發(fā)明（設(shè)計(jì)）人: 史亮;王斌;衛(wèi)冰潔;張帥;張冠元
• 申請（專利權(quán)）人: 中國科學(xué)院計(jì)算技術(shù)研究所
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 北京律誠同業(yè)知識產(chǎn)權(quán)代理有限公司 11006
• 代理人: 祁建國;梁揮

技術(shù)領(lǐng)域

本發(fā)明涉及搜索引擎性能優(yōu)化，特別是涉及一種用于對倒排索引進(jìn)行壓縮的文檔序號重排方法及其系統(tǒng)。?

背景技術(shù)

倒排文件是搜索引擎中廣泛使用的一項(xiàng)索引技術(shù)，和其他索引格式如位圖，簽名文件相比，更適用大規(guī)模數(shù)據(jù)量的情況。搜索引擎處理查詢的過程主要可以分為以下4個步驟：1）對文檔建立倒排文件，2）用戶輸入查詢，3）掃描倒排文件，獲取候選文檔集，4）計(jì)算文檔評分并返回得分最高的前K個文檔。?

隨著文檔數(shù)量的增長，倒排文件的占用的存儲空間越來越大，導(dǎo)致查詢處理的過程也變得越來越緩慢。在文獻(xiàn)[1]中表明，通過對倒排索引進(jìn)行壓縮，不僅可以減少索引占用的存儲空間，而且可以提高搜索引擎處理查詢的效率。?

倒排索引的一般形式如下所示：?

詞項(xiàng)t通過對文檔分詞得到，被存放在字典中，詞項(xiàng)對應(yīng)的倒排表存放出現(xiàn)該詞項(xiàng)的文檔個數(shù)f_t和一個長度為f_t的文檔序號記錄表。如果把倒排表中的文檔序號按照升序排列，則可以使用d-gap表示倒排文件，因?yàn)樾蛱栔g的間距（d-gap）要遠(yuǎn)小于原始文檔序號，更小的數(shù)值意味著可以采用更短的編碼表示，從而減少倒排索引占用的磁盤空間。d-gap倒排索引的具體形式如下所示：t→＜f_t;d₁,d₂-d₁,…,d_k-d_k-1＞?

其中，d₁,d₂，…，d_k是按升序排列的長度為f_t的文檔序號記錄表，d_k-1小于d_k。?

為了對倒排索引進(jìn)行壓縮，一種方法是在給定文檔序號的前提下，研究壓縮率更高的編碼算法；另一種方法就是在文獻(xiàn)[2]中提出的對文檔序號進(jìn)行重排的方法。該方法通過優(yōu)化倒排索引中d-gap的分布達(dá)到進(jìn)一步提高索引壓縮率的目的，具體來說就是對已經(jīng)分配好的文檔序號進(jìn)行重新排列。比如有N篇文檔，默認(rèn)的文檔序號分配方式就是根據(jù)文檔加入倒排索引的順序，依次分?配序號1、2、……、N，而文檔序號重排方法則是根據(jù)文檔的特點(diǎn)，對文檔序號進(jìn)行重新分配，如圖5所示。?

在圖5中，原始文檔序號為1的重排后映射到K-1，2映射到1，依次類推。文檔序號重排是從另一個角度對倒排索引進(jìn)行壓縮，配合高效的索引壓縮編碼算法，可以達(dá)到最優(yōu)的索引壓縮率。?

文檔序號重排已經(jīng)在文獻(xiàn)[3]中被證明是一個NP問題，該問題優(yōu)化的目標(biāo)是找到一個所有文檔的最優(yōu)排列，使得在該排列下，倒排索引能夠達(dá)到最優(yōu)的壓縮率。采用窮舉的方法，其算法復(fù)雜度為O(n!)。?

目前已有的方法都是采用近似算法，主要有基于文檔聚類的方法、基于URL（統(tǒng)一資源定位符）排序的方法以及目前效果最好的基于TSP（旅行商問題）的方法。?

基于聚類的方法首先對所有的文檔建立文檔相似度圖，相似度采用文檔之間的余弦相似度度量，然后遞歸將原始文檔相似度圖切分成一個個子圖，直到每個子圖僅包含一個文檔。最后對切分生成的樹進(jìn)行深度遍歷，文檔序號按照深度遍歷的順序進(jìn)行分配。?

基于URL排序的方法僅適用于包含URL信息的文檔，具體做法是對URL按照字典序排序，文檔序號即按照其相應(yīng)的URL順序進(jìn)行分配。?

基于TSP的方法把文檔序號重排問題近似為TSP問題，主要思路是首先計(jì)算文檔之間的相似度（如余弦相似度、共現(xiàn)的詞項(xiàng)數(shù)等相似度計(jì)算方法），構(gòu)建文檔相似度無向圖，然后利用貪心算法從無向圖中找出最優(yōu)遍歷路徑，最后根據(jù)文檔遍歷的順序，重新分配文檔序號。貪心算法的目標(biāo)是最大化1-gap的數(shù)目，具體采用的貪心策略是：每一步都選擇和當(dāng)前節(jié)點(diǎn)（文檔）相似度最高?的節(jié)點(diǎn)作為當(dāng)前遍歷路徑中的下一個節(jié)點(diǎn)。利用該貪心策略，本方法能產(chǎn)生盡可能多的1-gap，從而達(dá)到最小化d-gap平均值的目的。?

基于TSP的方法在大部分情況下的壓縮比率都要優(yōu)于基于URL和基于聚類的方法，但是由于其算法復(fù)雜度較高，僅適用于小規(guī)模的數(shù)據(jù)集；基于URL的方法壓縮比率稍差，但是算法復(fù)雜度較低，可以很方便地?cái)U(kuò)展到大規(guī)模數(shù)據(jù)集；該方法的一個主要缺陷是文檔必須帶有URL信息，限制了該方法的使用范圍。基于聚類的方法由于復(fù)雜度較高，壓縮比率也不如基于TSP的方法，所以應(yīng)用并不廣泛。?