具有间隙约束的模式匹配研究发展

范金泉 张楠

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

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

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

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

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

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

二、一次性条件下的间隙模式匹配

一次性条件下要求序列中的字符只能被使用一次，在例1中，<1，2，3>是一个出现，则<3，4，6>就不是一个出现，因为s3使用了两次。一次性条件对结果集进行了很大程度的缩减，但会出现丢解的现象，原因在于一次性约束的模式匹配算法是基于回溯搜索，在回溯点上的选择至关重要，SAIL算法是代表性的一次性模式匹配算法，可以在线求解一次性问题，但在局部最优方面处理较差。针对求解的质量问题，武等人[2]利用网树设计了SBO算法，采用局部全局最优解，增加了一次性条件的解集。在此基础上，柴等人[3]提出了IM_DCNP算法，通过深度优先遍历网树，解决了一次性约束下的一般间隙的近似模式匹配，具有良好的优越性。

三、无重叠条件下的间隙模式匹配

无重叠条件是指允许序列中的任意位置的字符重复使用，但不允许同一字符在相同位置多次使用[4]，所以例1中对应的无重叠出现有<1，2，3>和<3，4，6>，虽然s3被使用了两次但是是在不同的子序列中。文献[4]通过网树结构解决了无重叠模式匹配中无法求得完备解的问题。在此基础上，将网树应用到无重叠条件下序列模式挖掘中也取得优异的效果[5]。

从上述研究可以看出，无特殊结果是一个全集，则无重叠条件和一次性结果属于全集中的不同子集，网树结构用于求解这三种条件下的间隙模式匹配是非常有优势的。无重叠条件下的模式匹配问题属于P问题，通过遍历网树便可以求得完备解，然而一次性条件的模式匹配属于NPhard问题，采用迭代方式可以进行简化，因此，使用启发式策略求解一次性问题是关键。无特殊问题相对比较容易处理，是其他两种约束条件的关键问题。

四、总结

将间隙约束引入到模式匹配中使得模式匹配问题更加灵活多变，更富有挑战性。同时，不同的约束条件与模式匹配结合，能更好地满足用户需求。本文对带间隙约束的无特殊、一次性、无重叠条件下的模式匹配进行了分析介绍，对每种约束条件进行了总结并分析讨论几种求解算法。目前，带间隙约束的模式匹配发展迅速，但是在解的质量和实际应用方面仍存在不足之处，是未来进一步的发展趋势。

参考文献：

[1]Shi Q，Shan J，Yan W，et al.NetNPG：Nonoverlapping pattern matching with general gap constraints[J].Applied Intelligence，2020.

[2]武优西，吴信东，江贺，等.一种求解MPMGOOC问题的启发式算法[J].计算机学报，2011，34（8）：14521462.

[3]柴欣，贾晓菲，武优西，等.一般间隙及一次性条件的严格模式匹配[J].软件学报，2015，26（5）：10961112.

[4]Wu Y，Shen C，Jiang H，Wu X.Strict pattern matching under nonoverlapping condition[J].Science China Information Sciences.2017，60（1）：012101.

[5]Wu Y，Tong Y，Zhu X，Wu X.NOSEP：Nonoverlapping sequence pattern mining with gap constraints[J].IEEE Transactions on Cybernetics.2018，48（10）：28092822.

作者簡介：范金泉（1993—），男，汉族，山东临沂人，硕士，学生，研究方向：序列模式与挖掘;张楠（1991—），女，汉族，山东济宁人，硕士，学生，研究方向：铁路信息技术。