字符串模式匹配算法综述

1、字符串模式匹配算法综述摘要：字符串匹配问题是在给定符号序列（称为文本）中按照一定的匹配条件，搜索给定符号序列或给定符号序列集合中元素（称为模式）出现位置的搜索问题。该问题是计算机科学的基础问题之一，被广泛的应用于各种涉及文字和符号处理的领域中，是网络安全、信息检索、计算生物学等重要领域的关键问题。本文主要介绍了BF 算法、KMP 算法、BM 算法、BMH 算法、AC 算法和 AC-BM 算法。关键词：模式匹配，BF算法，KMP算法，改进算法，BM算法，AC算法，ACH算法。0.前言字符串是一种线性表,它在计算机应用系统中如文本编辑、情报检索、自然语言翻译有着广泛的应用。在这些应用中常常需要在一

2、堆文字符串中检测是否有某一指定的字符串。设Pattern(下文简称 P)和Text(下文简称 T)是给定的两个字符串,在字符串T中寻找等于P的子串的过程称为模式匹配,其中字符串T称为主串,字符串P称为模式串。如果在字符串T中找到等于P的子串,则称匹配成功,否则匹配失败。比较著名的模式匹配算法有BF算法、KMP算法、AC算法和BM算法,本文对所述算法进行探讨。随着计算机技术的快速发展，计算机网络在国民经济中发挥了日益重要的作用，己成为人们日常生活中不可缺少的一部分。同时，网络安全也日益引起人们的关注。1.模式匹配算法1.1 单模式匹配算法1.1.1 BF（Bruce Force）算法1. 算法思

3、想从文本字符串 T的第一个字符起和模式字符串 P 中的第一个字符开始比较，若相等，逐个比较后续字符，否则从文本字符串的下一个字符起再重新和模式字符串的第一个字符比较。2. 算法描述对于文本字符串模式字符串（1）P 和 T 从左端对齐，使得 与 对齐；（2）从左到右匹配 P 与 T 的字符，直到出现不匹配的情况，则执行（3），或是 P 己被完全匹配的情况则结束比较；（3）将 P 右移一个字符，重新从P的第一个字符开始匹配；（4）重复上述（2）过程，直到 P 被完全匹配，或 P 移到 T 的右端。1.1.2 KMP（Knuth Morris Pratt）算法KMP 算法是 Knuth 等人在 BF

4、 算法的基础上提出来的。从本质上讲，KMP算法就是出现不匹配情况下带有智能指针初始化的 BF 算法。为了在不匹配时重新定位指针，KMP 算法需要进行预处理算出一个 next数组来。1.基本思想KMP 算法利用己匹配成功部分的信息，即前缀（模式字符串中存在的相同子串），可以使模式字符串向前推进若干个字符位置，而不只是一个字符，避免了重复比较，同时也实现了文本字符串指针的无回溯。2. 算法描述当模式匹配执行到比较字符 和，其中 l=i=n，l=j=m。（l）若 =则继续往右做匹配检测，即对 和 进行匹配检测。（2）若 当 j=l，则对 和 进行匹配检测，即把模式和正文向右移动一位再从模式的第一个字

5、符进行匹配；若 l<j=m，我们将试图在模式中找到一个合适位置再进行比较，我们把这个下标记做 nextj。执行和的匹配，其中 nextj的构造是算法的核心，约定如下：改进的字符串匹配算法字符串模式匹配算法要解决的关键问题是：在模式与文本在某个位置比较失败时，如何使模式串窗口向右移动最佳距离，尽量多的跳过不必要比较的字符，减少匹配的次数，并使产生这种距离的算法复杂度降低和易于理解。通过对现有的各种字符串匹配算法进行分析研究，我们提出一种改进算法，该算法简单实用，便于理解。1.基本思想与KMP算法类似，在模式串的匹配过程中，字符比较采用符合人们习惯的从左到右顺序，模式窗口也是从左到右移动。2

6、.算法描述设当前的比较窗口是，在某次比较过程中失败于处，即前 j个字符匹配成功：=，而 。首先定义一个函数 S来确定正文中出现的字符 x 在模式P 中的位置，考虑到要使用模式对应窗口后的第一个字符，在模式串 P 中补充一个字符 Pm与之对应，以使和文本中的窗口对齐，这样 ，如图 1所示。图 1 模式串P与主串T对应位置函数 S 的定义如下：其中：x取当前窗口匹配失败位置j及其后的字符即x=，jkm，并且x取值位置的变化引起前面子串长度的变化。S(x)函数实质是用来求匹配失败时模式串的向右移动距离。有以下三种情况：（1） 当 x 不在前面的子串 (子串包括 P本身) 中时，启发移动的距离是子串的

