1、基于查詢空間的分布式文檔集合劃分算法    摘要：合理的文檔集合劃分能夠有效的提高分布式信息檢索的效果，本文針對分布式信息檢索中的集合劃分問題，提出了一種基于查詢空間的文檔集合劃分算法。與傳統的基于文檔空間的劃分算法相比，該算法從一種全新的角度看待和理解文檔集合劃分問題，給出了一種針對大規模海量信息的文檔集合劃分解決方案。實驗表明該算法在算法效果和算法效率方面都有很大的提高。關鍵詞：計算機應用；中文信息處理；分布式信息檢索；文檔集合劃分；聚類1前言集合劃分是影響分布式信息檢索效果的一個重要問題。在分布式WEB信息檢索中，開展集合劃分的目的是希望通過集合劃

2、分操作，繼而在后面的檢索過程中可以通過檢索更少的文檔而獲取更好的檢索結果。對于集合劃分問題，直觀的想法是為了讓一個查詢的相關文檔都集中在一個或少數的集合中，但不同查詢的相關文檔可能是相同的，因此要實現將一個查詢的相關文檔都集中在一個或少數幾個集合中的想法，常常會出現矛盾和沖突的情況。在以往的工作中，Claudine Badue等人研究了對索引劃分的兩種策略：一是把文檔分布在多臺處理機上，并行的建立索引并進行檢索，在檢索時采用并行檢索的方式，每個搜索引擎同時檢索；另一種策略是，將建立好的倒排索引，按照關鍵詞的順序分布在不同的機器上，每個引擎負責處理一部分關鍵詞的倒排索引，在檢索時，只有含有查詢中

3、關鍵詞的機器，參與到本次檢索中。在這個工作中，對于第一種策略文檔的分布是隨機的，沒有根據一定的原則來進行處理，在檢索時采用的是并行的處理辦法，由于對所有文檔集合都要檢索，沒有降低檢索的計算開銷。Jeong通過研究對索引的劃分來提高檢索的效率，但這種對于索引的劃分主要考慮的是提高檢索的效率，沒有對檢索的效果進行充分的考慮。1999年SigIR上Xu和W.Bruce Croft等人采用的基于語言模型聚類的方法，把數據按照聚類結果進行劃分，取得比較好的實驗結果。該工作主要特點是從文檔的聚類出發來實現對文檔集合的劃分。通過文檔的聚類，有利于把相關的文檔聚集在一個類中，從而改善檢索結果的質量，由于文檔集

4、合劃分是為了進一步檢索服務的，因此必須考慮用戶查詢對于文檔集合劃分的影響，而該方法主要從文檔內容角度出發來實現對于文檔集合的劃分，沒有考慮查詢對于文檔集合劃分的影響，該方法在效率方面也難以面對海量的信息處理。本文將嘗試從查詢空間角度實現對文檔集合的劃分，該算法將在劃分的效率與劃分的效果方面具有明顯的改善與提高。2算法基本思想集合劃分問題，就是要將文檔集合劃分成若干個子集合，使得進一步的檢索能夠取得更好的檢索結果。文檔集合的劃分問題，雖然是對文檔集合的劃分，但絕不能簡單的從文檔角度看待這個問題，因為文檔集合劃分的目的是為了更好更方便的查找信息，因此文檔集合的劃分必須和信息的需求緊密聯系起來，而信

5、息需求又是通過查詢來體現的。一般的，對于信息檢索問題，存在著以下幾個相互關聯的空間：用戶空間、查詢空間、文檔空間、作者空間，如圖1所示。傳統的文檔集合劃分算法都是基于文檔空間的，也就是說從文檔本身角度實現對文檔集合的劃分，基于文檔空間的劃分方法是建立在“Closely as-sociated document tend to be relevant to the same requests”這個假設基礎之上的。但文檔集合的劃分最終目標是為查詢服務的，如果只關注文檔空間而忽略查詢空間顯然是不合理的。文檔集合的劃分應該是以有利于查詢為導向的劃分，其劃分的目的是為了更好的實現查詢，即：同一個查詢的相

6、關文檔盡量集中在一個或少數幾個文檔集合中。從查詢空間出發，要實現對文檔空間的劃分，必須建立起查詢空間與文檔空間的聯系，這種聯系就是查詢與文檔的相關關系。通過搜索引擎記錄的查詢日志來建立查詢與文檔之間的相關關系是一種有效的方法，當用戶向搜索引擎發出一個檢索請求時，整個檢索過程包括用戶點擊的檢索結果都會被搜索引擎記錄下來，形成查詢日志。查詢日志一般記錄了用戶所查詢的查詢詞、點擊查看的文檔等。例如“搜狗”搜索引擎的查詢日志如圖2所示。該日志每一行是一個用戶訪問行為的記錄，包括了用戶Session ID、查詢詞、URL(文檔)、該URL在檢索結果中的排序和用戶點擊該URL的順序等信息。用戶查詢日志記錄

