基于文法壓縮的倒排索引求交算法設(shè)計(jì).pdf

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

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

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