模式匹配（也称为串匹配）是计算机科学中基本问题之一，已经广泛地应用到了生物研究、音乐信息检索和序列模式挖掘等各个领域。同时也是序列模式挖掘技术的核心与基础，模式匹配最新研究之一是具有间隙约束的模式匹配问题。序列模式挖掘（Sequence Pattern Mining）是数据挖掘的重要组成部分，主要任务是发现序列数据库中频繁出现的子序列，并且在诸多领域具有广泛的应用。传统的序列模式挖掘具有盲目性，导致挖掘结果冗余并且效率低下，因此衍生出多种类型的条件和约束有针对性地进行挖掘。间隙约束的序列模式挖掘问题具有广泛的应用价值，是目前的研究热点。 本研究首先通过对无特殊条件、一次性条件和无重叠条件等三种间隙约束的模式匹配的求解算法进行优缺点对比分析，选取有代表性的数据集和对比算法，设计了大量的对比实验，从算法的挖掘结果和挖掘效率两方面对实验结果进行了分析。根据出现的不同约束要求，间隙约束的序列模式挖掘可以分为无特殊条件、一次性条件和无重叠条件。由于精确匹配要求每个字符必须匹配，一定程度上限定了匹配的灵活性。为此本研究提出 了 无 重 叠 约 束 的 近 似 模 式 匹 配 问 题 (Approximate Pattern matching with Non-Overlapping constraints , APNO），并运用网树结构解决该问题,提出了 NETLOR和 NETROL 算法。该算法在求解时，先将模式匹配问题转换为一棵网树，然后在网树中每次查找树根叶子路径，并将该路径所对应的解作为一个无重叠近似出现，之后依据树根叶子路径在网树的局部范围内进行快速剪枝，为下一次查找树根叶子路径做准备。最后大量实验验证了本文提出的2个算法的正确性，并且验证了 NETLOR 是更为高效的算法。通过前期的网树结构研究，对间隙约束的序列模式挖掘的核心问题进行对比性研究，通过实验，验证了无重叠的序列挖掘可以同时实现Apriori性质和完备性的统一，同时该算法具有较好的挖掘速度。

哈尔滨商业大学

该项目为储备库项目资源，暂无效益分析内容。