编辑距离下具有间隙约束的近似模式匹配

摘要

模式匹配问题在计算机科学中出现的最早且人们对它的研究也最广泛，随着需要处理的文本规模越来越大，在文本中进行的搜索越来越复杂，模式和文本之间可以有某些细小不同的近似模式匹配问题得到了广泛的应用。但对具有间隙约束的近似模式匹配问题的研究目前尚未成熟，因此，论文针对此问题展开研究和实现。
　　论文将目标问题分成两个方面进行具体的研究以及方法实现。一是字符串的近似匹配问题，二是模式之间存在间隙约束的匹配问题。在字符串的近似匹配方面，论文首先对基本字符串匹配的一些相关知识进行了介绍，包括字符串匹配的概念以及传统字符串匹配的方法。接着对近似串的匹配方法进行了研究，包括：动态规划方法、基于自动机的方法、位并行方法以及基于文本过滤的方法。通过对这四种方法进行研究和对比，本文将动态规划方法作为近似串匹配的主要方法，将编辑距离模型作为衡量字符串相似度的模型，并对编辑距离矩阵的建立以及字符串之间编辑距离的计算进行了方法实现。在具有间隙约束的模式匹配方面，本文首先对文本串进行了预处理，将文本串保存为纯文本文档的形式，利用Lucene对纯文本文档建立倒排索引的方式为文本串中的每个字符串建立索引，这种索引包含了该字符串所有的出现位置及出现次数，然后在索引基础上通过Lucene中SpanNearQuery的搜索机制对具有间隙约束的模式串进行搜索。此方法摒弃了普通顺序方法因文本过大而造成的匹配时间代价高的缺陷，大大提高了匹配效率。
　　最后，论文将此方法和普通的顺序匹配算法进行了对比，在保证相同文本、相同模式和相同匹配结果的情况下，经过大量实验以及对实验结果的分析，得出当文本较大且不易变动时，本算法以合理的空间消耗换取了时间的绝对性缩减，比普通顺序算法有明显的优势。

目录

封面

声明

中文摘要

英文摘要

目录

第一章 绪论

1.1 研究背景及意义

1.2 课题的研究现状

1.3 文本的主要研究内容

1.4 本文结构

第二章 基本字符串匹配

2.1 字符串匹配基本概念

2.2 字符串匹配的经典方法分析

2.3 代表性算法分析

2.4 本章小结

第三章 近似串匹配概述

3.1 基本理论知识

3.2 动态规划方法

3.3 自动机方法

3.4 位并行方法

3.5 文本过滤方法

3.6 本章小结

第四章 具有间隙约束的近似模式匹配

4.1 问题概述

4.2 基于lucene倒排索引的匹配算法

4.3 顺序匹配算法

4.4 实验结果与分析

4.5 本章小结

第五章 多功能文本编辑系统

5.1 系统简介

5.2 系统功能说明

5.3 本章小结

第六章 总结

6.1 工作总结

6.2 工作展望

参考文献

研究生期间主要科研工作及成果

致谢