【2017年整理】字符串模式匹配算法综述

《【2017年整理】字符串模式匹配算法综述》由会员分享，可在线阅读，更多相关《【2017年整理】字符串模式匹配算法综述（13页珍藏版）》请在金锄头文库上搜索。

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

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

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

5、配检测。iTjP1i1jP（2）若 当 j=l，则对 和 进行匹配检测，即把模式和正文向ij 1ij右移动一位再从模式的第一个字符进行匹配；若 l.Tm根本没有在 Pattern 中任何一个位置出现，那么我们可以将 Pattern 向右移动 m 个字符，然后将 Pattern 中最后一个字符与它现在所对应的 Text 中的字符（即 T2m）进行比较。如图 3 所示： JHFEGXBWTextDCQParn:图 3 Tm不在 Pattern 中出现在上图中，Pattern 的长度 m4，Pattern 和 Text 左对齐后，检查 Pattern 中最后一个字符“E”与它在 Text 中对应的字

6、符“G” ，结果是不匹配；再检查“G”是否在 Pattern 其它位置出现，发现“G”不在 Pattern 中任一位置出现，所以移动距离为 4，移动后的结果如图 4 所示：JHFEGXBWText DCQParn:图 4 跳跃后的结果.如果 Tm是 Pattern 中的第 j 个字符，那么我们可以将 Pattern 向右移动 m-j 个字符。如图 5 所示： JHFEDXBWTextCQParn:图 5 Tm在 Pattern 中出现在上图中，Pattern 和 Text 左对齐后，检查 Pattern 中最后一个字符“E”与它在 Text 中对应的字符“D” ，结果是不匹配；再检查， “D”

7、是否在 Pattern 其它位置出现，发现“D”在 Pattern 中的最右出现位置是 3，所以移动距离为 4-3 = 1，移动后的结果如图 6 所示： JHFEDXBWTextCQParn:图 6 跳跃后的结果（2）好后缀 GS 规则描述如果已经匹配了一个好后缀，并且在模式中还有另外一个相同的后缀，GS规则考虑己经取得的匹配情况，确定了一个新的移动距离，该函数只与模式字符串 P 有关。当比较过程中发生了失配时，具体分以下两种情况讨论。P 中间的最右某一子串 与已比较部分 相同，可以让 P s-ms-jP m1jP右移 S 位。P 已比较部分 的后缀 与 P 的前缀 相同，可以让 m1j1s

8、s-1P 右移 S 位。满足上述两种情况的较小的 S 值即为最佳右移距离。例如将 Pattern 和 Text 左对齐后， Pattern 中最后一个字符与其在 Text 中对应字符进行比较，结果如图 7 所示：跳跃前： fityhundretwocunTexttplstPar:跳跃后： fityhundretwocunText tplstPar:图 7 好后缀跳转示例上图中，文本字符串 T 中的字符“o”不匹配模式字符串 P 中的字符“s” ，根据坏字符跳转，BadChar（o）等于 0。因此，坏字符跳转在这里不起作用。但我们发现文本字符串 T 中的“two”在 P 中显示多次。我们将模式字

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

10、符串和模式字符串，单个字符匹配则继续比较。如果到达模式字符串的最左边，则成功发生了匹配，输出；如果发生字符失配，则转第三步。（3）取失配字符相应的 Skip数组和 Shift数组中的数值最大的一个，作为移动距离，将模式字符串右移。如果已到达文本字符串的末尾，则退出算法；否则转回到第二步执行。BM 算法被设计成为在文本中搜索单一模式字符串的算法，在单一模式的字符串匹配算法中，BM 算法一般被认为是性能最佳的。而在内容过滤和检测中有很多种关键词模式需要匹配，因此 BM 算法需要对每一种模式分别进行匹配。BM 算法的预处理阶段的时间空间复杂性是 O（m+n） ，查找阶段的时间复杂性是 O（m n）

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

