靳超艳 刘靖宇



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

靳超艳 刘靖宇

河北工业大学计算机科学与软件学院，天津 300401

模式匹配（也称为字符串匹配）是计算机科学的经典问题之一，也是众多交叉学科解决技术问题的关键。具有间隙约束的序列模式匹配已成为模式匹配问题中的研究热点，在很多领域有着广泛应用，如生物学中DNA序列的研究、音乐领域音符信息的检索以及目前研究火热的大数据领域等，因此具有间隙约束的模式匹配问题是诸多领域的基础，具有很高的研究价值和意义。因此，总结了近年来具有间隙约束的模式匹配的成果和进展，对具有间隙约束的模式匹配的发展趋势进行了展望，以便对具有间隙约束的模式匹配问题做进一步研究。

模式匹配；间隙约束；研究进展

引言

近年来，随着科学技术的迅猛发展，人类进入了信息社会。人类社会产生的数据量与日俱增，在很多领域涌现出大量的序列数据。如何对这些序列数据进行分析和挖掘以提取有价值的信息，是目前人们比较关注的问题。数据挖掘技术的基础就是模式匹配问题。

模式匹配也称为字符串匹配。此问题描述的是从序列串中找到与模式串P相匹配的出现的个数或者出现的位置。其中，序列串S和模式串来自同一个字符集。具有间隙的模式匹配问题的研究较早，所研究的模式串间隙都是单个可变间隙，例如Manber等人[1]为解决单个可变间隙的模式匹配问题提出了有效算法。然而随着科技的快速发展，单一可变通配符的模式匹配已经不能满足现实应用。因此，多个可变间隙的模式匹配问题成为研究热点，近年来受到越来越多研究者的关注。

1 具有间隙约束的模式匹配

具有间隙约束的模式匹配问题主要可以从以下几方面进行分类：非负间隙约束或者一般间隙约束、宽松模式匹配或者严格模式匹配、精确匹配或者近似匹配、是否对出现有特殊约束条件。

1.1 间隙类型

具有间隙约束的模式匹配问题按照间隙的类型可以分为非负间隙约束模式匹配和一般间隙约束模式匹配。非负间隙模式匹配是指模式串中的最小间隙和最大间隙均为大于等于0的数，而一般间隙模式匹配是指模式串中的最小间隙和最大间隙至少有一个为小于0的数。例如模式串=1[1，1]2[2，2]3= a[0，1]b[0，1]c就是一个非负间隙模式串，而模式串=1[1，1]2[2，2]3=a[-1，1]b[-1，2]c则为一般间隙模式串。文献[2]对非负间隙约束的模式匹配问题进行了研究，并应用于序列模式挖掘中；文献[3]利用网树结构对一般间隙约束的模式匹配问题进行了研究。

1.2 宽松模式匹配与严格模式匹配

宽松模式匹配是指仅考虑模式串中最后一个字符在序列串中的位置，不考虑其他位置的字符，因此宽松模式匹配通常对出现没有特殊的约束要求。Fredriksson和Grabowski[4]对一般间隙的宽松模式匹配问题进行了研究，并应用于音乐信息检索及蛋白质序列分析等方面。

严格模式匹配要考虑模式串中每个字符在序列串中的位置，并由此构成一个出现。文献[2]及文献[5]均是对严格模式匹配问题进行研究。严格模式匹配更广泛的应用于生物信息等领域。

以下举例说明了宽松模式匹配与严格模式匹配的区别。

例1：给定序列串=1234567=gaccgac，模式串=1[1，1]2[2，2]3=g[0，4]a[0，1]c。

宽松模式匹配只考虑模式串中最后一个字符3=c在序列串中的位置，例1中模式串在序列串中有3个出现，分别是3、4、7。

严格模式匹配考虑模式串中所有字符在序列串中的位置，例1中模式串在序列串中的出现有4个，分别为<1，2，3>、<1，2，4>、<1，6，7>以及<5，6，7>。

1.3 精确模式匹配与近似模式匹配

精确模式匹配要求所有位置的字符都要与模式串P中的字符相对应，而近似模式匹配允许一定程度的不对应，如基于Hamming距离的近似模式匹配。文献[6]对基于Hamming距离的一般间隙的近似模式匹配问题进行研究，并提出SETA算法对该匹配问题进行求解。

1.4 对出现的特殊约束条件

对出现的特殊约束条件只存在于严格模式匹配问题中。其中包括三种对出现的统计方式：无条件约束、一次性条件约束和无重叠条件约束。此外，还有无长度约束。

1.4.1 无条件约束

无条件约束指对出现没有任何约束，即找到模式串在序列串中的所有出现。

