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

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

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

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