压缩全文自索引算法的研究

《压缩全文自索引算法的研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、压缩全文自索引算法的研究作者姓名陈龙刚导师姓名、职称霍红卫教授一级学科计算机科学与技术二级学科计算机软件与理论申请学位类别工学硕士提交学位论文日期2014年11月学校代码10701学号1203121618分类号TP39密级公开西安电子科技大学硕士学位论文压缩全文自索引算法的研究作者姓名：陈龙刚一级学科：计算机科学与技术二级学科：计算机软件与理论学位类别：工学硕士指导教师姓名、职称：霍红卫教授提交日期：2014年11月StudyonAlgorithmsforCompressedFull-textSelf-indexesAt

2、hesissubmittedtoXIDIANUNIVERSITYinpartialfulfillmentoftherequirementsforthedegreeofMasterinComputerScienceandTechnologyByLonggangChenSupervisor:Prof.HongweiHuoNovember2014西安电子科技大学毕业论文独创性（或创新性）声明秉承学校严谨的学风和优良的科学道德，本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标注

3、和致谢中所罗列的内容以外，论文中不包含其他人已经发表或撰写过的研究成果；也不包含为获得西安电子科技大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中做了明确的说明并表示了谢意。毕业论文与资料若有不实之处，本人承担一切的法律责任。本人签名：日期：西安电子科技大学关于论文使用授权的说明本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究生在校攻读学位期间论文工作的知识产权单位属于西安电子科技大学。学校有权保留送交论文的复印件，允许查阅、借阅论文；学校可以公布论文的

4、全部或部分内容，允许采用影印、缩印或其它复制手段保存论文。同时本人保证，获得学位后结合学位论文研究成果撰写的文章，署名单位为西安电子科技大学。保密的学位论文在年解密后适用本授权书。本人签名：导师签名：日期：日期：摘要摘要在信息检索领域，基于数据库的条目型检索系统和基于倒排表的检索系统能解决一部分需求，但在字符串精确匹配、生物序列分析、任意模式检索等领域，无法通过数据库系统和倒排表完成。全文索引技术(full-textindex)可以在一定程度上解决这类问题，但是形如后缀数组(suffixarray,SA)和后缀树(suf

5、fixtrie,ST)这样的全文索引结构需要很大的空间，实用性不强。压缩索引(compressedfull-textself-index)技术解决了上述问题，它对原始数据进行压缩表示，所需空间与纯压缩算法相当，而且能够在不需要恢复出原始数据的情况下提供高效的模式匹配功能。本文研究了常见后缀数组构建算法、压缩后缀数组、BitMap、FM-index、熵与编码等方面的知识。在此基础上，设计和实现了高效的压缩索引方案，包含以下三部分。首先，针对常见后缀数组计算方法内存峰值过大、计算速度慢的问题，提出了高效的SA计算方法DCV，

6、具有省内存、速度快的优点，运行时内存峰值为原始数据的5倍左右，运行时间与知名的LS方法相当，总体性能优越。其次，我们针对压缩后缀数组(compressedsuffixarray,CSA)设计了两种高效、简洁的结构：CSA和Adaptive-CSA，分别对数组的差分序列使用gamma编码和自适应的混合编码，理论结果保持了该领域已有理论结果的性能，可以在O(mlogn)的时间内完成count查询，m表示模式长度，可以将原始数据压缩到2nHk(T)+n+o(n)比特，Hk(T)表示原文T的k阶经验熵，结合自适应策越、调优的编

7、码方法、查找表等优化手法，使我们的CSA结构在构建时间、压缩率、查询速度上优于常见CSA结构，在CanterburyCorpus和Pizza&ChiliCorpus上的各项测试结果优势明显。最后，提出了一种高效的BitMap索引结构，对每块数据能自动的选择最佳编码方法，并能根据数据的分布选择最合适的块大小等参数，并以此为基础，结合小波树实现了第二种压缩索引方案Adaptive-FM，充分利用数据分布特点，具有数据感知的能力，理论结果保持了该领域已有理论结果的性能，count查询可以在O(mlog)时间内完成，表示字符

8、表大小，所需空间为2nHk(T)+o(n)log比特，CanterburyCorpus和Pizza&ChiliCorpus数据集上的测试表明Adaptive-FM综合性能优越，特别是压缩率。所开发的压缩索引已工程化，可在https://github.com/chenlonggang/上获取。关键词：后缀数组，压缩全