论文部分内容阅读
在信息检索领域,基于数据库的条目型检索系统和基于倒排表的检索系统能解决一部分需求,但在字符串精确匹配、生物序列分析、任意模式检索等领域,无法通过数据库系统和倒排表完成。全文索引技术(full-text index)可以在一定程度上解决这类问题,但是形如后缀数组(suffix array,SA)和后缀树(suffix trie,ST)这样的全文索引结构需要很大的空间,实用性不强。压缩索引(compressed full-text self-index)技术解决了上述问题,它对原始数据进行压缩表示,所需空间与纯压缩算法相当,而且能够在不需要恢复出原始数据的情况下提供高效的模式匹配功能。本文研究了常见后缀数组构建算法、压缩后缀数组、Bit Map、FM-index、熵与编码等方面的知识。在此基础上,设计和实现了高效的压缩索引方案,包含以下三部分。首先,针对常见后缀数组计算方法内存峰值过大、计算速度慢的问题,提出了高效的SA计算方法DCV,具有省内存、速度快的优点,运行时内存峰值为原始数据的5倍左右,运行时间与知名的LS方法相当,总体性能优越。其次,我们针对压缩后缀数组(compressed suffix array,CSA)设计了两种高效、简洁的结构:CSA和Adaptive-CSA,分别对?数组的差分序列使用gamma编码和自适应的混合编码,理论结果保持了该领域已有理论结果的性能,可以在O(m log n)的时间内完成count查询,m表示模式长度,可以将原始数据压缩到2nHk(T)+n+o(n)比特,Hk(T)表示原文T的k阶经验熵,结合自适应策越、调优的编码方法、查找表等优化手法,使我们的CSA结构在构建时间、压缩率、查询速度上优于常见CSA结构,在Canterbury Corpus和Pizza&Chili Corpus上的各项测试结果优势明显。最后,提出了一种高效的Bit Map索引结构,对每块数据能自动的选择最佳编码方法,并能根据数据的分布选择最合适的块大小等参数,并以此为基础,结合小波树实现了第二种压缩索引方案Adaptive-FM,充分利用数据分布特点,具有数据感知的能力,理论结果保持了该领域已有理论结果的性能,count查询可以在O(m log?)时间内完成,?表示字符表大小,所需空间为2nHk(T)+o(n)log?比特,Canterbury Corpus和Pizza&Chili Corpus数据集上的测试表明Adaptive-FM综合性能优越,特别是压缩率。所开发的压缩索引已工程化,可在https://github.com/chenlonggang/上获取。