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

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

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

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

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

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