论文部分内容阅读
模式匹配Pattern matching（也称串匹配String matching)是复杂性理论中研究最广泛的问题之一，它是网络安全、信息检索与过滤、文字处理、数据库查询、音乐检索、计算生物学等重要领域的核心问题，同时也是序列模式挖掘技术的核心与基础。目前学术界又重新对字符串匹配提起了兴趣，尤其是人类基因组计划的实施，计算生物学的兴起，又将字符串匹配推到了高潮。为了更好地满足用户对模式灵活设置，在传统的模式中加入通配符约束，使问题变得更复杂。虽然目前允许对通配符进行约束，但研究方向主要侧重于对间隙值为正的有序模式匹配，然而间隙值为负的更为一般的模式匹配问题更具普遍意义，且求解难度更大，本文针对以上研究现状进行分析，做了如下工作：(1)基于前人的研究工作，提出了更具一般性的模式匹配，即一般间隙和长度约束的严格模式匹配(Strict Pattern Matching with General Gaps and Length Constrains,简称SPANGLO)：此匹配强调严格精确；文本串中的字符可以使用多次；模式串中可以含有多个负间隙；对匹配结果的长度进行了约束。(2)深入分析了一般间隙和正间隙之间的关系，并给出了转换方法，并实验验证了这种转换方法的正确性。尽管这种转换方法可以将SPANGLO问题转换为多个已解决的正间隙模式匹配问题，但是这样的转换方法过于复杂，最坏情况下，一个SPANGLO问题可以产生出指数个正间隙模式匹配问题。(3)在借鉴网树概念的基础上，提出了子网树的概念，利用子网树计算模型对SPANGLO问题进行求解；提出了SubnettreeSpanglo(SETS)算法，并给出了算法的正确性和完备性证明，深入分析了算法的时空复杂度分析，并用实验验证了本算法的高效性。(4)本文针对SPANGLO问题设计了一个模式匹配计算原型系统，将具有间隙的模式匹配算法集成到此系统之中，便于今后更方面更深入的研究。