| 题名 | 基于索引的压缩文本查找算法研究及其并行化实现 |
| 作者 | 李开士 |
| 学位类别 | 博士 |
| 答辩日期 | 2007-06-11 |
| 授予单位 | 中国科学院软件研究所 |
| 授予地点 | 软件研究所 |
| 关键词 | 压缩 自索引 FM-index 分块 并行 |
| 中文摘要 | 摘要 压缩查询是近几年兴起的一种文本模式查找技术，它是通过查找压缩文本实现初始文本的查找。在最初的时候，压缩查询是在线的，也就是在压缩文本上直接执行模式子串的匹配操作。对于海量的文本，在线的压缩查询不能满足性能要求，于是将压缩和索引结合起来形成了压缩索引的文本查询。文本索引一般包含两种类型：单词索引和全文索引。单词索引只能检索文本中的单词，而全文索引可以检索任意字符串。自索引是一种完全的索引，它完全包含索引的文本数据。 FM-index是一种压缩的自索引结构，可以实现全文检索。FM-index在简单查询和索引空间占用方面达到了很好的性能，但是在建立索引时却要消耗很大的内存，并且很难处理复杂查询，于是我们提出了一种重叠分块的FM-index索引结构，并且使用MPI对重叠分块FM-index的建立和查询实现了并行化。我们通过实验发现重叠分块的FM-index很好的解决了建立时内存占用过多的问题，它占用的内存跟文本数据量大小没有关系，只跟分块大小有关；它相对于原来的FM-index在复杂查询方面性能也有所改进；同时它占用的存储空间跟原来FM-index的大致相等。重叠分块FM-index的并行化也取得了较好的加速比效率，具有较好的可扩展性。 |
| 语种 | 中文 |
| 公开日期 | 2011-03-17 |
| 页码 | 60 |
| 内容类型 | 学位论文 |
| 源URL | [http://ir.iscas.ac.cn/handle/311060/6534]  |
| 专题 | 软件研究所_中科院软件所_中科院软件所 |
| 推荐引用方式 GB/T 7714 | 李开士. 基于索引的压缩文本查找算法研究及其并行化实现[D]. 软件研究所. 中国科学院软件研究所. 2007. |
| 个性服务 |
| 查看访问统计 |
| 相关权益政策 |
| 暂无数据 |
| 收藏/分享 |
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。
修改评论