定义

传统的匹配算法

应用

柔性字符串匹配(带有通配符的串匹配 近似匹配 序列比对 序列模式挖掘)

定义

字符串匹配是计算机科学中最古老、研究最广泛的问题之一。一个字符串是一个定义在有限字母表∑上的字符序列。例如，ATCTAGAGA是字母表∑ = {A,C,G,T}上的一个字符串。字符串匹配问题就是在一个大的字符串T中搜索某个字符串P的所有出现位置。其中，T称为文本，P称为模式，T和P都定义在同一个字母表∑上。

传统的匹配算法

串匹配算法虽然发展了几十年，然而非常实用的算法是近年才出现。串匹配问题的研究存在理论研究和实际应用的脱节。那些专门从事算法研究的学者关心的只是理论上看起来很美妙的算法——具有很好的时间复杂度。而开发人员只追求实际应用中尽可能快的算法。两者之间从不注意对方在干什么。将理论研究和实际应用结合的算法(如BNDM算法)只是近年才出现。在实际应用中常常很难找到适合需求的算法——这样的算法实际上是存在的，但是只有资深专家才比较了解。考虑如下情况，一位软件开发人员，或者一位计算生物学家，或者一位研究人员，又或者一位学生，对字符串匹配领域并没有深入了解，可是现在需要处理一个文本搜索问题。那些汗牛充栋的书籍使得阅读者淹没在各种匹配算法的海洋中，却没有足够的知识选择最适用的算法。最后，常常导致这样的局面：选择一种最简单的算法加以实现。这往往导致很差的性能，从而影响整个开发系统的质量。更糟糕的是，选择了一个理论上看起来很漂亮的算法，并且花费了大量精力去实现。结果，却发现实际效果和一个简单算法差不多，甚至还不如简单算法。因此，应该选用一种“实用”算法，即在实际应用中性能较好，并且一个普通程序员能在几小时内完成算法的实现代码。另外，在字符串匹配研究领域中，一个人所共知的事实是“算法的思想越简单，实际应用的效果越好”。

传统的串匹配算法可以概括为前缀搜索、后缀搜索、子串搜索。代表算法有KMP，Shift-And，Shift-Or，BM，Horspool，BNDM，BOM等。所用到的技术包括滑动窗口、位并行、自动机、后缀树等。

应用

它的应用包括生物信息学、信息检索、拼写检查、语言翻译、数据压缩、网络入侵检测。例如在生物信息学中，启动子有助于研究者从数以亿计的ACGT序列中快速定位内含子的起始位置，这些启动子中较常见的有TATA序列。它常常出现在CAATCT序列之后。它们之间并不是连续出现，而是间隔了30-50个通配符。又比如在信息检索中，一个挑战性的任务是，搜索出由用户自定义的模式对应在文本中的匹配位置，这种模式很可能带有通配符。在上述应用背景下，一种更加灵活的带有通配符的模式串应运而生。

柔性字符串匹配

1974年Fischer和Paterson将通配符don't cares引入模式匹配问题，之后模式匹配的定义出现了各种各样非标准形式：按匹配方式分，有容错的近似匹配，交换相邻字母的交换匹配，服务于程序代码查错的参数匹配等；按匹配对象分，T、P可以是一张二维表，也可以分别含有通配符；按匹配结果分，有返回匹配位置和匹配数两种定义。Muthukrishna等人将上述各类问题统称为Non-standard Stringology。然而，通配符的引入会让问题定义更加灵活，却也带来了复杂性。算法的设计有时不仅仅考虑时空效率，保证匹配结果的完备性很可能成为算法设计更重要的问题。甚至其中的某些问题被猜测具有NP难度。

带有通配符的串匹配

在Fischer和Paterson于1974年将通配符*引入模式匹配问题之后，如何将通配符与传统的模式匹配有效结合是研究的重点。这其中，最具代表性的定义是通配符指代的字符数不仅仅用一个固定的常数表示，而是一个可由用户自定义的区间，即带有上下限约束，如TCT*(30,50)TATA。将上述带有区间的通配符扩展至任意两两相邻的字符之间，然而所有的通配符上下限相同，如A*(1,3)C*(1,3)G*(1,3)C。为了进一步放宽约束，提出了不同通配符彼此独立的思想，如A*(0,3)C*(2,4)G*(1,1)C。

近似匹配

近似匹配是一种允许误差的串匹配。这种误差的度量一般用编辑距离，记为k。衡量编辑距离的操作包括插入、删除、替换。问题的输入是文本T，模式P和编辑距离k，输出是匹配数或匹配位置。常用的方法包括动态规划、自动机、位并行和过滤算法。近似匹配也属于Non-standard Stringology问题。它最常见的应用背景来源于生物信息学。问题定义上，近似匹配中的k可以对模式中的任何字符的编辑操作进行计数。例如，给定文本T的子串T’= ……aacct……，P = aaacc，从P到T’要经过两次替换操作，因此k = 2。

序列比对

将两个或多个序列排列在一起，标明其相似之处。序列中可以插入间隔。序列比对中也允许错误匹配，也需要计算编辑距离。与近似匹配相比，序列比对将文本和模式都看作序列，且长度接近。序列比对最广的应用是生物信息学，将未知序列同已知序列进行相似性比较是一种强有力的研究手段。例如，序列的片段测定，拼接，基因的表达分析，RNA和蛋白质的结构功能预测。

序列模式挖掘

序列模式挖掘是数据挖掘的一个重要分支，是基于时间或者其他序列的经常发生的模式。序列模式的一个例子就是“一个9个月前买了一台PC的顾客有可能在一个月内买一个新的CPU”。很多数据都是这种时间序列形式的，我们就可以用它来市场趋势分析，客户保留和天气预测等等。序列模式首先是由R.Agrawal和R.Srikant提出的，随后几年研究者所提出的算法都是基于Apriori原理的改进算法。随后Zaki等人提出了基于垂直数据表示的SPADE算法。Han等提出了不产生候选集的基于模式增长的FP-Growth算法。接着Han等又研究出了基于投影数据库的FreeSpan和PrefixSpan算法。