史 亮，張 鴻，劉欣然，王 勇，王 斌

(1. 國家計算機網(wǎng)絡(luò)應(yīng)急技術(shù)處理協(xié)調(diào)中心，北京 100029； 2. 中國科學院 信息工程研究所，北京 100093)

?

倒排索引中的文檔序號重排技術(shù)綜述

史 亮1，張 鴻1，劉欣然1，王 勇1，王 斌2

(1. 國家計算機網(wǎng)絡(luò)應(yīng)急技術(shù)處理協(xié)調(diào)中心，北京 100029； 2. 中國科學院 信息工程研究所，北京 100093)

倒排索引作為文本搜索的核心索引技術(shù)，廣泛應(yīng)用于搜索引擎、桌面搜索和數(shù)字圖書館領(lǐng)域。倒排索引由字典和對應(yīng)的倒排表組成，倒排表一般采用差值存儲和整數(shù)編碼進行壓縮。研究表明，當?shù)古疟砭哂休^好的局部連續(xù)性時，上述方法能夠獲得很高的壓縮率。整數(shù)編碼研究通過不斷改進編碼算法來充分利用倒排表的局部連續(xù)性特征，而文檔序號重排正是一種對文檔序號重新排列來產(chǎn)生局部連續(xù)性的技術(shù)。通過文檔序號重排，索引壓縮率得到顯著提高。該文主要介紹近年來文檔序號重排技術(shù)取得的研究成果： 首先介紹索引壓縮的基本原理，然后詳細介紹文檔序號重排技術(shù)，包括分析、對比各個方法的優(yōu)劣；最后對文檔序號重排技術(shù)進行總結(jié)、整理和展望。

搜索引擎；性能優(yōu)化；索引壓縮；文檔序號重排；局部連續(xù)性

1 引言

隨著互聯(lián)網(wǎng)的快速發(fā)展，搜索引擎已經(jīng)成為人們獲取信息的主要手段。在搜索引擎中，倒排索引被證明是最合適并廣泛使用的索引格式[1]。隨著網(wǎng)絡(luò)數(shù)據(jù)和用戶規(guī)模的不斷增長[2-3]，索引存儲和查詢處理都面臨前所未有的挑戰(zhàn)。

根據(jù)倒排索引的特點，索引壓縮(Index Compression)采用文檔序號重排技術(shù)和整數(shù)編碼算法對倒排索引進行壓縮。通過索引壓縮，可以把倒排索引的體積壓縮到原始文檔集合的15%～25%左右。索引壓縮的優(yōu)勢主要體現(xiàn)在以下方面： 1)減少倒排索引占用的磁盤空間，節(jié)約存儲成本；2)通過壓縮，降低了索引從磁盤傳輸至內(nèi)存過程中的延遲，提高了查詢處理效率；3)在有限容量的緩存中存儲更多的索引，提高查詢處理過程中的緩存命中率[4]。

本文的目標是介紹索引壓縮中文檔序號重排技術(shù)的研究進展。文檔序號重排是索引壓縮的一項重要技術(shù)。研究表明，倒排表中的局部連續(xù)性(局部連續(xù)性是指具有連續(xù)文檔序號的文檔在倒排表中多次連續(xù)出現(xiàn))能夠有效地提高索引壓縮率。

倒排索引一般由字典和倒排表組成，和倒排表相比，字典只占非常小的空間，所以如果不做特別說明，索引壓縮一般是指倒排表的壓縮。倒排表采用差值存儲， 然后使用整數(shù)編碼算法進行壓縮。整數(shù)

編碼算法主要是在不改變初始文檔序號分布的前提下，通過改進算法提高索引壓縮率。目前主流的編碼算法已經(jīng)能夠兼顧壓縮、解壓速度和壓縮率，并且可以根據(jù)實際需求選擇相應(yīng)的編碼算法。但是受限于文檔序號的初始分布，倒排表中的局部連續(xù)性往往較差，僅通過優(yōu)化編碼算法來提高索引壓縮率的空間已經(jīng)不是很大。

文檔序號重排是一種對倒排索引中文檔序號重新分配的技術(shù)。相比于初始文檔序號分布，重排后的文檔序號具有更好的局部連續(xù)性，進一步提高了索引壓縮率。該方法提出后，在搜索引擎中得到了廣泛應(yīng)用，在研究人員的努力下，其可用性和擴展性都得到了有效的改進。

本文的組織結(jié)構(gòu)如下： 第2節(jié)介紹了索引壓縮的基本原理，第3節(jié)介紹了文檔序號重排技術(shù)的基本原理和方法，第4、5、6節(jié)從三個類別整理和總結(jié)了近年來文檔序號重排技術(shù)的研究工作，第7節(jié)對本文進行了總結(jié)和展望。

