字符串匹配

计算机术语

字符串匹配是计算机科学中最古老、研究最广泛的问题之一。一个字符串是一个定义在有限字母表∑上的字符序列。例如，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算法。

特点

一般而言，好的字符串匹配算法要有以下特点:

速度快

这是评价一个字符匹配算法最重要的标准。通常要求字符匹配能以线性速度执行。目前，网络安全应用中的基于误用的NIDS使用字符串匹配算法进行入侵检测，因此，随着网速的提高，对字符串匹配速度的需求同样也在提高。

有几种时间复杂性的评价指标：

1)预处理时间的复杂性:有些算法在进行字符串匹配前需要对模式特征进行预处理;

2)匹配阶段的时间复杂性:字符串匹配过程中执行查找操作的时间复杂性，它通常和文本长度及模式长度相关;

3)最坏情况下的时间复杂性:对一个text进行字符模式匹配时，设法降低各算法的最坏情况下的时间复杂性是目前的研究热点之一;

4)最好情况下的时间复杂性:对一个text进行字符模式匹配时的最好的可能性。

内存占用少

执行预处理和模式匹配不仅需要CPU资源还需要内存资源，尽管目前内存的容量较以前大得多，但为了提高速度，人们常利用特殊硬件。通常，特殊硬件中内存访问速度很快但容量偏小，这时，占用资源少的算法将更具优势。

未来的工作

字符串匹配工作一直是IDS研究领域中的热点之一。在网络速度迅速发展的今天，基于字符匹配技术的网络应用存在着性能瓶颈，提高系统的整体性能是研究和设计者的主要工作。字符匹配是其实现网络入侵检测的主要技术之一，因此，高效的算法将是提高系统总体性能的手段之一。在字符匹配算法中存在这样的几个定理:一个是“任何的字符串匹配算法在最糟的情况下必须检查至少n-m+1个text中的字符”，这说明没有哪一个算法会比KMP或BM有更好的计算复杂性。算法的平均性能可以得到提高，但最糟情况下的结果是一个严格的限制;另一个定理是“任何字符匹配算法至少检查n/m个字符”，这个是显而易见的。基于以上的结论，接下来研究的主要方向是设法提高算法的平均性能和减少资源耗费:主要的途径可以采用在实际的网络应用中设法减少m或n的值来减少实际匹配的次数;设法将部分匹配算法移植到硬件的实现中或在并行的体系结构卜实现等，以减少匹配所耗费的时问。

全国各地天气预报查询

上海市

云南省

云南省

云南省

云南省

云南省