7、了用戶一系列重要的行為，因此常常被用來幫助提高檢索結果的質量。如果假設用戶通過搜索引擎返回的文檔摘要(Snippet)可以判斷該文檔是否是查詢的相關文檔，那么可以認為用戶點擊過的文檔都是查詢的相關文檔，也就是查詢日志中每條記錄的URL都是其查詢詞的相關文檔，這樣利用查詢日志就建立起了文檔和查詢之間的相關關系，當然這相關關系的建立與實際的相關情況有一定的偏差，但總的來說用戶的點擊行為可以刻畫查詢與文檔的相關關系。如圖3所示，利用查詢日志構建的文檔和查詢之間的關系可以被看作一個二部圖，文檔和查詢之間的相關關系是二部圖中的邊。下一步本文需要解決的問題是利用構建的查詢與文檔的關系圖，實現對文檔集合的劃

8、分。針對查找時間和空間開銷隨聚類進行不斷增長的現實，本文提出采用BloomFilter算法來解決這個問題。BloomFilter算法可以使查找時間為一個常數，不隨被查找集合的大小而發生變化，BloomFilter的另外一個優點是，空間開銷固定不變，不會隨處理的進行而不斷增大，它是一種綜合平衡時間、空間代價，允許存在查找錯誤的有效查找算法。雖然可能存在查找的錯誤，但在理論和實踐方面，都可以把查找的錯誤控制在可以接受的范圍內。另外，在查詢日志中，相同的查詢可能被用戶多次查詢，重復出現的查詢在計算相關度時是被重復計算的，這樣的計算是有實際意義的，因為如果文檔d1和文檔d2是查詢qi的相關文檔，而查詢

9、qi被查詢了很多次，雖然不能說因為查詢qi重復出現了多次，就能增加文檔d1和文檔d2的相關性，但是從聚類角度認為d1和d2更相關是合理的，因為將d1和d2放入到一個集合中將有利于qi的查詢，而qi的被查詢次數多，有利于qi，就有利于降低查詢的整體開銷，這顯然是合理的。4實驗與分析為了驗證基于查詢空間的文檔集合劃分算法的                    有效性，本文使用的實驗數據是“搜狗”搜索

10、引擎發布的查詢日志數據。直觀定性的感覺，一種好的文檔集合劃分結果應該具有這樣的特點：1.一個查詢的相關文檔應該集中在一個或盡量少的文檔集合中，這樣在檢索時，只要檢索少量的文檔集合，就可以得到全部相關文檔。2.一個文檔集合中盡量包含一個查詢的相關文檔，而不包含其他查詢的相關文檔，這樣檢索時處理的無關文檔減少，有利于檢索。3.文檔集合的數量應該有一定的限制，如果沒有集合數量上的限制，令每個文檔集合中只包含一個文檔，雖然可以很好的滿足上面的兩條要求，但這樣的劃分顯然是不現實的。但這些直觀的原則不能定量的刻畫一種劃分算法的有效性，本文采用了下面的評價原則來對劃分結果進行評價，該原則很好的體現了上面對文

11、檔集合劃分的要求。評價原則：對于給定的一種文檔集合劃分算法和一個待查詢的查詢集合，計算出對于每個查詢要檢索到其全部相關文檔所需要處理的平均文檔數，把這個平均文檔數作為評價原則，需要處理的平均文檔數越少，說明劃分越合理，劃分方法越好。為了更好的說明實驗所使用數據的特點，本文針對日志文件進行了分析統計。該數據集合的一些統計特性如表1所示。我們將用戶查詢日志分為“訓練集合”和“測試集合”兩個部分，訓練集合用來對文檔集合進行劃分，而測試集合用來評價劃分的結果。在實驗中，文檔空間與查詢空間的相關關系采用前面定義的方法。為了方便比較，采用了隨機的劃分方法作為參照(隨機的劃分算法就是隨機的將文檔歸入某個類別

12、)，具體的實驗結果如表2所示。其中avgdoc1表示包括集合選擇在內的整體代價(平均文檔數)，而avgdoc2表示不計算集合選擇過程的代價(avgdoc1和avgdoc2的計算方法，將在文檔集合劃分評價部分闡述)，由于文檔集合共被劃分為100個子集合，因此avgdoc1和avgdoc2相差100。從實驗結果看，如果按照基于查詢的劃分方法，檢索一個查詢詞需要處理的文檔數目，大概只是隨機劃分方法的十分之一，約占整個文檔集合的2.7，可見基于查詢的文檔集合劃分方法相對于隨機的劃分方法取得了很好的實驗結果，這充分體現出了采用該算法對于文檔集合劃分問題的重要意義。從效率角度看，對文檔數為8 404 35

13、6的整個文檔集合進行劃分大約耗時57分鐘，劃分算法所消耗的絕對時間也是一個可以接受的劃分時間，由于該算法是一個線性時間復雜度的算法，因此算法的運行效率是可以滿足文檔集合劃分要求的。5結論基于查詢的文檔集合劃分方法從查詢空間這一全新視角實現對文檔集合的劃分，該方法利用查詢日志建立起文檔與查詢的關系圖，并采用本文提出的LIBCA算法實現了從查詢空間出發對文檔集合的劃分。基于查詢的文檔集合劃分方法體現了文檔集合劃分的直接目標，即：劃分的目的是為查詢服務。從實驗結果看，無論是算法的效果還是算法的效率都取得了比較理想的結果。在基于查詢的文檔集合劃分中，實現了利用查詢空間對文檔空間的劃分，反過來，利用文檔空間也可以實現對查詢空間的劃分，或者是在對文檔集合劃分后，會自然形成每一個子文檔集合對應著一系列的查詢的情況，這些查詢對應了該子文檔集