2 索引壓縮

倒排表的基本形式如式(1)所示：

(1)

詞項ti通過文檔分詞得到，存放在字典中，倒排表存放出現(xiàn)該詞項的文檔個數(shù)fti和長度為fti的文檔序號記錄表，這里暫不考慮詞項ti在每個文檔中出現(xiàn)的頻率和位置信息。

觀察發(fā)現(xiàn)，如果把倒排表中的文檔序號升序排列，然后僅存儲文檔序號之間的差值(簡稱d-gap)，可以有效減少存儲倒排表所需空間。這是因為d-gap要遠小于原始文檔序號，尤其隨著文檔數(shù)目的增長文檔序號越來越大時更是如此。更小的數(shù)值意味著可以采用更短的編碼表示，所以在實際系統(tǒng)中文檔序號往往采用d-gap表示，又稱倒排表的d-gap形式，如式(2)所示。

(2)

對d-gap壓縮，本質(zhì)上是對整數(shù)進行壓縮。所以當把倒排表按照d-gap形式存儲后，便可以采用整數(shù)編碼算法作進一步處理。按照碼長是否可變，整數(shù)編碼可以分為定長編碼和變長編碼。定長編碼是指每個整數(shù)由固定長度的碼字表示，如INT32、INT64等。變長編碼會根據(jù)整數(shù)的大小，選擇不同的碼長。變長編碼又分為變長比特編碼和變長字節(jié)編碼。變長比特編碼包括Gamma編碼[5]、Delta編碼[5]、Rice編碼[6]、Simpe9編碼[7]、PForDelta編碼[8]、IPC編碼[9]等，特點是在比特粒度上長度可變；變長字節(jié)編碼主要指VByte編碼[10]，特點是在字節(jié)粒度上長度可變。相比于變長字節(jié)編碼，變長比特編碼的優(yōu)點是能夠獲得更高的壓縮率，但是編碼和解碼過程都需要大量計算，速度更慢。

舉例來說，假如要對1 000篇文檔建立倒排索引，其中詞項t在4篇文檔中出現(xiàn)，文檔序號分別是200、407、412和855，文檔序號采用Gamma編碼。表1將倒排表的基本形式和d-gap形式進行了對比，包括存儲方式和所需的編碼長度。

表1 倒排表的基本形式和d-gap形式所需編碼長度對比

整數(shù)X的Gamma編碼需要(2×log2X+1)比特，所以表1中倒排表基本形式共需要68比特，d-gap形式共需要52比特。從這個簡單的例子可以看出，使用差值存儲，d-gap形式總共節(jié)約了16比特。在實際的倒排索引中，d-gap形式帶來的好處更加明顯。

3 文檔序號重排技術(shù)

倒排表具有較好的局部連續(xù)性時，差值存儲能夠獲得更高的壓縮率，這是因為好的局部連續(xù)性意味著倒排表中存在更多數(shù)值較小的d-gap。通過前面的介紹可以知道，更小的數(shù)值可以采用更短的編碼表示。但在實際情況中，受限于文檔序號的分布，倒排表的局部連續(xù)性往往不是很好。

近年來，研究人員提出了文檔序號重排技術(shù)(DocumentIdentifierReassignment)，按照文檔之間的相似度，對文檔序號重新分配。經(jīng)過文檔重排，顯著提高了倒排表的局部連續(xù)性。實驗表明，文檔序號重排技術(shù)不僅提高了索引壓縮率[11]，而且優(yōu)化了查詢處理的性能[12]。此外，通過對文檔序號進行重排，還能夠更好地管理新加入的文檔[13]。

(3)

以表1中的倒排表為例，對其進行文檔序號重排后得到的倒排表及其d-gap形式如表2所示，采用Gamma編碼。在本例中，通過將原始的文檔序號200,407,421,855映射到10,13,14,和201，編碼長度由原來的52比特減少為26比特。

表2的例子簡單演示了文檔序號重排技術(shù)對單個倒排表的影響。實際情況中，對單個倒排表中的文檔序號重排將會影響全局的d-gap分布，所以文檔序號重排的過程是一個求全局最優(yōu)解的過程。

表2 倒排索引的基本形式和重排后d-gap形式編碼長度對比

最簡單的文檔序號重排方法是對所有N篇文檔序號進行全排列，然后找出使總的編碼長度之和最小的排列，時間復雜度為O(N!)。該方法能夠有效解決文檔序號重排問題，但僅適用于小規(guī)模數(shù)據(jù)集。RoiBlanco等人指出[14]，該問題的求解類似于PSP(PatternSequencingProblems，模式序列問題)，屬于NP(Non-deterministicPolynomial，非確定性多項式)問題，暫無確定性解法，只能通過近似的方法求解。

