基于文法壓縮的倒排索引求交算法設計.pdf

1、隨著互聯(lián)網網頁數量的日益增多，如何提高搜索引擎的效率是近些年學術界及工業(yè)界都在極力解決的問題。搜索引擎的基本檢索數據結構是倒排索引，近幾年，許多研究都專注于提升倒排索引的壓縮率和求交效率。目前，主流搜索引擎的倒排索引使用的是算術編碼技術，文法壓縮算法在倒排索引上的應用并不廣泛。本文探討并改良了一種適用于倒排索引的文法壓縮技術，在兼顧倒排索引壓縮率的同時，設計了適用于文法壓縮的高效的求交算法。
　　本文的具體工作包括以下幾個方面：<

2、br>　　第一，本文系統(tǒng)地回顧了倒排索引的壓縮及求交算法，并將文檔重排技術也納入了研究討論的范圍，對現(xiàn)有的重排技術進行了總結。倒排索引的鏈表中有許多重復的文檔序列，傳統(tǒng)的算術編碼算法在壓縮和求交過程中并沒有使用這些信息。本文利用文法壓縮算法對倒排列表之間的重復序列進行了抽取，并將其應用到了倒排索引的求交過程之中。
　　第二，本文設計了基于文法壓縮的倒排索引求交算法，并為優(yōu)化求交效率改良了索引格式。在文法壓縮算法的壓縮過程中，會將重

3、復的序列集中存儲到字典中，并用Pattern（產生式）代表某一段重復的序列。其中歸約產生的 Pattern和字典都是傳統(tǒng)求交技術中沒有的元素。本文針對這些新的列表元素設計了搜索算法，設計了適用于文法壓縮的求交算法，并針對求交過程優(yōu)化修改了文法壓縮的歸約過程。
　　第三，本文對文法壓縮后的倒排列表的求交效率進行了優(yōu)化。不僅使用了傳統(tǒng)的求交技術優(yōu)化，還加入了文檔重排、Run-Length等相關技術。本文通過這些手段優(yōu)化了文法壓縮下的倒