基于上下文無關(guān)文法的倒排索引壓縮策略研究.pdf

1、伴隨著互聯(lián)網(wǎng)的快速發(fā)展，大型搜索引擎面臨著越來越嚴(yán)峻的性能挑戰(zhàn)。一方面，它們每秒鐘都要響應(yīng)成百上千的查詢請求，而這些請求需要從上百億張網(wǎng)頁中檢索出與之最相關(guān)的網(wǎng)頁集合。另一方面，它們必須不斷引入信息檢索及相關(guān)領(lǐng)域最新的科學(xué)技術(shù)，用以滿足日益增長的用戶需求，例如用戶個性化檢索。
　　為了解決上述問題，前人提出了大量針對搜索引擎架構(gòu)及策略的優(yōu)化方法，例如提前停止和結(jié)果緩存策略。本文將專注于研究一類重要的搜索引擎性能優(yōu)化方法——倒排索引

2、壓縮。
　　盡管研究者們提出了大量高度優(yōu)化的算數(shù)編碼方法用以減少倒排索引的存儲空間及其查詢處理時間，但是隨著互聯(lián)網(wǎng)信息和查詢負(fù)載的不斷增長，傳統(tǒng)的索引壓縮方法仍面臨著日益嚴(yán)峻的性能挑戰(zhàn)。為此，本文提出了一套全新的基于文法的倒排索引壓縮策略，該策略在顯著提高索引壓縮效果的同時，還能有效提高后續(xù)的查詢處理性能。
　　本文方法主要通過識別不同列表內(nèi)反復(fù)出現(xiàn)的重復(fù)數(shù)據(jù)模式（相同文檔號子序列），從而將原始倒排索引存儲成一個數(shù)據(jù)組織更為

3、緊湊的上下文無關(guān)文法。為了進一步提高壓縮效果，本文在生成的文法索引基礎(chǔ)上又提出了一系列新的索引存儲結(jié)構(gòu)，例如一種四段式結(jié)構(gòu)——通過執(zhí)行一種基于文法的倒排索引重排策略得到。實驗結(jié)果顯示：與傳統(tǒng)索引壓縮策略相比，通過采用本文方法，存儲完整倒排索引所需的磁盤空間可降低10％~37%。
　　為了最大限度地提高本文方法的解壓性能，文中針對存儲結(jié)構(gòu)不同的各式索引分別給出了它們對應(yīng)的快速解壓策略。實驗結(jié)果顯示：相比于傳統(tǒng)索引壓縮策略，基于文法的