目前解決該問題的基本做法是將連續(xù)的文檔序號分配給相似文檔，這樣做是因為相似度高的文檔在倒排表中的共現(xiàn)頻率也高，可以產(chǎn)生很好的局部連續(xù)性，增加倒排表中小的d-gap出現(xiàn)的頻率。

所以文檔序號重排問題可以分為三個子問題： 1)如何定義文檔相似度；2)如何尋找相似文檔；3)如何重新分配文檔序號。其中第二個子問題可以認為是最核心的問題。

本文根據(jù)尋找相似文檔方法的不同，把相關(guān)工作分為三類并分成三節(jié)進行詳細介紹。第4節(jié)主要介紹基于聚類的方法，第5節(jié)介紹基于TSP(TravelingSalesmanProblem，旅行商問題)的方法，第6節(jié)介紹基于排序的方法。

4 基于聚類的方法

基于聚類方法的特點是通過對文檔集合進行聚類，尋找相似文檔。根據(jù)聚類算法的區(qū)別，可以分為自頂向下和自底向上的方法。

4.1 自頂向下的方法

自頂向下的方法主要包括B&B、TransactionalB&B和Bisecting算法，這些算法的基本思想是將原始文檔集合看成一個整體，然后自頂向下遞歸地對文檔集合進行聚類，每一次聚類將相似文檔劃分到一個類別中。聚類的同時伴隨著調(diào)整類別之間先后順序的過程。

(1)B&B算法

Blandford和Blelloch(以下簡稱B&B)第一次提出利用聚類算法對文檔序號進行重新排列的方法，算法的基本步驟如下(預先已對文檔集合建立倒排索引)。

1) 選擇中心點： 首先對給定的文檔集合進行抽樣，忽略文檔中的高頻詞，根據(jù)文檔之間的余弦相似度計算得到DSG(DocumentSimilarityGraph，文檔相似圖)，然后調(diào)用Metis[16]圖切分算法將DSG劃分為兩個子集，這兩個子集的中心向量作為新的聚類中心；

2) 劃分剩余文檔: 剩余未被抽樣選中的文檔，根據(jù)到兩個聚類中心的余弦相似度，劃分到相應(yīng)的文檔集合中；

3) 文檔集合排序： 對兩個子集進行排序；假設(shè)將文檔集合S劃分為子集I1和I2，令I(lǐng)L為節(jié)點S左祖先的左孩子節(jié)點，IR為節(jié)點S右祖先節(jié)點的右孩子節(jié)點。之所以要對子集I1和I2排序，是因為需要考慮I1、I2和其前驅(qū)文檔集合IL及后繼文檔集合IR的相似度，通過排序，可以將相似度更高的文檔集合放在一起；

4) 遞歸聚類： 遞歸調(diào)用上述過程，直到每個文檔子集合只包含單個文檔為止。

通過對文檔集合自頂向下遞歸聚類得到一個層次聚類樹，樹的葉子節(jié)點是單個文檔，然后從左至右遍歷樹中所有的葉子節(jié)點，最后按照遍歷的次序?qū)ξ臋n分配新的文檔序號。

對文檔抽樣處理，可以降低DSG的規(guī)模，減少算法執(zhí)行的時間；忽略高頻詞是因為高頻詞對應(yīng)倒排表的d-gap已經(jīng)較小，通過文檔序號重排所得提升有限，相比整體優(yōu)化效果可以忽略不計，而且高頻詞的存在影響了文檔相似度的計算。

(2)TransactionalB&B算法

B&B算法在對文檔序號進行重排之前，需要預先對文檔建立倒排索引，增加了算法的額外開銷。TransactionalB&B[16]算法對B&B算法進行了改進，跳過了建立倒排索引的步驟，并且在中心點選擇和文檔集合排序上進行了改進，其基本步驟如下：

1) 選擇中心點： 類似于B&B算法，但是在計算DSG時使用Jaccard相似度；因為沒有預先建立倒排索引，所以沒有過濾高頻詞；

2) 劃分剩余文檔： 根據(jù)Jaccard相似度劃分未被抽樣選中的剩余文檔；

3) 遞歸聚類： 和B&B算法不同，該方法先進行遞歸劃分至葉節(jié)點，然后對文檔集合排序。這樣做的結(jié)果是先得到一個層次聚類樹，然后再自底向上對文檔集合排序；

4) 文檔集合排序： 假設(shè)對文檔子集I1和I2排序，如果I1中最后一個文檔和I2中第一個文檔的Jaccard相似度大于I1中第一個文檔和I2中最后一個文檔的相似度，則將保持I1和I2的次序(I1在I2之前)，否則交換兩者次序。

最后從左至右遍歷層次聚類樹的葉子節(jié)點，為每個文檔分配新的文檔序號。

(3)Bisecting算法

