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

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

?

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

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

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

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

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

1 引言

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

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

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

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

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

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

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

2 索引壓縮

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

(1)

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

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

(2)

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

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

表1 倒排表的基本形式和d-gap形式所需編碼長(zhǎng)度對(duì)比

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

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

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

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

(3)

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

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

表2 倒排索引的基本形式和重排后d-gap形式編碼長(zhǎng)度對(duì)比

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

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

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

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

4 基于聚類的方法

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

4.1 自頂向下的方法

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

(1)B&B算法

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

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

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

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

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

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

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

(2)TransactionalB&B算法

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

1) 選擇中心點(diǎn)： 類似于B&B算法，但是在計(jì)算DSG時(shí)使用Jaccard相似度；因?yàn)闆]有預(yù)先建立倒排索引，所以沒有過濾高頻詞；

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

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

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

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

(3)Bisecting算法

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

4.2 自底向上的方法

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

(1)k-means-like算法

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

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

1) 選擇中心點(diǎn)： 使用Buckshot[17]方法，選取k個(gè)聚類中心點(diǎn)；

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

(2)k-scan算法

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

1) 文檔預(yù)排序： 對(duì)N篇文檔，按照文檔長(zhǎng)度降序排列；

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

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

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

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

4.3 方法小結(jié)

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

5 基于TSP的方法

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

5.1 基本的TSP的方法

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

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

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

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

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

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

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

(4)

(5)

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

(6)

(7)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5.4 方法小結(jié)

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

6 基于排序的方法

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

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

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

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

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

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

1) 選擇對(duì)文檔排序時(shí)，詞項(xiàng)的比較順序： 作者在文中實(shí)驗(yàn)了三種順序，分別是文檔頻率升序、降序和原始順序；

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

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

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

6.3 方法小結(jié)

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

7 總結(jié)

本文總結(jié)了目前常見的文檔序號(hào)重排方法。當(dāng)?shù)古疟聿捎貌钪荡鎯?chǔ)并使用整數(shù)編碼進(jìn)行壓縮時(shí)，通過對(duì)文檔序號(hào)進(jìn)行重排，可以有效地在倒排表中產(chǎn)生局部連續(xù)性，顯著提高索引壓縮率。

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

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

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

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

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

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

表4 文檔序號(hào)重排方法匯總

[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次中國(guó)互聯(lián)網(wǎng)絡(luò)發(fā)展?fàn)顩r統(tǒng)計(jì)報(bào)告[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—)，博士，中級(jí)工程師，主要研究領(lǐng)域?yàn)樾畔z索和數(shù)據(jù)壓縮。E?mail：shiliang@ict．a(chǎn)c．cn王斌(1972—)，博士，研究員，主要研究領(lǐng)域?yàn)樾畔z索與自然語言處理。E?mail：wangbin@iie．a(chǎn)c．cn

1003-0077(2015)02-0024-09

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

國(guó)家973重點(diǎn)基礎(chǔ)研究發(fā)展規(guī)劃項(xiàng)目(2011CB302605)、科技支撐計(jì)劃(2012BAH47B04)。

TP391

A