字符串词典压缩索引算法研究

发布时间：2017-08-11 11:00

  本文关键词：字符串词典压缩索引算法研究

  更多相关文章： 字符串词典 压缩索引 外存算法 大数据处理

【摘要】：近年来，随着互联网的迅猛发展和移动设备的大量普及，尤其是大数据时代的到来，越来越多的数据需要处理，其中文本数据占据着越来越大的比重，如何对大规模文本数据进行高效地存储和索引成为一个新的挑战。面对这一挑战，主要有两种解决思路：一种是对数据进行空间上的压缩，使得在相同存储资源的情况下，能存储和处理更多的数据；另一种是设计更加高效的外存算法和数据结构，把数据放在外存，每次只读取需要的部分到内存中进行处理，确保高效的I/O操作。 字符串词典索引作为文本索引的基础，其应用无所不在，如地理信息系统、网络搜索引擎、信息检索系统等。大数据时代大规模的文本数据同样对字符串词典索引提出了新的挑战。本文从空间压缩和外存索引两方面对字符串词典索引算法进行研究，其主要研究工作如下： (1)针对现有的字符串词典索引空间占用普遍较大的问题，提出了一种新的字符串词典压缩索引S-trie，实现了字符串词典索引的压缩，即在对原始字符串词典数据进行索引以支持快速查找的同时，，实现了对原始字符串词典数据的压缩。通过实验对比，证明了S-trie在空间性能方面的优势，S-trie的压缩比达到原始数据的30%。 (2)针对外存磁盘环境，对S-trie进行改进，提高数据的本地引用，使其在外存环境下具有高效的I/O操作，提出了一种字符串词典外存压缩索引SB-trie。SB-trie继承了S-trie空间占用小的优点，同时具有良好的本地引用性能，可以高效地工作在外存磁盘环境。实验表明，SB-trie在空间占用上优于现有的索引，同时在数据量较大的情况下，也具有良好的查找时间性能。
【关键词】：字符串词典 压缩索引 外存算法 大数据处理
【学位授予单位】：苏州大学
【学位级别】：硕士
【学位授予年份】：2014
【分类号】：TP391.1
【目录】：

• 中文摘要4-5
• Abstract5-9
• 第一章 绪论9-14
• 1.1 研究背景与意义9-11
• 1.2 研究现状11-12
• 1.3 本文研究内容12
• 1.4 本文组织结构12-14
• 第二章 字符串词典外存索引概述14-25
• 2.1 问题定义14
• 2.2 基础算法和数据结构14-19
• 2.3 外存模型和算法19-22
• 2.3.1 外存模型19
• 2.3.2 前缀编码的 B+tree19-20
• 2.3.3 String B-tree 索引20-21
• 2.3.4 B-trie 索引21-22
• 2.4 缓存无关模型和算法22-24
• 2.5 本章小结24-25
• 第三章 文本压缩索引概述25-38
• 3.1 数据压缩相关的基础算法和数据结构25-30
• 3.2 全文压缩索引30-35
• 3.2.1 FM 索引31-32
• 3.2.2 压缩后缀数组32-33
• 3.2.3 LZ 索引33-35
• 3.3 字符串集合的压缩索引35-37
• 3.3.1 基于前缀编码的方法35-36
• 3.3.2 基于 RePair 编码的方法36
• 3.3.3 基于 FM 索引的方法36-37
• 3.4 本章小结37-38
• 第四章 字符串词典压缩索引 S-trie38-48
• 4.1 S-trie 索引38-43
• 4.1.1 S-trie 数据结构38-41
• 4.1.2 S-trie 构造算法41
• 4.1.3 S-trie 准确查找算法41-43
• 4.2 S-trie 实现细节43-45
• 4.3 实验45-47
• 4.3.1 实验环境45
• 4.3.2 实验结果45-46
• 4.3.3 实验分析46-47
• 4.4 本章小结47-48
• 第五章 字符串词典外存压缩索引 SB-trie48-60
• 5.1 S-trie 的下界查找操作48-53
• 5.1.1 下界查找操作的定义48
• 5.1.2 下界查找操作48-50
• 5.1.3 S-trie 的下界查找辅助过程实现50-53
• 5.2 SB-trie 索引53-55
• 5.2.1 SB-trie 数据结构53
• 5.2.2 SB-trie 的构造算法53-55
• 5.2.3 SB-trie 的查找算法55
• 5.3 实验55-59
• 5.3.1 实验环境56
• 5.3.2 实验结果和分析56-59
• 5.4 本章小结59-60
• 第六章 总结与展望60-62
• 6.1 本文工作总结60-61
• 6.2 未来工作展望61-62
• 参考文献62-67
• 攻读硕士学位期间取得的科研成果67-68
• 致谢68-69

【参考文献】

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

1 阚君满;;基于改进哈夫曼编码的全文索引结构压缩算法[J];吉林大学学报(信息科学版);2011年05期

2 申展;江宝林;陈yN;唐磊;胡运发;;全文检索模型综述[J];计算机科学;2004年05期

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

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

本文编号：655715