Bisecting[16]方法在TransactionalB&B算法的基礎(chǔ)上，進行了進一步簡化。在選擇中心點時，隨機地挑選兩個文檔作為聚類中心，而不像B&B和TransactionalB&B方法一樣，使用圖切分算法選擇聚類中心，從而省去了計算DSG和圖切分的步驟，降低了算法的復雜度。當然，這樣做犧牲了聚類的準確性，影響了文檔序號重排后最終的索引壓縮效果。

4.2 自底向上的方法

不同于自頂向下劃分文檔集集合進行聚類的方法，自底向上的方法從原始文檔集合開始，根據(jù)文檔與聚類中心的相似度，依次將每個文檔劃分到距離最近的類別中，最后得到k個文檔聚類。自底向上的方法主要包括k-means-like算法和k-scan算法。

(1)k-means-like算法

基本的k-means算法是從文檔集合中選出k個聚類中心點，然后將剩余文檔按照到各個聚類中心點的距離，聚到距離最近的類別。待所有文檔分配完成后，重新計算k個聚類的中心點，然后重復上述步驟，直到k個中心點不再變化或者達到給定的收斂條件為止。

k-means算法由于復雜度的原因，在文檔序號重排問題中并不適用。Silvestri在文獻[16]中提出了一個輕量級的k-means-like聚類算法，該算法在k-means算法的基礎(chǔ)上進行了簡化，只進行一次中心點選擇和文檔劃分。算法的具體步驟如下：

1) 選擇中心點： 使用Buckshot[17]方法，選取k個聚類中心點；

2) 劃分剩余文檔： 根據(jù)Jaccard相似度，將剩余文檔分配到k個類別中；

(2)k-scan算法

k-scan[16, 18]算法是另一種輕量級聚類算法，假設(shè)對N篇文檔進行序號重排，共有k個類別，具體步驟如下。

1) 文檔預排序： 對N篇文檔，按照文檔長度降序排列；

2) 選擇中心點： 每次選擇剩余文檔集合中長度最長的文檔作為聚類中心；

3) 劃分剩余文檔： 根據(jù)Jaccard相似度，從剩余文檔集合中選擇(N/k-1)個和聚類中心相似度最高的文檔添加到該類別；

4) 重復第2)、3)步k次，得到k個文檔聚類，每個類別中包含N/k個文檔。

在k-means-like算法和k-scan算法運行完成后，得到k個文檔類別，最后根據(jù)k個中心點產(chǎn)生的順序和以及每個類別里文檔被添加的順序，給文檔分配新的序號。

4.3 方法小結(jié)

本節(jié)介紹的方法主要是通過聚類算法，將文檔集合中相似度比較高的文檔添加到同一個類別中，然后給同一個類別中的文檔分配連續(xù)的文檔序號，同時也考慮了類別之間的相似度?；诰垲惙椒ǖ膬?yōu)點是能夠有效地在倒排表中產(chǎn)生局部連續(xù)性，提高了索引壓縮率；缺點是算法復雜度較高，B&B算法構(gòu)建、劃分DSG的空間和時間復雜度均為O(m2)，其中m為抽樣集合的大??；建立層次聚類樹的空間、時間復雜度為O(nlogn)。其他基于聚類的算法和B&B相比，在時間復雜度和空間復雜度上進行了優(yōu)化，但均以犧牲聚類的準確性為代價，最后實際的壓縮效果也差一些。

5 基于TSP的方法

TSP又稱旅行商問題，是一個最優(yōu)化問題： 有n個城市，一個旅行商要從某一個城市出發(fā)，走遍所有的城市僅且一次，再回到他出發(fā)的城市，求最短路線。相關(guān)研究工作利用了TSP的思想來求解文檔序號重排問題。

5.1 基本的TSP的方法

Shieh等人首次提出了文檔序號重排問題轉(zhuǎn)化為TSP問題進行求解[19]。根據(jù)前面介紹，文檔序號重排過程就是尋找文檔集合中相似文檔的過程，如果把DSG中邊的權(quán)重定義為文檔之間的相似度，則文檔重排可以看作從一個文檔開始，遍歷所有的文檔僅且一次，再回到開始文檔，求相似度之和最大的路徑。找到這樣的路徑后，再按照路徑中文檔節(jié)點遍歷的順序，重新分配序號。在這里，相似度定義為兩個文檔之間共現(xiàn)詞項的個數(shù)。

TSP被證明是NP問題，Shieh等人分別采用了貪心算法和生成樹算法求解。貪心算法又包括Greedy-NN(NearestNeighbor)和Greedy-NA(NearestAddition)方法。Greedy-NN算法挑選路徑中下一個節(jié)點的策略是每次都選擇和當前路徑的最后一個節(jié)點相似度最大的節(jié)點，而Greedy-NA算法選擇下一個節(jié)點的策略是計算剩余節(jié)點和當前路徑上所有節(jié)點的相似度，然后選擇相似度最大的節(jié)點加入到當前路徑的末端。

