基于索引的压缩文本查找算法研究及其并行化实现

ISCAS OpenIR > 中科院软件所 > 中科院软件所

	基于索引的压缩文本查找算法研究及其并行化实现
	李开士
	2007-06-11
学位授予单位	中国科学院软件研究所
学位	博士
学位授予地点	软件研究所
关键词	压缩自索引 Fm-index 分块并行
摘要	摘要压缩查询是近几年兴起的一种文本模式查找技术，它是通过查找压缩文本实现初始文本的查找。在最初的时候，压缩查询是在线的，也就是在压缩文本上直接执行模式子串的匹配操作。对于海量的文本，在线的压缩查询不能满足性能要求，于是将压缩和索引结合起来形成了压缩索引的文本查询。文本索引一般包含两种类型：单词索引和全文索引。单词索引只能检索文本中的单词，而全文索引可以检索任意字符串。自索引是一种完全的索引，它完全包含索引的文本数据。 FM-index是一种压缩的自索引结构，可以实现全文检索。FM-index在简单查询和索引空间占用方面达到了很好的性能，但是在建立索引时却要消耗很大的内存，并且很难处理复杂查询，于是我们提出了一种重叠分块的FM-index索引结构，并且使用MPI对重叠分块FM-index的建立和查询实现了并行化。我们通过实验发现重叠分块的FM-index很好的解决了建立时内存占用过多的问题，它占用的内存跟文本数据量大小没有关系，只跟分块大小有关；它相对于原来的FM-index在复杂查询方面性能也有所改进；同时它占用的存储空间跟原来FM-index的大致相等。重叠分块FM-index的并行化也取得了较好的加速比效率，具有较好的可扩展性。
其他摘要	Abstract Compressed query is a new approach to text pattern matching problems, which achieves its goal through querying on compressed text. At its early stage, compressed query is on-line, i.e., to directly scan on compressed text from the beginning to the end. However, for massive volume data, this is not enough. Thus index is introduced into compressed query. There’re two kinds of text index-one is word-based index and the other one is full-text index. Word-based index can be used to querying words in text, while full-text index can support any string matching in text. Self-index is an index that contains the full text information in the index. FM-index is a compressed self-index and also is a full-text index. It occupies small storage space and is very quick when dealing with simple query. But it needs a lot of memory to build the index and is difficult to support complex query. To solve those problems, we designed an overlapping blocked FM-index algorithm and parallelized it with MPI. Through experiments, we found that overlapping blocked FM-index algorithm realized our goals. During building period, its memory occupation doesn’t depend on the volume size of the text, but depends on the block size. Compared to the original FM-index algorithm, overlapping blocked FM-index algorithm consumes less time to handle complex query. The storage space of overlapping blocked FM-index algorithm is almost equal to its original version. The parallel version of overlapping blocked FM-index algorithm achieved acceptable speedup and well scalability.
页数	60
语种	中文
内容类型	学位论文
URI标识	http://ir.iscas.ac.cn/handle/311060/6534
专题	中科院软件所_中科院软件所
推荐引用方式 GB/T 7714	李开士. 基于索引的压缩文本查找算法研究及其并行化实现[D]. 软件研究所. 中国科学院软件研究所,2007.

条目包含的文件
文件名称/大小	文献类型	版本类型	开放类型	使用许可
10001_20032801500432（559KB）			限制开放	--	请求全文