基于倒排索引的壓縮算法性能研究.pdf

1、在這個信息爆炸的時代，每天都會產(chǎn)生成千上百萬的新信息，反映在因特網(wǎng)上，是網(wǎng)頁數(shù)量的急劇增長。如何在巨量級的信息集合中，高效的定位、查找所需的目標(biāo)信息，這使得搜索引擎成為當(dāng)今最熱門的技術(shù)之一，也對搜索引擎的性能提出了更高的要求。搜索引擎的索引結(jié)構(gòu)與它的性能密切相關(guān)，倒排索引是搜索引擎使用最為廣泛的索引保存形式，它將“關(guān)鍵詞”作為搜索的起始，追蹤包含該關(guān)鍵詞的眾多信息源。在倒排索引中把關(guān)鍵字(term)映射到包含該關(guān)鍵字的文檔集合，對于每一

2、個關(guān)鍵字，記錄包含該關(guān)鍵字的文檔標(biāo)識，文檔內(nèi)頻率以及文檔內(nèi)位置信息：term->(，d t f，I d，[ 0 p，…1 freq p ])……。
　　 本文所進(jìn)行的索引壓縮算法的研究是在該索引結(jié)構(gòu)基礎(chǔ)上進(jìn)行的。采用索引壓縮技術(shù)不僅能夠減小索引的容量，同時也能提高查詢性能。其優(yōu)勢在于壓縮后的索引需要的存儲空間較少，并且壓縮后的數(shù)據(jù)能更好的利用通信帶寬，相比未經(jīng)壓縮的數(shù)據(jù)，每秒能傳輸更多的信息量?；诳焖俳鈮旱姆桨?，傳輸和解壓壓縮

3、后數(shù)據(jù)的總時間代價比傳輸未經(jīng)壓縮的數(shù)據(jù)時間代價要小的多。在檢索過程中，通常在內(nèi)存中對倒排列表進(jìn)行緩存，可提升查詢響應(yīng)的性能，在緩存容量相等前提下，能容納更多以壓縮形式存放的倒排信息，從而提升緩存的命中率及查詢響應(yīng)速度。本文所作的是在開源信息檢索系統(tǒng)Lucene 上，實現(xiàn)Variable-Byte、Simple9、PForDelta 詳盡評測，關(guān)注文檔號、頻率、位置信息在Lucene的word-level 倒排索引中壓縮存放。近年來有一些

4、新的壓縮算法提出，但還沒有文章在基于Java 環(huán)境，流行通用，影響廣泛的Lucene 中來評測實驗算法。本文的工作主要有1)改進(jìn)具有最快解壓速度PForDelta的實現(xiàn)，在保證不降低算法解壓速度的前提下，提升了算法的位使用率，并加以實驗驗證。2)探討在Java 環(huán)境由if-then-else 結(jié)構(gòu)導(dǎo)致的分枝預(yù)測對Java 程序的性能影響，在JVM 中運(yùn)行的程序弱化了分枝預(yù)測帶來的性能損害。3)接著修改Lucene的索引結(jié)構(gòu)，研究數(shù)據(jù)存放

5、是否間隔分布對算法壓縮比率和解壓性能的影響。4)在本文的最后全面比較算法的壓縮比率及關(guān)鍵字和短語查詢性能，對實驗結(jié)果進(jìn)行分析。從實驗結(jié)果可以看出，在各個數(shù)量級的文檔集合上，Variable-Byte 表現(xiàn)最為穩(wěn)定，并且在基于跳躍機(jī)制的短語查詢中有最好的表現(xiàn)。Simple9 有最好的壓縮比率，但由于Java 環(huán)境對分枝預(yù)測性能損害的弱化，其查詢性能比其他兩個算法要差。PForDelta在解壓代碼的關(guān)鍵區(qū)域去除if-then-else 程序