12、种类较多的情况下，例如 T 中字符为 ASCII 码的情况下，坏字符启发效率明显提高，这时好后缀启发的优越性体现得并不明显，因此仅仅采用坏字符启发对 BM 算法有比较明显的改进。1.算法描述例如：文本字符串：HERE IS A SIMPLE PICTURE 模式字符串：PICTURE，BMH 算法的匹配过程如图 8 所示： )7Patern(: 位右 移中 ， 则 将”不 在中 字 符 “PaternSText ICTUREIMLHERICUPatrn )6ater(: 位右 移中 ， 则 将在中 字 符 terext IIAr )4Patern(: 位右 移中 ， 则 将在中 字 符 Pat

13、ernCText ICTURESIMLHERParn)(:匹 配 成 功 IIAtr图 8 BMH 算法匹配过程1.2 多模式匹配算法1.2.1 AC（Aho-Corasick）算法1975 年，贝尔实验室的 Alfred V.Aho 和 Margaret J.Corasick 提出了著名的多模式匹配算法AC 自动机匹配算法（简称 AC 算法） 。该算法最早被使用在图书馆的书目查询程序中，取得了很好的效果。1.AC 算法思想AC 算法基于有限状态自动机（FSA） ，在进行匹配之前先对模式串集合 SP进行预处理，形成模式树（树形 FSA） ，然后只需对文本字符串 T 扫描一次就可以找出所有与其匹

14、配的模式字符串 P。模式树 K 的构成如下：（1）K 的每一条边 e 上都用 1 个字符作为标签；（2）与同一节点相连的边的标签均不同；（3）每 1 个模式 pSP 都存在 1 个节点 v，使得 L(v)=p，其中 L(v)表示从根节点到 v 所经过的所有边上的标签的拼接；（4）每一个叶子节点 v ，都存在一个模式 pSP 使得 L(v) = p。例如：对于模式集 SP=he，she，his，hers，构成的模式树如图 9 所示，其中圆圈表示节点，双圈是根节点，边上的字符就是该边的标签，填充点圈的标签就是各个模式。图 9 模式树2.AC 算法描述预处理阶段，模式树的各个节点作为状态，根节点作为

15、初态，标签为模式的节点作为终态，利用转向函数 g 和失效函数 f 作为转移函数，将模式树扩展成一个树型有限自动机。由模式树扩展所得的 AC 自动机 M 是 1 个 6 元组：M = (Q，g，f，q 0，F )其中：（1）Q 是有限状态集（模式树上的节点） ；（2） 是有穷的输入字符表（数据包中可能出现的所有字符） ；（3）g 是转移函数，该函数定义如下：g（s，a）：从当前状态 s 开始，沿着边上标签为 a 的路径所到的状态。假如 (u,v)边上的标签为 a，那么 g(u，a )= v；如果根节点上出来的边上的标签没有 a，则 g（0，a）=0，即如果没有匹配的字符出现，自动机停留在初态；（

16、4）f（不匹配时自动机的状态转移）也是转移函数，该函数定义如下：f（s）：当 w 是 L(s)最长真后缀并且 w 是某个模式的前缀，那么 f(s) 就是以 w 为标签的那个节点；（5）q 0Q 是初态（根节点，标识符为 0） ；（6）FQ 是终态集（以模式为标签的节点集） 。这样，在文本字符串中查找模式字符串的过程转化成在模式树中的查找过程。查找一个文本字符串 T 时从模式树的根节点开始，沿着以 T 中字符为标签的路径往下走：若自动机能够抵达终态 v，则说明 T 中存在模式 L(v） ；否则不存在模式。1.3 影响模式匹配算法的因素对于一个模式匹配算法来说，在实际应用中，最为关注的问题有以下几个方面：（1）正确性：即误判率和漏判率，这与模式的选择是密切相关的，如果模式的选择比较严格，那么误判率和漏判率一定会下降，但是过于严格的模式会影响识别的速度；同时过于简短的模式又会影响误判