生成樹算法的思路是首先找到DSG的一棵最大生成樹，然后使用廣度優(yōu)先(BFS)或者深度優(yōu)先(DFS)遍歷生成樹，得到遍歷所有文檔的一條路徑，然后依據(jù)路徑中節(jié)點出現(xiàn)的順序重新分配文檔序號。具體的最大生成樹算法可以采用Kruskal算法和Prim算法。

實驗結(jié)果表明，采用Greedy-NN算法進行文檔序號重排后的實驗結(jié)果要好于Greedy-NA算法和生成樹算法，也要優(yōu)于前面介紹的基于聚類的算法，但是該算法的缺點是時間復雜度和空間復雜度太高，不適合在大數(shù)據(jù)集上使用。

5.2 結(jié)合SVD的TSP方法

上述TSP算法的基本思想是從DSG中尋找最優(yōu)路徑，所以必須保存DSG，而隨著文檔數(shù)量的增長，DSG所需的存儲空間急劇膨脹，于是RioBlanco等人提出了利用SVD(SingularValueDecomposition，奇異值分解)對DSG進行降維的方法[20, 21]。

假設(shè)有一個t×d維詞項-文檔矩陣X，其中t代表詞項，d代表文檔。對該矩陣進行SVD分解，可以得到三個子矩陣，如式(4)所示。

(4)

(5)

則d×d維文檔-文檔矩陣DSG可以表示為式(6)。

(6)

(7)

經(jīng)過SVD分解后，文檔之間的相似度可以通過矩陣D和S計算得到，所以只需要保存d×k維的矩陣D和對角矩陣S的k個對角線元素即可，而不需要保存完整的d×d維文檔-文檔矩陣DSG。根據(jù)實際應(yīng)用的需求，k值可以取幾十到幾百，顯著降低了算法的空間復雜度。

另一個關(guān)于時間復雜度的優(yōu)化是把原始文檔集合分為c塊，在每一塊內(nèi)使用SVD+TSP，塊與塊之間的次序可以通過從每個塊中選取一個文檔，然后使用Greedy-NN算法決定。

實驗結(jié)果表明，當k=200時，可以在時間和文檔序號重排效果之間達到較好的平衡點。采用分塊的策略時，c=1表示不分塊，隨著c值增加，程序運行時間減少，序號重排后的壓縮效果也逐漸變差，可以根據(jù)實際需求選擇參數(shù)。

結(jié)合SVD的TSP方法通過降維和分塊，顯著降低了TSP求解的空間復雜度和時間復雜度，但是另一方面，由于SVD分解本身就是一項時間復雜度較高的步驟，所以總的來說，該方法適用范圍有限，在小規(guī)模的文檔集合上使用比較合適。

5.3 結(jié)合LSH的TSP方法

為了將基于TSP的文檔序號重排方法擴展到大規(guī)模數(shù)據(jù)集，Ding等人提出了結(jié)合LSH(LocalitySensitiveHash，局部敏感哈希)的TSP方法[22]，該方法基本思路是通過抽樣對原始的DSG進行簡化，每個節(jié)點僅保留k條鄰近邊(k?n)，即每個節(jié)點僅保留k個鄰居節(jié)點，在抽樣得到的稀疏圖上求解TSP。主要步驟如下：

1) 詞項抽樣： 掃描文檔集，使用Min-Hash[23]算法從每個文檔中選取s個詞項(s可以任意取值，這里設(shè)為100)；

2) 選擇最鄰近候選文檔： 使用LSH[24-25]算法為每個節(jié)點挑選k′>k個鄰近節(jié)點；

3) 過濾候選文檔： 計算每個節(jié)點和選出的k′個候選文檔的相似度，僅保留k個相似度最高的文檔；

4) 求解TSP： 使用Greedy-NN算法求解相似度之和最大的路徑。如果出現(xiàn)某個節(jié)點的k個鄰近節(jié)點都已在路徑中，導致無路可走的情況，則選擇剩余圖中權(quán)重最大的邊，將對應(yīng)節(jié)點加入路徑。

在計算兩個文檔di，dj相似度時，Ding等人實驗了多種方法，如表3所示。其中n為文檔個數(shù)，ft為詞項頻率。

表3 結(jié)合LSH的TSP方法使用的相似度計算方法

除了上面介紹的四種方法，Ding還提出，使用Greedy-NN求解TSP時，每一步都選擇和當前路徑的尾節(jié)點相似最高的文檔，這樣做的目的是最大化倒排表中1-gap的數(shù)目，但是卻忽略了其他數(shù)值的d-gap。