例2：给定序列串=123456=gagaag，模式串=1[1，1]2[2，2]3=g[0，1]a[0，1]g。

无约束条件下模式串在序列串中的3个出现为：<1，2，3>、<3，4，6>以及<3，5，6>。文献[2]所研究的即为无条件约束的模式匹配问题。

1.4.2 一次性条件约束

一次性条件约束要求序列串中任意位置对应的字符在匹配过程中最多被使用一次。在一次性条件约束下，例2中模式串在序列串中的出现只有1个，为<1，2，3>（或<3，4，6>或<3，5，6>）。文献[5]提出了DCNP算法，该算法利用网树结构，通过动态更新网树的策略，解决了一般间隙及一次性条件的模式匹配问题，并在很大程度上提高了解的质量。

1.4.3 无重叠条件约束

Ding 等人[7]提出了无重叠序列模式挖掘问题。无重叠条件约束要求序列串中任意位置的字符不能在两个出现的同一位置使用。在例2中，模式串在序列串中的无重叠出现有两个，为<1，2，3>和<3，4，6>（或<1，2，3>和<3，5，6>亦可）。尽管位置3的字符“g”被使用了两次，但是分别是模式子串3和子串1使用。

由于Ding 等人提出的无重叠模式匹配算法INSgrow不能找到完备解，因此Wu等人[8]针对INSgrow算法存在的问题，提出了NETGAP-Best算法，该算法利用网树结构通过寻找最右双亲结点来找到一个出现，在找到出现后对网树进行剪枝，该算法有效的解决了无重叠模式匹配所找解不完备的问题。

1.4.4 是否存在长度约束

具有长度约束的模式匹配要求找到的出现中的最小位置与最大位置的差要满足给定的最大长度和最小长度。若例2中规定最小长度为4、最大长度为5，则由于出现<1，2，3>的长度为3-1+1=3，因此不满足长度约束。对于出现<3，4，6>和出现<3，5，6>，因为6-3+1=4，所以满足长度约束。文献[3]对有长度约束的模式匹配进行了研究。

2 总结

本文介绍了具有间隙约束的模式匹配问题的研究现状，具体介绍了具有间隙约束的模式匹配问题的分类以及近几年各种模式匹配问题的研究进展，并对其中经典算法进行了简单的介绍。目前具有间隙约束的模式匹配问题的研究越来越多，如何更好地提高解的质量，并将其应用到现实生活中，值得研究者们做进一步的探索。

[1]Manber U，Baeza-Yates R. An algorithm for string matching with a sequence of don’t cares[J].Information Processing Letters，1991，37（3）：133-136.

[2]Wu Y X, Wang L L，Ren J D, et al. Mining Sequential Patterns with Periodic Wildcard Gaps[J]. ApplIntell，2014，41（1）：99-116.

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

[4]Fredriksson K，Grabowski S. Efficient algorithms for pattern matching with general gaps, character classes and transposition invari- ance[J]. Information Retrieval，2008，11（4）：335-357.

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

[6] Wu Y X，Fu S，Jiang H， Wu X D.Strict approximate pattern matching with general gaps[J].ApplIntell, 2015，42：566-580.

[7]Ding B，Lo D， Han J， Khoo S C. Efficient mining of closed repetitive gapped subsequences from a sequence database[C]//In: Ioannidis Y E, Lee D L, Ng R T，eds. IEEE 25th International Conference on Data Engineering（ICDE），Shanghai，China: IEEE, 2009：1024-1035.

[8]Wu Y X，Shen C，Jiang H，Wu X D. Strict pattern matching under non-over lapping condition[J]. Science China Information Sciences，2017，60（1）：1-16.

Progress on Pattern Matching with Gap Constraints

Jin Chaoyan Liu Jingyu

School of Computer Science and Engineering, Hebei University of Technology, Tianjin 300401

Pattern matching (also known as string matching) is one of the classic computer science problems, and is also the key to solving technical problems many interdisciplinary. Sequence pattern matching with gap constraint has become a research hotspot in pattern matching. It has been widely used in many fields, such as the research of DNA sequence in biology, the retrieval of note information in music field, and the hot field of big data nowadays. Therefore, the problem of pattern matching with gap constraints is the foundation of many fields and has high research value and significance. The paper summarizes the achievements and progress of pattern matching with gap constraint in recent years, and forecasts the trend of pattern matching with gap constraint in order to further study the pattern matching with gap constraint.

pattern matching; gap conditions; research progress

TP391.1

A

河北省高等学校科学技术研究项目资助（QN2014192）；河北省科技计划项目（15210325）；河北省自然科学基金（F2016202145）。