信息化時代,數(shù)據(jù)量的激增給我們帶來了機遇也帶來了信息存儲及檢索的挑戰(zhàn)。字符串匹配是信息檢索最基本的操作,解決該問題的常用方式為索引匹配和順序匹配。鑒于索引匹配的高效性,使用后綴數(shù)組(Suffix Array,SA)等索引結(jié)構(gòu)的匹配方式逐漸代替了傳統(tǒng)的順序匹配。然而SA空間過大的問題,限制了其實用性。如何高效地存儲SA這一索引結(jié)構(gòu),并使其支持快速查詢操作,就成為了壓縮索引領(lǐng)域重要的研究課題之一。就壓縮后綴數(shù)組(Compressed Suffix Array,CSA)這一熵壓縮結(jié)構(gòu)而言,近年來的相關(guān)研究都以如何高效編碼Ф數(shù)組為目標(biāo)。本文沿襲這樣的研究路線,結(jié)合Ф數(shù)組的差值序列(gap序列)針對不同文本展現(xiàn)出的數(shù)據(jù)特點,設(shè)計具有針對性的CSA新結(jié)構(gòu)與算法,力圖改善CSA面對不同類型文本輸入時的壓縮率及查詢效率。首先,本文以GamCSA這一雙層索引框架為基礎(chǔ),對各種類型的標(biāo)準(zhǔn)文本輸入進行實驗,發(fā)現(xiàn)不同文本具有不一樣的gap序列統(tǒng)計特征,具體反映在其1-gap比重和1-gap-Runs的長度上,其中1-gap表示gap序列中的1值,1-gap-Runs表示gap序列中1值連續(xù)出現(xiàn)次數(shù)的平均值。1...

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

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

【文章目錄】：
摘要
ABSTRACT
符號對照表
縮略語對照表
第一章 緒論
    1.1 研究背景及意義
    1.2 研究現(xiàn)狀
    1.3 本文工作
第二章 預(yù)備知識
    2.1 符號及問題描述
    2.2 文本的熵
    2.3 后綴數(shù)組
    2.4 BWT變換
    2.5 近鄰函數(shù)Ф的定義
    2.6 本章小結(jié)
第三章 壓縮后綴數(shù)組的基本框架
    3.1 近鄰函數(shù)Ф的表示
    3.2 字符頻數(shù)統(tǒng)計表
    3.3 近鄰函數(shù)Ф的線性構(gòu)造
    3.4 本章小結(jié)
第四章 編碼
    4.1 差值序列分析
    4.2 候選編碼
    4.3 混合編碼及結(jié)構(gòu)分類
    4.4 本章小結(jié)
第五章 壓縮后綴數(shù)組的新結(jié)構(gòu)和算法
    5.1 高度重復(fù)文本集的HiCSA結(jié)構(gòu)
    5.2 普通文本集的NorCSA結(jié)構(gòu)
    5.3 空間分析
    5.4 解碼加速
    5.5 計數(shù)查詢
        5.5.1 詞匯加速表
        5.5.2 count算法
    5.6 定位和恢復(fù)查詢
        5.6.1 采樣方式
        5.6.2 locate和extract算法
        5.6.3 變長采樣策略
    5.7 本章小結(jié)
第六章 實驗結(jié)果與分析
    6.1 實驗環(huán)境和數(shù)據(jù)源
    6.2 變長采樣實驗
    6.3 性能評估
    6.4 本章小結(jié)
第七章 總結(jié)與展望
    7.1 總結(jié)
    7.2 展望
參考文獻
致謝
作者簡介



本文編號：3787677