倒排索引壓縮算法研究.pdf

1、數(shù)據(jù)集的檢索通常使用倒排索引模型進(jìn)行檢索，可以在海量的文本數(shù)據(jù)獲取信息。基于數(shù)據(jù)集構(gòu)建倒排索引文件通常十分龐大，壓縮倒排索引可以減少空間使用，在相同的內(nèi)存中駐留更多的信息，加快檢索的速度。而現(xiàn)有的倒排索引壓縮算法在空間利用、解壓性能存在局限性，因此，倒排索引的高效壓縮與解壓成為一個(gè)重要的課題。
　　倒排索引的壓縮分為單詞壓縮和倒排鏈表的壓縮，倒排鏈表的壓縮主要將單詞在文檔中出現(xiàn)的docID、frequency和positions等

2、信息進(jìn)行壓縮，而這些信息的壓縮通常為整數(shù)壓縮。
　　本文提出并實(shí)現(xiàn)了RFMEGC壓縮算法對(duì)倒排索引中docID的壓縮和解壓。該算法在RFEGC算法的基礎(chǔ)上，在實(shí)現(xiàn)docID的壓縮編碼時(shí)，減少除法的計(jì)算步驟，從而提高壓縮編碼速度，并降低倒排索引的文件大小。
　　本文提出并且實(shí)現(xiàn)了RLERFEGC壓縮算法對(duì)倒排索引中docID的壓縮和解壓算法。該算法在RFEGC壓縮算法的基礎(chǔ)上，將連續(xù)的整數(shù)1的序列替換為該序列的長度，然后將該長

3、度使用RFEGC壓縮算法進(jìn)行壓縮，最后實(shí)現(xiàn)docID的壓縮，降低docID壓縮文件的整體空間。
　　本文提出并實(shí)現(xiàn)了DPRFEGC壓縮算法對(duì)倒排索引中docID的壓縮和解壓算法。BRFEGC壓縮算法將docID序列分為指定長度的整數(shù)序列，然后對(duì)整數(shù)序列使用RFEGC壓縮算法進(jìn)行壓縮，使用定長的整數(shù)序列進(jìn)行壓縮，對(duì)不同的整數(shù)序列，倒排索引的壓縮效果會(huì)明顯不同。DPRFEGC壓縮算法使用動(dòng)態(tài)規(guī)劃，計(jì)算整數(shù)序列的最優(yōu)分塊方案，根據(jù)分塊方