為了考慮其他數(shù)值d-gap的影響，定義詞項t對應(yīng)的倒排表中j-gap的權(quán)重為： 如果j

如圖1所示，假設(shè)候選文檔是有D1和D2，假設(shè)文檔D1包含詞項a和c，文檔D2包含詞項a、b和d，所以文檔D1對應(yīng)的d-gap權(quán)重之和為a、c對應(yīng)的倒排表中3-gap和4-gap的權(quán)重之和；文檔D2對應(yīng)的d-gap權(quán)重之和為詞項a、b和d對應(yīng)的倒排表中3-gap、5-gap和1-gap的權(quán)重之和。最后選擇權(quán)重之和最大的文檔作為路徑中的下一個節(jié)點。

圖1 文檔d-gap權(quán)重的計算(a, b, c, d表示詞項，橫線上的數(shù)字表示d-gap的數(shù)值)

實驗結(jié)果表明，結(jié)合LSH的方法可以有效地處理大規(guī)模數(shù)據(jù)，并且得到較好的壓縮效果。同時，在進行候選文檔選取時，考慮文檔d-gap權(quán)重影響的方法，其壓縮率要高于通過其他四種相似度選取候選文檔的方法。

5.4 方法小結(jié)

基于TSP的文檔序號重排技術(shù)被認為是目前比較好的方法，對索引壓縮率的提高也最明顯?；镜腡SP方法，其時間復雜度和空間復雜度均為O(n2)，性能最差，不太適合大規(guī)模數(shù)據(jù)，SVD方法通過矩陣分解將算法的空間復雜度降低到O(nk)(其中k為需要保留的矩陣維度)，但是時間復雜度沒有得到優(yōu)化。LSH方法通過局部敏感哈希將算法的空間和時間復雜度降低到O(nk)(其中k為抽樣的文檔數(shù))，使TSP算法能夠很好地處理大規(guī)模數(shù)據(jù)集，但是抽樣造成了精度損失，影響了最后的壓縮效果。

6 基于排序的方法

前面介紹的文檔序號重排方法，包括基于聚類的方法和基于TSP的方法，都是通過計算文檔之間相似度，然后尋找近鄰文檔，雖然通過降維或者抽樣可以降低整個過程的空間復雜度和時間復雜度，但是在大規(guī)模數(shù)據(jù)下，由于聚類、TSP本身的復雜性，算法實用性仍有一定限制。下面要介紹的算法采用排序的策略挖掘文檔之間的相似性，其時間復雜度和空間復雜度相比于前面介紹的方法，都得到了進一步降低。

6.1 基于URL排序(URLSORT)的方法

Silvestri提出了基于URL(UniformResourceLocator，統(tǒng)一資源定位器)字典序排序的文檔序號重排方法[26]。這樣做的依據(jù)是URL一般都有層次目錄結(jié)構(gòu)，內(nèi)容相似的文檔往往會被人為存放在名稱相同或者相似的目錄下。利用這個特征，在Web數(shù)據(jù)集上可以對每個文檔對應(yīng)的URL按照字典序排序，然后按照這個順序?qū)Ψ峙湫碌奈臋n序號。

實驗表明，通過該方法進行文檔序號重排的結(jié)果和基于聚類的方法的結(jié)果相當，而在時間和空間復雜度上，都得到了顯著的優(yōu)化。由于依賴于文檔的URL，該方法在桌面搜索、圖書搜索等領(lǐng)域有一定的局限性。

6.2 基于詞項排序(TERMSORT)的方法

Shi等人在文獻[27]中提出了基于詞項對文檔進行排序的方法，然后按照排序后的文檔次序，重新分配文檔序號。該方法的基本依據(jù)是如果兩篇文檔相似，那么其中包含的詞項重復的可能也比較大。如果按照詞項是否出現(xiàn)，對文檔進行排序，那么相似的文檔由于包含重復的詞項，排序后鄰近的概率會比較高。該方法就是使用基于排序的方式來挖掘文檔集合中的相似文檔。具體的步驟為：

1) 選擇對文檔排序時，詞項的比較順序： 作者在文中實驗了三種順序，分別是文檔頻率升序、降序和原始順序；

2) 按照第1)步確定的詞項順序，對文檔降序排列： 文檔大小的判斷的依據(jù)是如果文檔A包含詞項t而文檔B不包含，則文檔A> 文檔B；

3) 按照排序后的文檔，重新分配文檔序號。

實驗結(jié)果表明，當詞項按照文檔頻率降序排列時，該方法能夠獲得最好的結(jié)果，其索引壓縮率和基于TSP的方法基本持平，但是算法復雜度明顯優(yōu)于基于TSP的方法。

6.3 方法小結(jié)

