壓縮全文自索引算法的研究.pdf

1、在信息檢索領(lǐng)域，基于數(shù)據(jù)庫(kù)的條目型檢索系統(tǒng)和基于倒排表的檢索系統(tǒng)能解決一部分需求，但在字符串精確匹配、生物序列分析、任意模式檢索等領(lǐng)域，無法通過數(shù)據(jù)庫(kù)系統(tǒng)和倒排表完成。全文索引技術(shù)(full-text index)可以在一定程度上解決這類問題，但是形如后綴數(shù)組(suffix array,SA)和后綴樹(suffix trie,ST)這樣的全文索引結(jié)構(gòu)需要很大的空間，實(shí)用性不強(qiáng)。壓縮索引(compressed full-text self

2、-index)技術(shù)解決了上述問題，它對(duì)原始數(shù)據(jù)進(jìn)行壓縮表示，所需空間與純壓縮算法相當(dāng)，而且能夠在不需要恢復(fù)出原始數(shù)據(jù)的情況下提供高效的模式匹配功能。
　　本文研究了常見后綴數(shù)組構(gòu)建算法、壓縮后綴數(shù)組、BitMap、FM-index、熵與編碼等方面的知識(shí)。在此基礎(chǔ)上，設(shè)計(jì)和實(shí)現(xiàn)了高效的壓縮索引方案，包含以下三部分。首先，針對(duì)常見后綴數(shù)組計(jì)算方法內(nèi)存峰值過大、計(jì)算速度慢的問題，提出了高效的 SA計(jì)算方法 DCV，具有省內(nèi)存、速度快的優(yōu)

3、點(diǎn)，運(yùn)行時(shí)內(nèi)存峰值為原始數(shù)據(jù)的5倍左右，運(yùn)行時(shí)間與知名的LS方法相當(dāng)，總體性能優(yōu)越。其次，我們針對(duì)壓縮后綴數(shù)組(compressed suffix array,CSA)設(shè)計(jì)了兩種高效、簡(jiǎn)潔的結(jié)構(gòu)：CSA和Adaptive-CSA，分別對(duì)?數(shù)組的差分序列使用gamma編碼和自適應(yīng)的混合編碼，理論結(jié)果保持了該領(lǐng)域已有理論結(jié)果的性能，可以在O(m log n)的時(shí)間內(nèi)完成count查詢，m表示模式長(zhǎng)度，可以將原始數(shù)據(jù)壓縮到2nHk(T)+n+

4、o(n)比特，Hk(T)表示原文T的k階經(jīng)驗(yàn)熵，結(jié)合自適應(yīng)策越、調(diào)優(yōu)的編碼方法、查找表等優(yōu)化手法，使我們的CSA結(jié)構(gòu)在構(gòu)建時(shí)間、壓縮率、查詢速度上優(yōu)于常見CSA結(jié)構(gòu)，在Canterbury Corpus和Pizza&Chili Corpus上的各項(xiàng)測(cè)試結(jié)果優(yōu)勢(shì)明顯。最后，提出了一種高效的BitMap索引結(jié)構(gòu)，對(duì)每塊數(shù)據(jù)能自動(dòng)的選擇最佳編碼方法，并能根據(jù)數(shù)據(jù)的分布選擇最合適的塊大小等參數(shù)，并以此為基礎(chǔ)，結(jié)合小波樹實(shí)現(xiàn)了第二種壓縮索引方案A

5、daptive-FM，充分利用數(shù)據(jù)分布特點(diǎn)，具有數(shù)據(jù)感知的能力，理論結(jié)果保持了該領(lǐng)域已有理論結(jié)果的性能，count查詢可以在 O(m log?)時(shí)間內(nèi)完成，?表示字符表大小，所需空間為2nHk(T)+ o(n)log?比特，Canterbury Corpus和Pizza&Chili Corpus數(shù)據(jù)集上的測(cè)試表明Adaptive-FM綜合性能優(yōu)越，特別是壓縮率。所開發(fā)的壓縮索引已工程化，可在 https://github.com/che