实时压缩文本索引技术研究与实现

发布时间：2017-11-02 06:24

  本文关键词：实时压缩文本索引技术研究与实现

  更多相关文章： 全文索引 自索引 并行计算 数据压缩 模糊搜索

【摘要】：互联网的不断发展导致网络信息量越来越庞大,这也给信息检索带来了很大的挑战。全文索引技术是搜索引擎、信息过滤等信息检索领域中的关键技术,全文索引是在庞大的文本字符串上建立的一种数据结构,利用该数据结构可以实现对原文本的任意子串进行高效搜索。 传统的全文索引技术首先对原始文本建立索引,然后利用索引和原始文本实现对子串的搜索,所需空间大小是原始文本的4至20倍,造成了巨大的空间浪费。压缩的全文自索引技术是近期研究的热点,该技术仅利用索引即可完成子串搜索,并且可以从索引无损地还原出原始文本,是一种无需存储原始文本的自索引技术,在有些情况下,索引空间消耗不足原文本的50%,这就节省了很大的存储空间,压缩的全文自索引技术达到了很好的时间和空间的平衡。此外,压缩的全文自索引技术直接对二进制数据进行处理,索引的创建过程是与语义无关的,无需进行分词处理,这样就避免了自然语言分词技术带来的麻烦。本文的研究内容和取得的研究成果如下： (1)本文综述了关于压缩的全文自索引技术的典型算法,并在多种数据集上对各种压缩的全文自索引算法进行综合的测试评估,验证了压缩的全文自索引技术的有效性和实用性。 (2)为了支持模糊搜索功能的应用需求,在压缩的全文自索引技术的基础上,研究并实现了支持通配符搜索、编辑距离搜索、正则表达式搜索的文本索引技术,对文本索引技术进行了功能扩展。 (3)设计并实现了高性能文本索引系统,该系统采用可并行的压缩的全文自索引算法RLCSA作为基础解决方案,在众核CPU高性能处理器上可实现多线程并行处理,提高了处理速度。该文本索引系统节省了空间开销,可以对文本进行实时索引,避免了自然语言分词方法的影响,,整个系统的实现是基于Web方式的,可以跨平台运行,满足了对社交网络等实时更新数据对文本索引实时性的需求。
【关键词】：全文索引 自索引 并行计算 数据压缩 模糊搜索
【学位授予单位】：北京邮电大学
【学位级别】：硕士
【学位授予年份】：2014
【分类号】：TP391.1
【目录】：

• 摘要4-5
• ABSTRACT5-9
• 第一章 引言9-14
• 1.1 研究背景与意义9-11
• 1.1.1 大数据时代的兴起带来新的挑战9-10
• 1.1.2 传统文本索引技术的缺陷与不足10-11
• 1.1.3 压缩文本索引技术的特征11
• 1.1.4 新型体系结构的发展11
• 1.2 论文主要内容11-12
• 1.3 论文组织结构12-14
• 第二章 国内外研究现状14-26
• 2.1 经典的文本索引技术14-22
• 2.1.1 后缀树和后缀数组14-17
• 2.1.2 倒排索引17-20
• 2.1.3 中文分词20-22
• 2.2 全文索引系统22-24
• 2.2.1 Lucene22-23
• 2.2.2 Sphinx23
• 2.2.3 Xapian23-24
• 2.3 文本索引技术近期研究进展24-26
• 第三章 压缩的全文自索引技术综述及性能评估26-36
• 3.1 基本概念26-27
• 3.2 压缩的全文自索引算法27-30
• 3.2.1 后缀数组系列28-29
• 3.2.2 FM-Index系列29-30
• 3.2.3 LZ-Index系列30
• 3.3 复杂度比较30-31
• 3.4 实验评估31-35
• 3.4.1 索引建立32
• 3.4.2 计数和定位32-34
• 3.4.3 提取34
• 3.4.4 实验结果小结34-35
• 3.5 本章小结35-36
• 第四章 支持模糊搜索的文本索引技术36-43
• 4.1 通配符搜索36-38
• 4.1.1 算法思想36-37
• 4.1.2 算法描述37-38
• 4.2 编辑距离搜索38-40
• 4.2.1 编辑距离概述38
• 4.2.2 算法思想38-39
• 4.2.3 算法描述39-40
• 4.3 正则表达式搜索40-43
• 4.3.1 正则表达式概述40-41
• 4.3.2 算法思想41
• 4.3.3 算法描述41-43
• 第五章 高性能文本索引系统设计与实现43-53
• 5.1 RLCSA算法43-46
• 5.1.1 算法介绍43-44
• 5.1.2 算法测评44-46
• 5.2 模糊搜索46-47
• 5.3 实时索引47-49
• 5.4 系统总体设计与实现49-51
• 5.4.1 实时索引建立模块50
• 5.4.2 模糊搜索处理模块50
• 5.4.3 查询客户端模块50-51
• 5.5 系统性能对比51-52
• 5.6 本章小结52-53
• 第六章 总结与展望53-55
• 6.1 研究成果总结53-54
• 6.2 下一步工作展望54-55
• 参考文献55-61
• 致谢61-63
• 作者攻读硕士学位期间发表的论文目录63

【参考文献】

中国期刊全文数据库 前6条

1 刘小珠;彭智勇;陈旭;;高效的随机访问分块倒排文件自索引技术[J];计算机学报;2010年06期

2 王晓龙,王开铸,李仲荣,白小华;最少分词问题及其解法[J];科学通报;1989年13期

3 刘源,梁南元;汉语处理的基础工程——现代汉语词频统计[J];中文信息学报;1986年01期

4 刘学文,陶晓鹏,于玉,胡运发;一种全新的全文索引模型——后继数组模型[J];软件学报;2002年01期

5 周水庚,胡运发,关佶红;基于邻接矩阵的全文索引模型(英文)[J];软件学报;2002年10期

6 刘小珠;彭智勇;;全文索引技术时空效率分析[J];软件学报;2009年07期

，

本文编号：1130370