7、字符个数；（2） 在子串中从后向前查找第一个与x相同的字符，启发移动的距离是它们之间的间隔距离；（3） 如果 ，子串的下标0-1-1，为统一使用函数S(x)而规定的取值。图2 改进算法的具体实现流程我们采用 3个位置的字符：、进行计算，之所以考虑用、来参与决定模式窗口的移动距离，是因为如前面的字符发生不匹配，则模式至少向后移动一个位置，二者处于移动后的窗口之内，作为新窗口之内的字符，、也需要与模式中与之相同的字符对齐，它们也要求模式滑过一定距离，所以考查由它们来启发的距离是自然的，尤其是当二者不在它们前面的子串中时，能够得到更大的启发移动位移，比如位移距离可以是 j+1、m+1，不仅仅是 k

8、q，这样可以显著减少模式比较的次数，所以有必要考虑这两个字符的参与。这一算法的主要思想是：利用文本串当前窗口的特殊位置的字符来启发窗口向右移动的距离，取MAX(S(,)作为实际移动距离，记为 MAX(S)，假设在执行文本中自位置 i 起与模式的从左至右的匹配检查中，一旦发现不匹配(假设在 Ti+j处发生不匹配)，则去执行由与 对应起始的下一窗口的尝试。1.1.4 BM（Boyer-Moore）算法1.BM 算法思想假设模式字符串 P（Pattern）的长度为 m。先令模式字符串 Pattern 最左边的字符和文本字符串 T（Text）最左边的字符对齐，然后对 Pattern 中最后一个字符与其

9、在 Text 中相对应的字符 Tm进行比较，即从右向左进行匹配，当发现不匹配时，算法采用两条启发性规则，这两条启发性规则是：坏字符（BC）规则和好后缀（GS）规则，来计算模式字符串移动的距离，实现跳跃式的遍历匹配。（1） 坏字符 BC 规则描述当模式字符串 P 中的某个字符与文本字符串 T 中的某个字符不相同时，出现一个坏字符，BM 算法向右移动模式字符串，让模式中最靠右的对应字符与坏字符相对，然后继续匹配。移动函数如下：将 Pattern 和 Text 左对齐后，Pattern 中最后一个字符与其在 Text 中对应字符比较的结果有下面两种可能。<1>.Tm根本没有在 Patte

10、rn 中任何一个位置出现，那么我们可以将 Pattern 向右移动 m 个字符，然后将 Pattern 中最后一个字符与它现在所对应的 Text 中的字符（即 T2m）进行比较。如图 3所示：图3 Tm不在Pattern中出现在上图中，Pattern 的长度 m4，Pattern 和 Text 左对齐后，检查 Pattern 中最后一个字符“E”与它在 Text 中对应的字符“G”，结果是不匹配；再检查“G”是否在 Pattern 其它位置出现，发现“G”不在 Pattern 中任一位置出现，所以移动距离为 4，移动后的结果如图4所示：图4 跳跃后的结果<2>.如果 Tm是 Pat

11、tern 中的第 j 个字符，那么我们可以将 Pattern向右移动 m-j 个字符。如图 5 所示：图5 Tm在Pattern中出现在上图中，Pattern 和 Text 左对齐后，检查 Pattern 中最后一个字符“E”与它在 Text 中对应的字符“D”，结果是不匹配；再检查，“D”是否在 Pattern其它位置出现，发现“D”在 Pattern 中的最右出现位置是 3，所以移动距离为4-3 = 1，移动后的结果如图 6 所示：图6 跳跃后的结果（2）好后缀 GS 规则描述如果已经匹配了一个好后缀，并且在模式中还有另外一个相同的后缀，GS规则考虑己经取得的匹配情况，确定了一个新的移动距

12、离，该函数只与模式字符串 P 有关。当比较过程中发生了失配时，具体分以下两种情况讨论。<1> P 中间的最右某一子串 与已比较部分 相同，可以让 P 右移 S 位。<2> P 已比较部分的后缀与 P 的前缀 相同，可以让 P 右移 S 位。满足上述两种情况的较小的 S 值即为最佳右移距离。例如将 Pattern 和 Text 左对齐后，Pattern 中最后一个字符与其在 Text 中对应字符进行比较，结果如图 7 所示：跳跃前：跳跃后：图 7 好后缀跳转示例上图中，文本字符串 T 中的字符“o”不匹配模式字符串 P 中的字符“s”，根据坏字符跳转，BadChar（o）

13、等于 0。因此，坏字符跳转在这里不起作用。但我们发现文本字符串 T 中的“two”在 P 中显示多次。我们将模式字符串 P向右移动，使模式字符串 P 中第二次出现的子串“two”与文本字符串 T 的后缀“two”对齐。根据好后缀规则，将模式字符串 P 移动字符个数为 9。当模式字符串与文本字符串不匹配时，根据具体情况采用坏字符或者好后缀移动函数来计算偏移值。如同时满足两条启发性规则，在这种情况下就选取两者中的较大者作为模式字符串右移的距离。因为任何一个都可以保证移动是安全的，使用最大的移动值不会跳过可能的匹配。2.算法描述（1）预处理，算法根据预先计算好的两个数组将模式字符串向右移动尽可能远的

14、距离。计算 Skip数组和 Shift数组，分别代表 BC 规则和GS 规则。（2）从右向左逐个字符比较文本字符串和模式字符串，单个字符匹配则继续比较。如果到达模式字符串的最左边，则成功发生了匹配，输出；如果发生字符失配，则转第三步。（3）取失配字符相应的 Skip数组和 Shift数组中的数值最大的一个，作为移动距离，将模式字符串右移。如果已到达文本字符串的末尾，则退出算法；否则转回到第二步执行。BM 算法被设计成为在文本中搜索单一模式字符串的算法，在单一模式的字符串匹配算法中，BM 算法一般被认为是性能最佳的。而在内容过滤和检测中有很多种关键词模式需要匹配，因此 BM 算法需要对每一种模式

15、分别进行匹配。BM 算法的预处理阶段的时间空间复杂性是 O（m+n），查找阶段的时间复杂性是 O（m n），查找非周期性模式时的最坏情况下比较次数是 3n 。BM 算法最坏时间复杂度是 O（m n），最好时间复杂度是 O（n）。对多模式字符串进行匹配，直接采用 BM 算法的复杂度是 O（kn）。1.1.4 BMH（Boyer-Moore-Horspool）算法1980 年，Horspool改进了 BM 算法，称为 BMH 算法。该算法在移动模式时仅考虑了坏字符启发，即在预处理时只使用 PreBadchar 预处理函数。通过研究和证明，Horspool发现：在文本字符串 T 字符种类较少的情况下

16、，坏字符启发的效率不高，通过好后缀启发可以增加匹配速度，提高匹配效率。但是在文本字符串 T 字符种类较多的情况下，例如 T 中字符为 ASCII 码的情况下，坏字符启发效率明显提高，这时好后缀启发的优越性体现得并不明显，因此仅仅采用坏字符启发对 BM 算法有比较明显的改进。1. 算法描述例如：文本字符串：HERE IS A SIMPLE PICTURE 模式字符串：PICTURE，BMH 算法的匹配过程如图8所示： 图 8 BMH算法匹配过程1.2 多模式匹配算法1.2.1 AC（Aho-Corasick）算法1975 年，贝尔实验室的 Alfred V.Aho 和 Margaret J.Co

17、rasick 提出了著名的多模式匹配算法AC 自动机匹配算法（简称 AC 算法）。该算法最早被使用在图书馆的书目查询程序中，取得了很好的效果。1.AC 算法思想AC 算法基于有限状态自动机（FSA），在进行匹配之前先对模式串集合 SP进行预处理，形成模式树（树形 FSA），然后只需对文本字符串 T 扫描一次就可以找出所有与其匹配的模式字符串 P。模式树 K 的构成如下：（1）K 的每一条边 e 上都用 1 个字符作为标签；（2）与同一节点相连的边的标签均不同；（3）每 1 个模式 pSP 都存在 1 个节点 v，使得 L(v)=p，其中 L(v)表示从根节点到 v 所经过的所有边上的标签的拼接

18、；（4）每一个叶子节点 v，都存在一个模式 pSP 使得 L(v) = p。例如：对于模式集SP=he，she，his，hers，构成的模式树如图9所示，其中圆圈表示节点，双圈是根节点，边上的字符就是该边的标签，填充点圈的标签就是各个模式。图 9 模式树2.AC 算法描述预处理阶段，模式树的各个节点作为状态，根节点作为初态，标签为模式的节点作为终态，利用转向函数 g 和失效函数 f 作为转移函数，将模式树扩展成一个树型有限自动机。由模式树扩展所得的 AC 自动机 M 是 1 个 6 元组：M = (Q，g，f，q0，F )其中：（1）Q 是有限状态集（模式树上的节点）；（2）是有穷的输入字符表

19、（数据包中可能出现的所有字符）；（3）g 是转移函数，该函数定义如下：g（s，a）：从当前状态 s 开始，沿着边上标签为 a 的路径所到的状态。假如 (u,v)边上的标签为 a，那么 g(u，a )= v；如果根节点上出来的边上的标签没有 a，则 g（0，a）=0，即如果没有匹配的字符出现，自动机停留在初态；（4）f（不匹配时自动机的状态转移）也是转移函数，该函数定义如下：f（s）：当 w 是 L(s)最长真后缀并且 w 是某个模式的前缀，那么 f(s) 就是以 w 为标签的那个节点；（5）q0Q 是初态（根节点，标识符为 0）；（6）FQ 是终态集（以模式为标签的节点集）。这样，在文本字符串

20、中查找模式字符串的过程转化成在模式树中的查找过程。查找一个文本字符串 T 时从模式树的根节点开始，沿着以 T 中字符为标签的路径往下走：若自动机能够抵达终态 v，则说明 T 中存在模式 L(v）；否则不存在模式。1.3 影响模式匹配算法的因素对于一个模式匹配算法来说，在实际应用中，最为关注的问题有以下几个方面：（1）正确性：即误判率和漏判率，这与模式的选择是密切相关的，如果模式的选择比较严格，那么误判率和漏判率一定会下降，但是过于严格的模式会影响识别的速度；同时过于简短的模式又会影响误判率和漏判率，所以要选择一个最优的折衷点。（2）速度：即时间复杂性，这是评价一个模式匹配算法的重要的标准之一。

21、随着网络速度的提高，通常要求模式匹配能以线速率执行，特别是在一些实时性的系统中，对模式匹配的速度有很高的要求。一般情况下算法的时间复杂性，首先是预处理时间复杂性，其次是匹配过程中的时间复杂性，最后是最坏情况和最好情况下的时间复杂性，特别是最坏情况下的复杂性，是算法研究中的一个重要方面。而在上述三种情况的时间复杂性中，模式的因素都是一个不可缺少的原因。简洁有效的模式不仅可以降低预处理的时间复杂度，而且还能缩短匹配过程的时间，至于最坏和最好的时间复杂度，在很大程度上受控于模式的规模。所以若要提高算法的速度，提高模式的有效性是一个重要途径。（3）资源消耗：在模式的预处理阶段和模式匹配阶段，对内存的需

22、求也是应用中关注的重要问题之一，尽管目前内存的容量提高了很多，但是庞大的内存占有量会减慢算法的速度，所以现在人们常常借助于硬件实现算法。2.总结字符串匹配技术是入侵检测系统 IDS 中关键技术之一。在网络速度迅速发展的今天，基于模式匹配技术的 IDS 网络应用存在着严重的性能瓶颈，不能适应大流量网络环境的要求，丢包率和漏报率不断上升，因此研究高效的字符串匹配算法，将其应用到入侵检测系统的检测引擎中，提高匹配检测的速度及性能，更好地发挥算法的优势，是今后研究工作的重点。2.1 BF（Bruce Force）算法总结BF 算法在最坏的情况下的时间复杂度为 O（n m），比较次数是 2n，而且在文本

23、字符串中出现多个与模式字符串部分匹配的子串的情况下，文本字符串的指针需要经常回溯，显然算法的效率很低。2.2 KMP（Knuth Morris Pratt）算法总结KMP 算法搜索阶段在最坏的情况下时间复杂度为 O（n m），但在一般情况下，其实际的执行时间近似于 O（n+m），next数组的存在需要额外的空间为O（m）。在大多数情况下，KMP 算法并不比 BF 算法好很多，但 KMP 算法确保了线性，并且其扩展性适合求解更难的问题，尤其是因为 KMP 算法不需要回溯，在处理从外设读入的庞大文件时，这种特性很有价值。2.3 BM（Boyer-Moore）算法总结BM 算法是由 Boyer 和 Moore 于 1977 年提出，该算法是目前应用最为广泛的单模式匹配算法。BM 算法的一个最主要的特点是，在对字符串的匹配过程中，可以跳过很多无用的字符，即不对无用的字符进行匹配。通过这种跳跃式的匹配，获得了较高的执行效率。有实验数据表明，BM 算法的匹配速度大约是 KMP算法的 35 倍。BM 算法为