基于通配符和长度约束的近似模式匹配问题研究

摘要

近年来,随着生物信息计算、网络入侵检测、文本检索等领域数据量的激增,如何从中快速地提取用户感兴趣的信息成为了一项重要的研究课题,而模式匹配与挖掘是其中的重要组成部分,引起了国内外研究学者的广泛关注。　　为了增加用户模式查询的灵活性,通配符和长度约束的概念先后被引入模式匹配问题中。本文首先针对带有通配符和长度约束的近似模式匹配问题进行研究,用户可以自行定义模式字符间通配符的范围、模式的最短长度和最大长度以及允许出现的编辑误差。对该问题的研究,不仅完善了近似模式匹配中通配符的引入问题,而且在许多实际领域同样具备应用价值。随后,本文将该问题扩展至带有通配符和One-off条件的近似模式挖掘,解决了带间隔约束和误差的频繁模式挖掘问题。　　本文的研究工作主要包括以下三个方面:　　(1)根据文本字符是否满足One-off条件,针对带有通配符和长度约束的近似模式匹配问题分别提出了APM算法和APM-OF算法,并与同类算法Sail-Approx进行实验对比,结果表明APM和APM-OF算法解的平均增长率分别达到了12.37％和8.34%。同时,对影响算法性能的三个主要参数进行了实验与分析,发现当编辑误差k较大,模式P中字符(非通配符)的个数m适中,局部长度约束下限N很小或很大时解的增长率最为明显,可分别达到31.43%和18.78%。　　(2)将APM-OF算法扩展至带有通配符和长度约束的近似模式挖掘,提出了MAP算法。在与OneoffMining算法的实验对比中,结果显示MAP算法挖掘出的频繁模式个数约为OneoffMining算法的2.07倍。　　(3)构建了解决带有通配符和长度约束的近似模式匹配和挖掘问题的原型系统,并通过实例对系统进行演示说明,为模式匹配和挖掘进一步的研究提供了一个良好的平台。

目录

封面

声明

中文摘要

英文摘要

致谢

目录

插图清单

表格清单

第一章 绪论

1.1 引言

1.2 课题来源和研究内容

1.3 内容组织

1.4 本章小结

第二章 模式匹配研究概述

2.1 概述及分类

2.2 精确模式匹配问题

2.3 近似模式匹配问题

2.4 本章小结

第三章 模式挖掘研究概述

3.1 频繁模式挖掘

3.2 带通配符和长度约束的近似模式挖掘

3.3本章小结

第四章 基于编辑距离矩阵的近似模式匹配研究

4.1 问题定义

4.2 EDM编辑矩阵构造方法

4.3 APM（Approximate Pattern Matching with EDM）算法

4.4 APM-OF（Approximate Pattern Matching with EDM under One-off condition）算法

4.5 运行实例

4.6 算法时空复杂度分析

4.7 实验对比与分析

4.8 本章小结

第五章 基于APM-OF的频繁模式近似挖掘研究

5.1 问题定义

5.2 MAP（Mining Approximate Patterns）算法

5.3 实验结果与分析

5.4 本章小结

第六章 原型系统演示

6.1 系统简介

6.2 系统实现

6.3 本章小结

第七章 结束语

7.1 本文总结

7.2 工作展望

参考文献

攻读硕士学位期间参与科研项目和发表的论文