范金泉 张楠

摘 要：模式匹配应用于求解模式在序列中的支持度，是序列模式挖掘的基础问题，也是多种领域的重点研究方向。具有间隙约束的模式匹配相对传统的模式匹配更具灵活性和挑战性，在生物学、信息检索、网络安全等领域都有着广泛研究。本文总结了近几年来带间隙约束的模式匹配的研究进展与成果，分析了其中有代表性的算法，最后对带间隙约束的模式匹配的未来发展趋势进行了展望与总结。

关键词：模式匹配;间隙约束;支持度

模式匹配在数据搜索、音乐信息检索和生物信息学等领域有着非常重要的作用。但随着数据的不断变化，传统的通配符数量不变的模式匹配无法满足用户的需求，提出了具有间隙的模式匹配（通配符的数量有上下界）。具有间隙的模式匹配不仅更加灵活多样，富有挑战性[1]。根据出现的不同，常见的约束条件有三种：无特殊条件、一次性条件和无重叠条件。本文将从这三个方面，对带有约束条件的间隙约束模式匹配进行分析讨论。

一、无特殊条件下的间隙模式匹配

例1 假设序列S=s1s2s3s4s5s6=ATATTA，模式P=A[0，1]T[0，1]A。

无特殊条件下序列中的任意字符可以被多次使用，因此可以找到三个出现<1，2，3>，<3，4，6>，<3，5，6>。无特殊条件对出现没有限制，因此会得到大量的解，提高求解的速度将是无特殊条件最为关心的一点。PAIG算法采用三维数据表求解无特殊的间隙模式匹配，速度方面有很大提升，但随着序列的增长空间消耗会非常大。为了提高算法的空间利用率，提出了网树结构，该结构与树型结构类似，不同点在于网树中存在多个根结点并且相同结点可能会出现在不同层，基于此结构提出的NAMIC算法在运行空间消耗有着很大的提升。……