本節(jié)介紹的方法通過排序?qū)ふ椅臋n集中的相似文檔，進而在倒排表中產(chǎn)生局部連續(xù)性。因為不需要計算文檔集合中兩兩文檔之間的相似度，基于排序的方法其算法復雜度要好于前面介紹的方法?；赨RL的方法由于依賴于文檔的URL屬性，應(yīng)用范圍具有一定的局限性?；谠~項排序的方法依賴于預先對詞項按照文檔頻率排序，所以在重排之前需要對文檔集合進行預處理，得到相應(yīng)的詞項信息。

7 總結(jié)

本文總結(jié)了目前常見的文檔序號重排方法。當?shù)古疟聿捎貌钪荡鎯Σ⑹褂谜麛?shù)編碼進行壓縮時，通過對文檔序號進行重排，可以有效地在倒排表中產(chǎn)生局部連續(xù)性，顯著提高索引壓縮率。

表4概括和總結(jié)了本文介紹的文檔序號重排方法，包括每種方法的步驟、時間復雜度和空間復雜度。

這里需要注意的是，在基于聚類的方法和基于TSP的方法中，為了表示方便，我們把計算兩個文檔相似度的時間復雜度作為常數(shù)時間O(1)，但在實際情況中計算文檔相似度需要對兩個文檔中的詞項進行遍歷，時間復雜度正比于文檔的長度，所以準確的表示應(yīng)該把表格中的時間復雜度再乘以文檔長度。同樣，在表示空間復雜度時，我們忽略了文檔的長度，將一個文檔所需空間看作O(1)。而在基于排序的方法中，我們將比較兩個URL的時間復雜度看作是常數(shù)時間O(1)，在計算其空間復雜度時，將一個URL占用空間看作是O(1)。

總的來說，基于TSP的文檔序號重排技術(shù)被認為是目前比較好的方法，對索引壓縮率的提高也最明顯，但是性能最差，不太適合大規(guī)模數(shù)據(jù)，雖然可以通過優(yōu)化進一步降低算法復雜度，但是以犧牲壓縮率為代價；基于聚類的方法算法復雜度低于基于TSP的方法，適用于各種規(guī)模的數(shù)據(jù)集，但是其壓縮效果比較差。這兩類文檔序號重排方法均需要計算文檔之間相似度，而基于排序的方法通過比較尋找相似文檔，算法性能優(yōu)于前兩類方法，壓縮效果也比較好，在數(shù)據(jù)規(guī)模上沒有限制，具有良好的可擴展性。

在實際應(yīng)用中，可以根據(jù)軟硬件環(huán)境、文檔規(guī)模和壓縮率的要求，選擇合適的方法。

此外，從表4可以看出，我們可以綜合現(xiàn)有的文檔序號重排的方法，比如將基于聚類的方法和SVD分解結(jié)合[21]，或者將聚類和排序的方法結(jié)合[28]，也都獲得了很好的實驗結(jié)果。

文檔序號重排技術(shù)仍存在很多開放性問題，比如目前的方法主要是通過尋找相似文檔，然后分配連續(xù)文檔序號的方法?？偠灾?，這些方法都是通過間接的方法來優(yōu)化d-gap分布。是否存在一個根據(jù)倒排表中的文檔特征，直接以最小化d-gap編碼長度的文檔序號重排方法，是我們下一步要研究的問題。

表4 文檔序號重排方法匯總

[1] Witten I H, A Moffat, T C Bell. Managing Gigabytes: Compressing and Indexing Documents and Images[M]. Morgan Kaufmann, 1999.

[2] IDC. Digital Universe Study[OL]. 2011. http://idc-docserv.com/1142.

[3] CNNIC. 第28次中國互聯(lián)網(wǎng)絡(luò)發(fā)展狀況統(tǒng)計報告[OL]. 2012. http://www.cnnic.net.cn/dtygg/dtgg/201107/W020110719521725234632.pdf.

[4] Scholer F, et al. Compression of inverted indexes for fast query evaluation[C]//Proceedings of the SIGIR’05. Tampere, Finland: ACM, 2002: 222-229.

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

[6] Rice R, J Plaunt. Adaptive variable-length coding for efficient compression of spacecraft television data[J]. IEEE Transactions on Communication Technology, 1971, 19(6): 889-897.

[7] Anh V N, A Moffat. Inverted index compression using word-aligned binary codes[J]. Inf. Retr., 2005, 8(1): 151-166.

[8] Zukowski M, et al. Super-scalar RAM-CPU cache compression[C]//Proceedings of the ICDE’06. 2006: 59.

[9] Moffat A, L Stuiver. Binary interpolative coding for effective index compression[J]. Inf. Retr., 2000, 3(1): 25-47.

[10] Williams H E, J Zobel. Compressing integers for fast file access[J]. Computer Journal, 1999, 42(3): 193-201.

