一次性序列模式匹配研究进展

摘 要：带通配符的模式匹配问题具有更广阔的应用前景。间隙约束是将通配符的数量设置为一个可变范围，具有更高的灵活性。一次性模式匹配作为带间隙约束模式匹配的一种，能够对匹配结果进行有效的缩减，有着重要的实际应用意义。本文主要综述了目前一次性序列模式匹配相关研究，并对将来的研究工作进行了展望。

关键词：一次性;间隙约束;模式匹配

模式匹配是计算机科学中的一个重要研究方向。带通配符的模式匹配不仅具有理论研究意义，而且在生物基因检测、序列模式挖掘、文本信息搜索等领域具有重要的应用。然而，传统通配符的数目通常是单个或固定值，在间隔不确定字符数时无法适用。而更灵活的间隙约束采用了指定范围来描述模式中的通配符数量，可以表示为P=p1[a1，b1]p2…pj[aj，bj]pj+1…pm1[am1，bm1]pm，其中，[aj，bj]就是间隙约束，aj和bj分别指pj和pj+1之间通配符个数的最小值和最大值[1]。

一次性模式匹配作为带间隙约束模式匹配中的一种，不仅能够对结果集进行有效缩减，而且在序列模式挖掘中具有重要應用[2]。由于间隙约束的存在，每当子模式出现不同的位置，都会产生一个新的出现，从而导致解的空间大小达到指数级。设序列长度为n，模式长度为m，最大间隙为w，则解的空间大小为O（nwm），当模式长度m较大时，所有出现的数量将无法估计。为了解决该问题，武等人[3]研究了一次性条件的模式匹配，一次性条件规定序列中的字符最多只能被匹配一次，解的空间大小降低到O（n/m）。在此基础上，一系列的一次性匹配算法被相继提出，如SBO算法[3]、DCNP算法[4]等。按照间隙类型的不同，一次性模式匹配可分为非负间隙的匹配和一般间隙的匹配。本文将从这两个方面，对目前的一次性匹配算法进行综述。

一、非负间隙的匹配

一次性模式匹配已被证明为NPHard问题，现有的研究无法得到完备解。因此，研究者们均从解的完备性和时间效率两方面进行不断平衡。目前一次性模式匹配的求解方法可大致分为三类：二维表结构、位并行方法、树或图结构。

非负间隙约束满足0≤ai≤bi，在求解这类模式匹配问题时，最直接的方法是用二维表结构进行求解，通过对二维表的构建和回溯来搜索一次性出现。这类算法的特点是能够在线求解，具有较快的求解速度，但是容易陷入局部最优而丢解。而位并行的方法则是利用计算机字位运算的内在并行性，能够进一步提高匹配效率，但在求解数量上相比二维表结构的方法并未提高。为了提高算法的求解质量，有研究者将模式匹配转换为树或图中的路径搜索问题，得到了较好的结果。例如，武等人[3]利用网树结构提出一种离线求解算法SBO，该算法通过计算局部最优和全局最优，提高了一次性条件下解的个数。这类算法能够得到更多的解，但由于存在大量的耗时计算，导致算法的求解效率不高。

二、一般间隙的匹配

非负间隙忽略了字符颠倒的情况，在某些领域中使用受到限制。例如，在实际的购买序列中，<鼠标，键盘>和<键盘，鼠标>可以认为是同一购买行为。为了提高间隙约束的灵活性，有研究者开展了一般间隙下的模式匹配研究。一般间隙允许存在ai<0或者bi<0的情况，如P=a[1，2]g[2，1]t就是一般间隙下的模式，这样的模式能够发现更多隐藏的信息，但是求解难度更大。武等人[5]对一般间隙转化为非负间隙的模式进行了理论研究，并利用子网树结构提出一种SETS算法，能够对一般间隙下的模式匹配进行快速求解。然而该算法只能计算完全匹配数，出现数量巨大，并且不能输出具体的出现位置。为解决该问题，柴等人[4]在一般间隙的模式匹配问题中引入一次性条件，由于一次性条件限制了字符的使用次数，导致在一般间隙下存在形如<1，2，1>的内部重复问题。于是，引入一种Checking检测机制对该问题进行有效的解决，并提出一种基于结点动态更新的DCNP算法。该算法不仅能够对出现集进行有效缩减，而且能够计算出一般间隙模式的具体出现位置，具有更广阔的应用前景。

三、总结与展望

本文主要对一次性序列模式匹配进行了详细综述。首先对带间隙约束的模式匹配进行了介绍，然后从非负间隙和一般间隙两个角度，对一次性模式匹配的相关研究进行了详细分析。最终我们发现，目前的一次性模式匹配都是在力求找到更多解的同时，提高求解效率，但均未实现完备性求解。如何更加高效地处理一次性模式匹配问题，仍然需要进一步的研究。同时，现有的研究大多都将字符的效用视为均等，而基于高效用的一次性模式匹配工作则更加具有实际意义，这也需要进一步的研究探讨。

参考文献：

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

[2]Wu Y，Wang L，Ren J，et al.Mining sequential patterns with periodic wildcard gaps[J].Applied Intelligence，2014，41（1）：99116.

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

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

[5]武优西，刘亚伟，郭磊，等.子网树求解一般间隙和长度约束严格模式匹配[J].软件学报，2013，24（5）：915932.

作者简介：于磊（1994—），男，汉族，河北深州人，硕士，学生，研究方向：模式挖掘。