本文關(guān)鍵詞：字符串詞典壓縮索引算法研究

  更多相關(guān)文章： 字符串詞典 壓縮索引 外存算法 大數(shù)據(jù)處理

【摘要】：近年來，隨著互聯(lián)網(wǎng)的迅猛發(fā)展和移動(dòng)設(shè)備的大量普及，尤其是大數(shù)據(jù)時(shí)代的到來，越來越多的數(shù)據(jù)需要處理，其中文本數(shù)據(jù)占據(jù)著越來越大的比重，如何對(duì)大規(guī)模文本數(shù)據(jù)進(jìn)行高效地存儲(chǔ)和索引成為一個(gè)新的挑戰(zhàn)。面對(duì)這一挑戰(zhàn)，主要有兩種解決思路：一種是對(duì)數(shù)據(jù)進(jìn)行空間上的壓縮，使得在相同存儲(chǔ)資源的情況下，能存儲(chǔ)和處理更多的數(shù)據(jù)；另一種是設(shè)計(jì)更加高效的外存算法和數(shù)據(jù)結(jié)構(gòu)，把數(shù)據(jù)放在外存，每次只讀取需要的部分到內(nèi)存中進(jìn)行處理，確保高效的I/O操作。 字符串詞典索引作為文本索引的基礎(chǔ)，其應(yīng)用無所不在，如地理信息系統(tǒng)、網(wǎng)絡(luò)搜索引擎、信息檢索系統(tǒng)等。大數(shù)據(jù)時(shí)代大規(guī)模的文本數(shù)據(jù)同樣對(duì)字符串詞典索引提出了新的挑戰(zhàn)。本文從空間壓縮和外存索引兩方面對(duì)字符串詞典索引算法進(jìn)行研究，其主要研究工作如下： (1)針對(duì)現(xiàn)有的字符串詞典索引空間占用普遍較大的問題，提出了一種新的字符串詞典壓縮索引S-trie，實(shí)現(xiàn)了字符串詞典索引的壓縮，即在對(duì)原始字符串詞典數(shù)據(jù)進(jìn)行索引以支持快速查找的同時(shí)，，實(shí)現(xiàn)了對(duì)原始字符串詞典數(shù)據(jù)的壓縮。通過實(shí)驗(yàn)對(duì)比，證明了S-trie在空間性能方面的優(yōu)勢，S-trie的壓縮比達(dá)到原始數(shù)據(jù)的30%。 (2)針對(duì)外存磁盤環(huán)境，對(duì)S-trie進(jìn)行改進(jìn)，提高數(shù)據(jù)的本地引用，使其在外存環(huán)境下具有高效的I/O操作，提出了一種字符串詞典外存壓縮索引SB-trie。SB-trie繼承了S-trie空間占用小的優(yōu)點(diǎn)，同時(shí)具有良好的本地引用性能，可以高效地工作在外存磁盤環(huán)境。實(shí)驗(yàn)表明，SB-trie在空間占用上優(yōu)于現(xiàn)有的索引，同時(shí)在數(shù)據(jù)量較大的情況下，也具有良好的查找時(shí)間性能。
【關(guān)鍵詞】：字符串詞典 壓縮索引 外存算法 大數(shù)據(jù)處理
【學(xué)位授予單位】：蘇州大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2014
【分類號(hào)】：TP391.1
【目錄】：

• 中文摘要4-5
• Abstract5-9
• 第一章 緒論9-14
• 1.1 研究背景與意義9-11
• 1.2 研究現(xiàn)狀11-12
• 1.3 本文研究內(nèi)容12
• 1.4 本文組織結(jié)構(gòu)12-14
• 第二章 字符串詞典外存索引概述14-25
• 2.1 問題定義14
• 2.2 基礎(chǔ)算法和數(shù)據(jù)結(jié)構(gòu)14-19
• 2.3 外存模型和算法19-22
• 2.3.1 外存模型19
• 2.3.2 前綴編碼的 B+tree19-20
• 2.3.3 String B-tree 索引20-21
• 2.3.4 B-trie 索引21-22
• 2.4 緩存無關(guān)模型和算法22-24
• 2.5 本章小結(jié)24-25
• 第三章 文本壓縮索引概述25-38
• 3.1 數(shù)據(jù)壓縮相關(guān)的基礎(chǔ)算法和數(shù)據(jù)結(jié)構(gòu)25-30
• 3.2 全文壓縮索引30-35
• 3.2.1 FM 索引31-32
• 3.2.2 壓縮后綴數(shù)組32-33
• 3.2.3 LZ 索引33-35
• 3.3 字符串集合的壓縮索引35-37
• 3.3.1 基于前綴編碼的方法35-36
• 3.3.2 基于 RePair 編碼的方法36
• 3.3.3 基于 FM 索引的方法36-37
• 3.4 本章小結(jié)37-38
• 第四章 字符串詞典壓縮索引 S-trie38-48
• 4.1 S-trie 索引38-43
• 4.1.1 S-trie 數(shù)據(jù)結(jié)構(gòu)38-41
• 4.1.2 S-trie 構(gòu)造算法41
• 4.1.3 S-trie 準(zhǔn)確查找算法41-43
• 4.2 S-trie 實(shí)現(xiàn)細(xì)節(jié)43-45
• 4.3 實(shí)驗(yàn)45-47
• 4.3.1 實(shí)驗(yàn)環(huán)境45
• 4.3.2 實(shí)驗(yàn)結(jié)果45-46
• 4.3.3 實(shí)驗(yàn)分析46-47
• 4.4 本章小結(jié)47-48
• 第五章 字符串詞典外存壓縮索引 SB-trie48-60
• 5.1 S-trie 的下界查找操作48-53
• 5.1.1 下界查找操作的定義48
• 5.1.2 下界查找操作48-50
• 5.1.3 S-trie 的下界查找輔助過程實(shí)現(xiàn)50-53
• 5.2 SB-trie 索引53-55
• 5.2.1 SB-trie 數(shù)據(jù)結(jié)構(gòu)53
• 5.2.2 SB-trie 的構(gòu)造算法53-55
• 5.2.3 SB-trie 的查找算法55
• 5.3 實(shí)驗(yàn)55-59
• 5.3.1 實(shí)驗(yàn)環(huán)境56
• 5.3.2 實(shí)驗(yàn)結(jié)果和分析56-59
• 5.4 本章小結(jié)59-60
• 第六章 總結(jié)與展望60-62
• 6.1 本文工作總結(jié)60-61
• 6.2 未來工作展望61-62
• 參考文獻(xiàn)62-67
• 攻讀碩士學(xué)位期間取得的科研成果67-68
• 致謝68-69

【參考文獻(xiàn)】

中國期刊全文數(shù)據(jù)庫 前4條

1 闞君滿;;基于改進(jìn)哈夫曼編碼的全文索引結(jié)構(gòu)壓縮算法[J];吉林大學(xué)學(xué)報(bào)(信息科學(xué)版);2011年05期

2 申展;江寶林;陳yN;唐磊;胡運(yùn)發(fā);;全文檢索模型綜述[J];計(jì)算機(jī)科學(xué);2004年05期

3 劉小珠;彭智勇;陳旭;;高效的隨機(jī)訪問分塊倒排文件自索引技術(shù)[J];計(jì)算機(jī)學(xué)報(bào);2010年06期

4 劉小珠;彭智勇;;全文索引技術(shù)時(shí)空效率分析[J];軟件學(xué)報(bào);2009年07期

本文編號(hào)：655715