[11] Yan H, S Ding, T Suel. Inverted index compression and query processing with optimized document ordering[C]//Proceedings of the WWW’09. Madrid, Spain, 2009: 401-410.

[12] Manning C D, P Raghavan, H Schutze. Introduction to Information Retrieval[M]. Cambridge University Press, 2008.

[13] Zobel J, A Moffat. Inverted files for text search engines[J]. ACM Computing Surveys, 2006,38(2):6.

[14] Blanco R, A Barreiro. Characterization of a simple case of the reassignment of document identifiers as a pattern sequencing problem[C]//Proceedings of the SIGIR’05. Salvador, Brazil, 2005: 587-588.

[15] Karypis G, V Kumar. A fast and high quality multilevel scheme for partitioning irregular graphs[J]. SIAM Journal on Scientific Computing, 1998, 20(1): 359-392.

[16] Silvestri F, S Orlando, R Perego. Assigning identifiers to documents to enhance the clustering property of fulltext indexes[C]//Proceedings of the SIGIR’04. Sheffield, United Kingdom, 2004: 305-312.

[17] Cutting D R, et al. Scatter/gather: A cluster-based approach to browsing large document collections[C]//Proceedings of the SIGIR’92. 1992: 318-329.

[18] Silvestri F, R Perego, S Orlando. Assigning document identifiers to enhance compressibility of Web Search Engines indexes[C]//Proceedings of the SAC’04. Nicosia, Cyprus, 2004: 600-605.

[19] Shieh W Y, et al. Inverted file compression through document identifier reassignment[J]. Inf. Process. Manage., 2003, 39(1): 117-131.

[20] Blanco R,Barreiro. Document identifier reassignment through dimensionality reduction[J]. Advances in Information Retrieval, 2005: 375-387.

[21] Blanco R, A. Barreiro. TSP and cluster-based solutions to the reassignment of document identifiers[J]. Inf. Retr., 2006. 9(4): 499-517.

[22] Ding S, J Attenberg, T Suel. Scalable techniques for document identifier assignment in inverted indexes[C]//Proceedings of the WWW’10. Raleigh, North Carolina, USA, 2010: 311-320.

[23] Broder A Z, et al. Min-wise independent permutations[C]//Proceedings of the STOC’98. 1998:327-336.

[24] Haveliwala T, A Gionis, P Indyk. Scalable techniques for clustering the web[C]//Proceedings of the Third International Workshop on the Web and Databases. Dallas, Texas, 2000.

[25] Indyk P, R Motwani. Approximate nearest neighbors: towards removing the curse of dimensionality[C]//Proceedings of the STOC’98. 1998: 604-613.

[26] F Silvestri. Sorting out the document identifier assignment problem[C]//Proceedings of the ECIR’07. Rome, Italy, 2007: 101-112.

[27] Shi L, Wang B. Yet Another Sorting-Based Solution to the Reassignment of Document Identifiers[M]//Information Retrieval Technology. Springer Berlin Heidelberg, 2012: 238-249.

[28] Chen C, et al. Optimize document identifier assignment for inverted index compression[J]. Journal of Computational Information Systems 6, 2010: 339-346.

[29] Dan B, Guy B. Index compression through document reordering[C]//Proceedings of the DCC’02. IEEE Computer Society, 2002: 342.

Reassignment of Document Identifiers in Index Compression

SHI Liang1, ZHANG Hong1, LIU Xinran1, WANG Yong1, WANG Bin2

(1. National Computer Network Emergency Response Fechnical Team/Coordination Center of China, Bejing 100029, China; 2. Institute of Information Engineering, Chinese Academy of Sciences, Beijing 100093, China)

The inverted index has been widely used as the core data structure in search engine, desktop search and digital library. by. To best compress it via the d-gap or the integer coding, the algorithm called Document Identifiers Reassignment is usually adopted to achieve a high locality in an inverted index. This paper first introduces the basic principle of index compression, and then focuses on state-of-the-art techniques on document identifiers reassignment with an analysis of the pros and cons. It also summarizes all the related work and discusses the future work of document identifiers reassignment.

search engine; performance optimization; index compression; document identifier reordering; locality

史亮(1986—)，博士，中級工程師，主要研究領(lǐng)域為信息檢索和數(shù)據(jù)壓縮。E?mail：shiliang@ict．a(chǎn)c．cn王斌(1972—)，博士，研究員，主要研究領(lǐng)域為信息檢索與自然語言處理。E?mail：wangbin@iie．a(chǎn)c．cn

1003-0077(2015)02-0024-09

2012-12-03 定稿日期： 2013-03-21

國家973重點基礎(chǔ)研究發(fā)展規(guī)劃項目(2011CB302605)、科技支撐計劃(2012BAH47B04)。

TP391

A