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

RESEARCH ON COMPRESSED FULL-TEXT SELF-INDEX ALGORITHMS

作　　者：路炜[1,2] 刘燕兵[3] 王春露[1] 刘庆云[3] 郭莉[3] 

机构地区：[1]北京邮电大学计算机学院,北京100876 [2]河北师范大学附属民族学院,河北石家庄050091 [3]中国科学院信息工程研究所信息内容安全技术国家工程实验室,北京100093

出　　处：《计算机应用与软件》2014年第3期11-15,35,共6页Computer Applications and Software

基　　金：国家自然科学基金项目(61202477);国家高技术研究发展计划项目(2011AA010703);中国科学院战略性先导专项(XD06030602);河北省教育厅科研项目(QN20131164)

摘　　要：针对传统全文索引技术空间浪费过大等问题,介绍压缩的全文自索引技术。该技术仅利用索引数据即可完成子串搜索,并且可以从索引数据无损地还原出原始的文本信息,是一种无需存储原始文本信息的"自索引"技术,从而大大节省存储空间。综述现有的十几种典型的压缩的全文自索引算法的基本思想及其实现,并在多种数据集上对这些算法进行综合的测试评估。实验结果表明,压缩的全文自索引技术有效地节省了空间开销,实用价值较高。Traditional full-text index technology wastes huge space. In order to solve this problem, we introduce the compressed full-text self-index technology. By only employing index data it can implement the substring search. In addition, it can also restore original text information losslessly from the index data, thus is a ＂self-index＂ technology without the need of storing original text information, and therefore greatly saves the storage space. In this paper, we give the review on dozens of existing typical compressed full-text self-index algorithms in both the theories and the practices, and carry out comprehensive test and evaluation on them on different datasets. Experimental results show that the eompressed full-text self-index technologies save the space consumption effectively and have higher practical value as well.

关 键 词：全文索引 数据压缩 自索引 后缀数组 BWT变换 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]