字符串詞典壓縮索引算法研究.pdf

1、近年來,隨著互聯(lián)網(wǎng)的迅猛發(fā)展和移動設(shè)備的大量普及,尤其是大數(shù)據(jù)時代的到來,越來越多的數(shù)據(jù)需要處理,其中文本數(shù)據(jù)占據(jù)著越來越大的比重,如何對大規(guī)模文本數(shù)據(jù)進行高效地存儲和索引成為一個新的挑戰(zhàn)。面對這一挑戰(zhàn),主要有兩種解決思路:一種是對數(shù)據(jù)進行空間上的壓縮,使得在相同存儲資源的情況下,能存儲和處理更多的數(shù)據(jù);另一種是設(shè)計更加高效的外存算法和數(shù)據(jù)結(jié)構(gòu),把數(shù)據(jù)放在外存,每次只讀取需要的部分到內(nèi)存中進行處理,確保高效的I/O操作。字符串詞典索引作

2、為文本索引的基礎(chǔ),其應(yīng)用無所不在,如地理信息系統(tǒng)、網(wǎng)絡(luò)搜索引擎、信息檢索系統(tǒng)等。大數(shù)據(jù)時代大規(guī)模的文本數(shù)據(jù)同樣對字符串詞典索引提出了新的挑戰(zhàn)。
　　本文從空間壓縮和外存索引兩方面對字符串詞典索引算法進行研究,主要研究工作如下：⑴針對現(xiàn)有的字符串詞典索引空間占用普遍較大的問題,提出了一種新的字符串詞典壓縮索引S-trie,實現(xiàn)了字符串詞典索引的壓縮,即在對原始字符串詞典數(shù)據(jù)進行索引以支持快速查找的同時,實現(xiàn)了對原始字符串詞典數(shù)據(jù)的壓

3、縮。通過實驗對比,證明了S-trie在空間性能方面的優(yōu)勢,S-trie的壓縮比達到原始數(shù)據(jù)的30％；⑵針對外存磁盤環(huán)境,對S-trie進行改進,提高數(shù)據(jù)的本地引用,使其在外存環(huán)境下具有高效的I/O操作,提出了一種字符串詞典外存壓縮索引 SB-trie。SB-trie繼承了S-trie空間占用小的優(yōu)點,同時具有良好的本地引用性能,可以高效地工作在外存磁盤環(huán)境。實驗表明,SB-trie在空間占用上優(yōu)于現(xiàn)有的索引,同時在數(shù)據(jù)量較大的情況下,也