倒排索引是信息檢索系統(tǒng)的重要組成部分之一,被用于維護(hù)數(shù)十億文檔并對大量查詢操作進(jìn)行響應(yīng)。隨著當(dāng)前互聯(lián)網(wǎng)數(shù)據(jù)量的不斷增加,倒排索引的體積也不斷攀升。倒排索引壓縮算法可以提高信息檢索系統(tǒng)的性能,減少索引的空間占用,加快查詢處理速度,因而成為了重要的研究對象。模式化編碼相比傳統(tǒng)的位編碼具有解碼速度快,壓縮效果好的優(yōu)點,因而被廣泛應(yīng)用于倒排索引壓縮中。本文針對模式化編碼中的字節(jié)對齊編碼算法、固定比特編碼算法以及字對齊編碼算法進(jìn)行深入研究,主要工作如下:(1)本文對字節(jié)對齊編碼和固定比特編碼的特點進(jìn)行剖析,并以此為基礎(chǔ)提出了 PVU編碼壓縮算法。算法以字節(jié)對齊編碼為基礎(chǔ),引入了固定比特編碼中的分區(qū)思想,使用“模式區(qū)-長度區(qū)-編碼區(qū)”的三層存儲結(jié)構(gòu)對字節(jié)對齊編碼中的二層結(jié)構(gòu)加以改進(jìn)。算法代替以字節(jié)為最小存儲單位的單一方式,設(shè)計了多種最小存儲單位供各分區(qū)選取最優(yōu)的壓縮模式,從而提高了全局壓縮率。針對PVU編碼的分區(qū)策略進(jìn)行研究,將編碼分區(qū)問題轉(zhuǎn)換為圖論中的最短路徑問題,設(shè)計并實現(xiàn)了動態(tài)規(guī)劃求解編碼最優(yōu)分區(qū)的方法,并提出了分區(qū)優(yōu)化的OptPVU編碼。(2)分析DocID序列經(jīng)預(yù)處理后的取值分布特征,以...

【文章頁數(shù)】：71 頁

【學(xué)位級別】：碩士

【文章目錄】：
致謝
摘要
ABSTRACT
1 引言
    1.1 課題研究的背景和意義
    1.2 課題研究的內(nèi)容和目標(biāo)
    1.3 論文組織結(jié)構(gòu)
2 倒排索引及其相關(guān)技術(shù)介紹
    2.1 倒排索引
    2.2 倒排索引的預(yù)處理方案
        2.2.1 D-Gap編碼
        2.2.2 文檔標(biāo)識符分配技術(shù)
    2.3 模式化編碼壓縮
    2.4 模式化編碼壓縮算法
        2.4.1 Variable Byte編碼
        2.4.2 Stream VByte編碼
        2.4.3 Binary Packing編碼
        2.4.4 PForDelta編碼
        2.4.5 Simple Family編碼壓縮算法
    2.5 本章小結(jié)
3 PVU編碼壓縮算法
    3.1 PVU編碼壓縮算法
        3.1.1 PVU編碼壓縮算法的基本原理
        3.1.2 PVU編碼壓縮算法的模式選擇
    3.2 PVU編碼壓縮算法的編碼過程
    3.3 PVU編碼壓縮算法的解碼過程
    3.4 PVU編碼壓縮算法實例
    3.5 PVU編碼壓縮算法的分區(qū)優(yōu)化策略
    3.6 本章小結(jié)
4 Simple21編碼壓縮算法
    4.1 DocID序列取值分布研究
    4.2 Simple21編碼壓縮算法的基本原理
    4.3 Simple21編碼壓縮算法的編碼過程
    4.4 Simple21編碼壓縮算法的解碼過程
    4.5 本章小結(jié)
5 實驗和分析
    5.1 實驗評價指標(biāo)
        5.1.1 倒排索引編碼實驗評價指標(biāo)
        5.1.2 倒排索引解碼實驗評價指標(biāo)
    5.2 實驗環(huán)境
        5.2.1 實驗數(shù)據(jù)集
        5.2.2 實驗運(yùn)行環(huán)境和相關(guān)工具
    5.3 倒排索引壓縮算法編碼實驗與分析
    5.4 倒排索引壓縮算法解碼實驗與分析
    5.5 本章小結(jié)
6 總結(jié)與展望
    6.1 研究工作總結(jié)
    6.2 對后續(xù)工作的展望
參考文獻(xiàn)
作者簡歷及攻讀碩士學(xué)位期間取得的研究成果
學(xué)位論文數(shù)據(jù)集



本文編號：3842686