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

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

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

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