一般间隙和长度约束的严格近似模式匹配

摘要

模式匹配（也称为串匹配）是计算机科学中基本问题之一，在诸多研究领域都有着十分广泛的应用。近年来具有间隙约束的模式匹配在音乐信息检索和序列模式挖掘中得到了应用。在模式匹配中，有的仅仅考虑最后一个模式子串在序列中匹配的位置，这种模式匹配称为宽松模式匹配；更为挑战性的问题是对每个模式串均考虑其在序列串中匹配的位置，而这种模式匹配称为严格模式匹配。严格模式匹配问题能够计算出在给定序列中某种模式的出现频度，进而判定该模式的频繁性，因此严格模式匹配问题是具有间隙约束的序列模式挖掘问题的核心工作之一。在具有间隙约束的模式匹配问题中模式P可以描述为p0[min0, max0]p1…[minj-1, maxj-1]pj…[minm-2, maxm-2]pm-1的形式，这里的minj-1和maxj-1分别描述字符pj-1和pj之间可以通配的最小和最大字符的数量，更为一般性的研究是模式P中的字符pj-1和pj之间的间隙值可以为负。目前模式匹配问题主要是针对精确模式匹配的，而在实际研究过程中更多情形属于近似模式匹配，因此与精确模式匹配相比，近似模式匹配是更为一般性的问题。
　　本文对更具有一般性的严格近似模式匹配进行研究，提出了Hamming距离下间隙约束值可以为负值的一般间隙以及长度约束的严格近似模式匹配问题。论文首先给出了该问题的形式化定义；在此基础上，证明了一个SAP问题实例可以转换为指数个对应精确模式匹配问题实例；论文将SAP问题转化为一棵子网树并运用子网树结构设计了一个有效的在线求解算法并证明了算法的完备性，并分析了SETA算法的时间复杂度和空间复杂度分别是O(m×Maxlen×W×d)和O(Maxlen×W×m2×n×d)，这里的m, n, Maxlen, W和d分别表示的是模式串和序列串的长度，最大长度约束，模式P中最大间隙和近似度约束；最后，论文通过实验验证了影响SAP问题不同的参数对SETA算法的求解时间以及解大小的影响。大量的实验结果验证了SETA算法的正确性和有效性。

目录

封面

声明

中文摘要

英文摘要

目录

第一章 绪论

1.1 课题的研究背景和意义

1.2 国内外研究现状

1.3 本文主要研究内容及特色

1.4 本文结构安排

第二章 模式匹配的概述

2.1 具有间隙约束的模式匹配问题概述

2.2 具有间隙约束的模式匹配问题分类

2.3 几种模式匹配算法分析

2.4 本章小结

第三章 SAP问题及子网树求解方法

3.1 SAP问题定义

3.2 子网树

3.3 SETA算法设计及分析

3.4 运行实例

3.5 本章小结

第四章 实验结果与分析

4.1 实验环境及数据

4.2 SETA算法正确性验证

4.3 SETA算法有效性验证

4.4 性能评估

4.5 本章小结

第五章 结论

5.1 总结

5.2 展望

参考文献

攻读学位期间所取得的相关科研成果

致谢