无重叠条件下严格模式匹配的研究

【摘要】：序列模式挖掘是数据挖掘分支,而序列模式匹配是序列模式挖掘的重要基础。将挖掘方法用于生物序列、顾客购买序列、网络日志的分析,我们可从大数据中获取各种潜在的规律和感兴趣的信息。在这些研究中,带有通配符间隙约束的生物序列匹配和挖掘比传统的串匹配方法更具有挑战性,且衍生出诸多种类的条件和约束。有一种方法是建立在无重叠条件基础上的模式匹配,该问题是当给定具有间隙约束的模式串时,在给定的序列中找到满足无重叠约束的最多出现,而无重叠出现是指任何两个出现中不能在相同位置处使用相同字符。因此本文对无重叠约束的严格模式匹配问题进行研究。本文的主要研究内容和相关工作如下:(1)给出了无重叠约束模式匹配的严格形式化定义;(2)理论证明了无重叠约束模式匹配的计算复杂性是P的,即无重叠约束模式匹配是具有多项式时间的确定性算法来求解的判定问题;(3)采用网树结构构造了完备性求解算法NETLAP-Best算法;(4)大量对比性实验验证了NETLAP-Best算法的正确性与有效性。综上,本文不但理论证明了无重叠条件下严格模式匹配问题的计算复杂性为P,而且提出了有效地完备性求解算法NETLAP-Best算法,大量实验不但验证了该算法的完备性,而且验证了其较INSgrow是更为高效的算法。
【关键词】：模式匹配 间隙约束 无重叠 网树
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：TP311.13