字符串匹配算法探讨

母 泽 平

(重庆电子工程职业学院 软件学院 重庆401331)

字符串匹配是模式匹配中最简单的一个问题，但在文本处理领域中字符匹配是一个非常重要的主题。它可用于数据处理、数据压缩、文本编辑、信息检索等多种应用中，大多数操作系统中软件实现的字符匹配算法是基本组件之一。字符串匹配技术通常也和其他字符问题有一定关联。在实际应用中字符串匹配技术不仅适用于计算机科学，在语义学、分子生物学等领域也具有相当重要的应用，在以模式匹配为特征的网络安全应用中也发挥了举足轻重的作用。

1 字符串匹配算法研究现状

字符串匹配分为精确字符串匹配与非精确字符串匹配，是计算机科学的重要组成部分，隐含众多信息科学理论、算法思想以及算法技巧，其应用渗透了信息技术的各个领域。随着网络信息大众化的快速发展，用户对信息检索提出了更高要求，功能上要求提高查全率、查准率以及精确定位，操作上要求简单、灵活、快捷。作为信息检索的基础，字符串匹配越来越重要，成为信息检索的瓶颈技术，直接影响到信息检索的检索方式、检索功能、检索效果、用户界面等。非精确字符串匹配方法主要包括容错纠错匹配 、最大匹配 、相似匹配 等。非精确字符串匹配允许出现有限的错误，通过相似度或距离等方式进行约束，返回匹配结果以及匹配位置。

从上个世纪六十年代开始，非精确字符串匹配一直采用基于错误因素进行匹配的研究思路。错误因素主要包括插入错误(Insertion) 、删除错误(Deletion)、交换错误(Swap)、替换错误(Substitution)等[1]。由于错误因素种类较多，非精确字符串匹配通常综合处理部分错误因素，采用距离计算模型，从不同应用角度、各种技术，形成了线性时间复杂性到NPC(Non deterministic polynomial complete)复杂性的各种解决方案 ，用于解决允许有限错误的字符串匹配问题[2]。 为便于问题的讨论，本文聚焦于单模式字符串匹配。在分析BM和KMP算法特点的基础上，对这些算法进行了深入探讨和剖析。

2 字符串匹配技术常用算法分析

(1) BF算法。BF(Brute Force)算法是效率最低的算法。其核心思想是：T是文本串，P是模式串。首先S[1]和P[1]比较，若相等，则再比较S[2]和P[2]，一直到P[M]为止；若S[1]和P[1]不等，则P向右移动一个字符的位置，再依次进行比较。如果存在t，1≤t≤N，且S[t+1，t+2，…，t+M]=P[1，2，…，M],则匹配成功；否则失败。该算法最坏情况下要进行M*(N-M+1)次比较，时间复杂度为O(M*N)。

(2) KMP算法：KMP(Knuth-Morris-Pratt)算法是D.E.Knuth、J.H.Morris和V.R.Pratt 3 人于1977年提出来的。其核心思想是：在匹配失败时，正文不需要回溯，而是利用已经得到的“部分匹配”结果将模式串右移尽可能远的距离，继续进行比较[3]。在此要强调的是，模式串不一定向右移动一个字符的位置，右移也不一定必须从模式串起点处重新试匹配，即模式串一次可以右移多个字符的位置，右移后可以从模式串起点后的某处开始试匹配。KMP算法的时间复杂度是O(m+n)，最坏情况下时间复杂度为O(m*n)。空间复杂度是O(m)，对BF算法进行了很大的改进。虽然，KMP算法有着它自身的局限性，但是，在现代科学的众多领域中的应用仍然普遍。

(3) BM算法。1977 年，Boyer 和Moore 提出了一个全新的模式匹配算法——BM 算法。该算法在匹配过程中，模式串从左向右移动，但字符比较按照P[M]、P[M-1]、…、P[1]的次序从右向左进行[4]。BM 算法的一个最主要的特点是：在匹配过程中，可以跳过很多无用的字符。通过这种跳跃式的匹配，获得了极高的匹配效率。该算法的核心思想是：对于模式串P，定义一个函数d：Σ→{1, 2,…,M} ，函数d给出了正文中可能出现的字符在模式中的位置。该算法最坏情况下的时间复杂度为O(N*M)。但由于在实际应用中这种情况极少出现，因此BM算法仍得到广泛的应用。

