网树求解具有间隙和一次性条件约束的近似匹配

摘要

模式匹配是一个计算机学科中非常基础性和经典性的问题，在诸多领域具有十分广泛地应用，如在文本检索，生物序列分析，数据挖掘以及传感器网络中均有十分重要的应用。
　　在模式匹配的研究过程中，通常需要引入通配符，以方便用户的查询与检索。传统的通配符仅有“?”和“*”分别用来通配单个字符或任意多个字符。但近年来，一种具有间隙约束的模式匹配问题在音乐信息检索、数据挖掘和分类或聚类问题的特征抽取中均具有重要的应用。新的模式匹配问题中模式串P可以描述为p0[min0, max0]p1…[minj-1, maxj-1]pj…[minm-2, maxm-2]pm-1的形式，这里minj-1和maxj-1分别描述字符pj-1和pj可以通配的最小和最大字符的数量。在具有间隙约束模式匹配问题的研究中，一种被称为一次性条件约束的模式匹配具有很大的挑战意义，其是指不允许序列串中某一结点在结果中多次出现。但目前的研究主要是针对精确模式匹配的研究。近似模式匹配是更具实际意义的一项研究。
　　本课题对目前具有间隙约束和一次条件的近似模式匹配问题进行研究，针对目前该问题的求解算法 SAIL-APPROX求解的精度不高问题进行研究，论文首先给出了问题的形式化定义；在此基础上，将该问题转化为一棵网树；之后在网树上建立了一种启发式算法SBO-APP算法，该算法采用两种策略，分别是优化地选取近似出现策略和最右双亲近似出现策略，并从这两个近似出现中，选取对问题影响最小的近似出现作为本次选择的结果，迭代此过程，直到发现所有近似出现后停止。
　　论文通过大量对比性实验进行了验证，充分地说明了该算法在解决近似模式匹配问题中，解的质量的优越性。

目录

封面

声明

中文摘要

英文摘要

目录

第一章 绪论

1.1背景和意义

1.2国内外研究现状

1.3问题介绍

1.4本文结构

第二章 模式匹配研究发展

2.1算法概述

2.2 算法分析

2.3 本章小结

第三章 算法实现与分析

3.1问题定义

3.2提出算法

3.3运行实例

3.4算法复杂度分析

3.5 本章小结

第四章 实验结果与分析

4.1 实验数据说明

4.2 实验结果

4.3本章小结

第五章 结论

5.1 工作总结

5.2 工作展望

参考文献

致谢