(4) BMH算法。1980 年, Horspool 提出了对BM 算法的一种改进算法——BMH算法。首先比较文本指针所指字符和模式的最后一个字符,如相等再比较其余m-1个字符。无论文本中哪个字符造成了匹配失败,都将由文本中和模式最后一个位置对应的字符来启发模式向右的滑动。即文本自位置I起与模式的从右至左的匹配检查中, 一旦发现不匹配,就将I重新赋值为End+d[T[End]]。(End是一个中间变量,记录了文本中每次从右至左匹配的起始位置)。

(5) RK算法：RK算法是Turing奖获得者R.M.Karp和M.O.Rabin在1981年提出来的，该算法采用了与KMP算法和BM算法完全不同的方法。该算法利用Hash方法和素数理论，首先定义一个Hash函数，然后将模式串P和文本串T中长度为m的子串利用Hash函数转换成数值。显然只需比较那些与模式串具有相同Hash函数值的子串，从而提高了效率。当然因为Hash冲突的存在，还要进一步进行字符串比较，但只要选择适当的素数Hash冲突的概率就会很小。RK算法的时间复杂度是O(n+m)。

3 相关算法性能测试和结果分析

对上述的字符串模式匹配算法从时间方面进行测试 ,从而分析各算法的效率。实验中分别从4个方面对各算法进行了测试 ,分别是模式串在正文串中的匹配不成功、模式串在主串中的头部匹配成功、模式串在主串中的中部匹配成功、模式串在主串中的尾部匹配成功。在这四个方面中采用相同长度的文本串 ,分别为 50,100,150,200,但文本串的内容不一样；模式串的长度均为 5,内容也不一样。在这些用例的基础上对 KMP、BM、RK算法进行测试 ,得到的结果如表1-表 4所示。

表1 匹配不成功时各算法所花时间 m

表2 在正文头部匹配成功时各算法所花时间 m

表3 在正文中部匹配成功时各算法所花时间 m

表4 在正文尾部匹配成功时各算法所花时间 m

从表 3-表 4的数据可以看出 ,在相同长度的正文串中 ,BM算法所花的时间总是最少的。由于 BM算法是从右向左的把模式同正文做比较 ,当模式符号做比较的文本符号在模式中没有出现时,模式可以在这个文本符号之后移位m个位置 ,从而避免不必要的回溯,所以它的速度较快、效率高。

4 总 结

字符串匹配是模式匹配中最简单的一个问题，但在文本处理领域中字符匹配是一个非常重要的主题。本文对字符串匹配技术进行了详细的分析与探讨，总结了字符串匹配问题的解决方法。重点对KMP模式匹配算法和BM模式匹配算法进行了深入剖析，并分析和比较了常用字符串匹配算法的性能和效率。

参考文献：

[1] PODICHUK C, DELP E. Digital Watermarking：Algorithms and Applications[J]. IEEE Signal Processing Mag., 2001,18(4)：33-46

[2] PATTERSON R. A Pulse Ribbon Model of Monaural Phase Perception [J]. JASA,1997,82(5)：1560-1586

[3] BASSIA P, PITAS I, NIKOLAIDIS N. Robust Audio Watermarking in the Time Domain [J]. IEEE Trans. on Multimedia, 2001, 3(2)：232-241

[4] CRAVER S, MEMON N, BOON-LOCK Y. Resolving Rightful Ownerships with Invisible Watermarking Techniques：limitations, Attack, and Implications[J]. IEEE Journal on Selected Areas in Communication, 1998,16(4)：573-586

[5] 刘许刚； 黄海； 马宏. 一种基于分段匹配的字符串匹配算法[J]. 计算机应用与软件，2012，29(3)：128-131

[6] 廖秀玲， 邵剑飞， 李小武. 一种高效的字符串匹配算法[J]. 郑州轻工业学院学报：自然科学版，2012，27(1)：65-68.