一种改进的字符串模式匹配算法

摘 要：高效快速的字符串模式匹配算法有助于网络信息处理的相关应用。文章在分析相关字符串匹配算法的基础之上，针对模式串中字符重复次数较多匹配应用，提出了一种快速的字符串匹配改进算法。该算法利用文本串中当前失败字符与模式串右对齐端的文本串下一个字符来启发模式串向右移动。结合这两个字符在模式串中匹配的情况及以这两个字符为首末的特征字符串在模式串中的匹配情况来使计算模式串向右移动最大距离，尽可能地排除无效匹配。实验结果表明，该算法能有效减少模式匹配中字符的比较次数，提高模式匹配效率。

关键词：字符串匹配；KMP算法；BM算法；Sunday算法；移动距离

中图分类号：TP301.6 文献标识码：A 文章编号：2095-1302（2017）07-00-03

0 引 言

随着信息技术的高速发展，如何在海量数据中提取有用信息是网络信息技术研究的热点。字符串模式匹配主要用于文本串的处理领域，如信息检索、拼写检查、数据处理、信息测试、数据压缩、搜索引擎、网络入侵检测、DNA序列匹配等。如何用高效快速的字符串模式匹配算法解决网络信息处理的相关问题已成为目前研究的重要领域之一。

字符串匹配问题的形式化定义是[1]：在有限字母表∑上的字符序列上，给定一个长度为n的文本串T[0…n-1]以及一个长度为m的模式串P[0…m-1]，m

1 相关算法介绍

1.1 KMP算法

KMP算法是经典的字符串匹配算法，主要在模式匹配过程中执行T[i]和P[j]的匹配检查。若T[i]=P[j]，则继续匹配T[i+1]与P[j+1]；若T[i]≠P[j]，则分成两种情况：若j=0，模式串P向右移一位，继续匹配T[i+1]和P[0]；若1

（1）

其中：

1.2 Horspool算法

Horspool算法是字符串匹配算法中从右向左匹配的创始者。当失配发生时，模式串P要向右移动，T串的失配字符T[i]可能是正确结果中的一个元素，也可能不是。如果不是，可将P串的首位与T串中的T[i+1]对齐，继续进行比较；如果是，那么从P串失配位置j开始向左任意一位与P[i]相等的字符c确定的比较位置可能完全匹配，其产生的位移依次为k1，k2…，ki（k1为j-location（c））。综合这两种情况，选择位移最小值k1，以保证不会错过正确匹配的情况。

1.3 BM算法

BM（Boyer-Moore，BM）算法是基于Horspool算法的一种改进算法，其广泛应用于实际项目中。BM算法实际包含两个并行算法，坏字符算法和好后缀算法。匹配时，同Horspool算法；当失配时，计算P串失配字符的右边已经匹配的字符串（称为“好后缀”），在P串中其他位置出现的位置得到一个右移大小值（实际该值是预先计算好的），将该值与Horspool失配时P串移动大小的值进行比较，并选择其中较大者。P串移动后，继续进行比较。

1.4 Sunday算法

Sunday算法是一种高效算法，可以看成BM算法的简化形式。在匹配过程中，模式串P不一定要按从左向右的顺序比较或从右向左进行匹配。在失配情况下，选中T串与P串右对齐端的下一个字符T[i]，从P串末位向左寻找与该字符相等的字符P[j]，找到后，T[i]与P[j]对齐，继续从右到左比较；若找不到，则P串左端与T[i]的下一个字符对齐，从右到左比较。

2 改进的字符串匹配算法

字符串模式匹配算法要解决的关键问题是在模式与文本某个位置比较失败时，如何使模式串窗口向右移动最佳距离，尽量跳过无需比较的字符，减少匹配次数，并使产生这种距离的算法复杂度降低且易于理解。通过对现有各种字符串匹配算法的研究，我们提出一种改进算法，该算法主要针对模式串重复率较多的情况使用。当文本串T与模式串P发生匹配时，判断模式串最右端对应文本串下一个字符Ti+m是否在模式串中，若不在，匹配规则同Sunday算法；若在，记下在模式串P0P1…Pm-1中的位置q，同时记下文本串中当前失败的字符Ti+j在模式串P0P1…Pj-1出现的位置k，根据q、k的值以及Ti+j+1Ti+j+2…Ti+m-1与Pk+1Pk+2…Pm-1的比较情况来计算模式串向右移动的最大距离。

2.1 比较顺序

与BM算法类似，在模式串的匹配过程中，字符串采用从右向左的顺序依次比较。

2.2 模式串移动距离的确定

假设当前匹配的比较窗口是TiTi+1…Ti+m-1，在某次比较过程中失败于Pj处，即后m-j个字符匹配成功：Ti+j+1Ti+j+2…Ti+m-1=Pj+1Pj+2…Pm-1，而Ti+j≠Pj，如图1所示。

图1 模式串P与文本串T对应的位置

首先定义变量k来确定Ti+j字符串在P0P1…Pj-1出现的位置，即0≤k≤j-1；定义变量q来确定Ti+m字符串在P0P1…Pm-1出现的位置，即0≤q≤m-1；定义数组q[m]，q[m]存有q1q2…qm值；定义数组k[j]，k[j]存有k1k2…kj值；定义Ti+j至Ti+m中的字符串Ti+j+1Ti+j+2…Ti+m-1为substring；定义Pk+1至Pm-1中的字符串Pk+1Pk+2…Pm-1为pattern。

当文本串与模式串不匹配时，判断模式串最右端对应文本串下一个字符Ti+m是否在模式串中，若不在，匹配规则同Sunday算法，模式串向右移动m+1距离；若在，记下在模式串P0P1…Pm-1中的位置q，同时记下文本串中当前失败的字符Ti+j在模式串P0P1…Pj-1出现的位置k，根据q、k的值以及substring与pattern的比较情况来计算模式串向右移动的最大距离。函数S的定义如下：

其中， S （q， k）函数用来表示匹配时模式串的向右移动距离， n （q，k）表示Ti+m字符串在P0P1…Pm-1字符串中出现，且Ti+j字符串也在P0P1…Pj-1字符串中出现时模式串向右移动距离，改进的匹配算法描述如下：

定义第1种情况：当Ti+m字符串不在P0P1…Pm-1字符串出现时，则匹配规则与Sunday算法类似，模式串向右移动m+1距离。

当Ti+m字符串在P0P1…Pm-1字符串中出现时，从左至右依次记下Ti+m字符串在P0P1…Pm-1字符串出现的位置q1q2…qn∈q，且0≤q≤m-1，Ti+m出现的次数可能不止一次。根据Ti+j出现的情况来启发模式串向右移动的距离。

定义第2种情况：当Ti+m字符串在P0P1…Pm-1字符串中出现，且Ti+j字符串不在P0P1…Pj-1字符串中出现时，则说明P0P1…Pj-1可移至Ti+j之后，即P0与Ti+j+1对齐，移动距离为j+1。根据字符串匹配移动最大距离原则，取j+1与m-max （q）较大者max（j+1，m-max（q））橐贫距离。

定义第3种情况：当Ti+m字符串在P0P1…Pm-1字符串中出现，且 Ti+j字符串在P0P1…Pj-1字符串中出现时，从左至右依次记下Ti+j字符串在P0P1…Pj-1字符串中出现的位置k1k2…kj∈k，且0≤k≤j-1，Ti+j出现的次数可能不止一次。第3种情况又分为以下两种情况：

（1）当Ti+m字符串与Ti+j字符串相同，即q[m]等于k[j]，Ti+m字符串与Ti+j字符串相同。若m-j=max（q）-min（k），则比较min（k）与max（q）之间对应pattern字符串是否与substring相等，若相等，则模式串向右移动m-max（q）距离；若不相等，则模式串向右移动m-min（q）距离。若m-j≠max（q）-min（k），则模式串向右移动m-min（q）距离。

（2）当Ti+m字符串与Ti+j字符串不相同，即q[m]不等于k[j]。依次比较q[m]减k[j]的大小。若m-j=q[m]-k[j]，则比较字符串Pk+1…Pq-1，即pattern字符串是否与substring相等，若相等，则模式串向右移动m-max（q）距离（可能有多个相等），若不相等，则模式串向右移动m-min（q）距离；若m-j≠q[m]-k[j]，则模式串向右移动m-min（q）距离。

该算法的核心思想是当匹配失败时，利用文本串当前失败的字符与模式串右对齐端文本串的下一个字符来启发模式串向右移动的距离。结合这两个字符在模式串中匹配的情况以及以这两个字符为首末的子字符串在模式串中的匹配情况来对模式串向右移动最大距离。通过图2与表1详细阐明这种改进算法的具体实现与流程。

图2 改进算法匹配流程

表1 改进算法的匹配过程

序号 文本串 第1次 第2次 第3次 第4次 第5次

0 a a

1 a b

2 b b

3 a a a

4 b b a

5 a b b

6 b a b

7 a a a

8 b b

9 a b a

10 b a b

11 b b

12 a a

第1次： i=0，j=1，k=0，q={1，2}，m-j=3，q-k=1或2，则q-k≠m-j，模式串向右移动m-min（q）距离，即3个距离；

第2次：i=3，j=3，k={1，2}，q={0，3}，当q=3，k=2时，q-k=m-j，而Pk+1…Pq-1字符串与Ti+j+1…Ti+m-1字符串匹配，模式串向右移动m-max（q）距离，即1个距离；

第3次： i=4，j=1，k=0，q={1，2}，m-j=3，则q-k≠m-j，模式串向右移动m-min（q）距离，即3个距离；

第4次： i=7，j=3，k={1，2}，q={1，2}，当q=2，k=1时，q-k=m-j，模式串向右移动m-max（q）距离，即2个距离；

第5次：匹配成功。

可见，改进的算法需要5次匹配，21次字符比较；如果运用KMP算法，则需要6次匹配，27次字符比较；而Sunday算法需要6次匹配，26次字符比较。对文本串T：fdasdgasaexfasdfsagadsdsadf，模式串P：sagadsds，在匹配过程中，KMP算法需要5次匹配，Sunday算法需要5次匹配，BM算法需要4次匹配，改进算法需要3次匹配。

3 实验结果与分析

3.1 实验结果

由于本算法主要针对模式串中字符重复较多的情况，算法匹配的次数主要与需要匹配的文本串重复率与模式串的长度有关。本实验分别用KMP算法、Sunday算法、BM算法及改进的匹配算法进行字符串匹配。表2统计了在模式串长度、模式串字符重复个数以及文本串长度都不同的情况下，各算法的匹配次数。图3统计了在相同模式串长度、不同模式串字符重复个数的情况下，各算法的匹配次数。

表2 各算法及改进算法匹配次数

文本串长度 模式串长度 模式串重复个数 比较次数（次）

KMP

算法 Sunday

算法 BM

算法 改进

算法

94 4 2 37 64 31 28

222 6 3 73 145 81 49

655 7 4 325 217 253 181

1 563 10 5 1 353 1 258 1 267 1 039

图3 各算法以及改进算法匹配次数对比

大量数据测试结果表明，在模式串中字符重复较多的情况下，KMP算法、Sunday算法、BM算法的匹配效率较低，改进的匹配算法占有较大优势，而随着字符重复率的增大，改进的匹配算法优势更加明显。

3. 2 性能分析

在模式串字符重复率较高的匹配下，KMP算法存在着文本串与模式串多个相同字符重复比较的缺陷。Sunday算法没有利用成功的匹配信息与失配文本信息，新一轮的匹配都从首字符重新开始，所以匹配效率并无优势。BM算法利用好后缀与坏字符进行跳转，但在模式串字符重复率较高的匹配中，BM算法有待提高。本文是在相关字符串匹配算法的基础上，针对模式串字符重复率较高的匹配，提出了一种改进的字符串匹配算法，即文本串的i+j位置失配时，利用Ti+m、Ti+j在模式串中的位置q、k与Ti+j+1…Ti+m-1、Pk+1…Pq-1文本串来计算最大移动距离。本算法在最坏的情况下，即Ti+m、Ti+j字符在模式串中重复较多，q与k的值不等，且存在多个q与k值，此时模式串向右移动的距离不一定是1个距离，而是m-max（q）距离。所以本算法在模式串字符重复率较多的匹配中可以提高匹配速度与算法执行效率。

4 结 语

本算法是对模式串中字符重复率较多的匹配而提出的，可大大缩减匹配次数。通过计算文本串当前失败的字符在模式串中的位置与模式串右对齐端文本串的下一个字符在模式串中的位置，来增加模式串向右移动的距离。本文的算法可广泛应用在模式串中字符重复率较大情况下的关键字匹配中。

参考文献

[1]刘萍， 刘燕兵， 郭莉.字符串匹配算法中模式串与文本之间关系的研究[J].软件学报，2010，21（7）： 1503-1514.

[2]闵联营， 赵婷婷.BM算法的研究与改进[J].武汉理工大学学报（交通科学与工程版），2006，30（3）： 528-530.

[3]俞松，郑骏，胡文心.一种改进的KMP算法[J].华东师范大学学报 （自然科学版）， 2009，7（4）：92-97.

[4]王天聪，侯整风，何玲.基于BM的模式匹配改进算法[J].合肥工业大学学报（自然科学版）， 2011，34（3）： 363-366.

[5]刘雨心，孟亮，窦银科.一种改进的 Sunday 字符串匹配算法[J].太原理工大学学报，2013，44（5）： 604-607.

[6] JJ Fan，KY Su. An efficient algorithm for matching multiple patterns[J]. Knowledge and Data Engineering， 1993， 5（2）： 339-351.

[7] L Salmela，J Tarhio. Approximate Boyer-Moore String Matching for Small Alphabets [J]. Computer science， Software engineering，2010，58（3）： 591-609.

[8]胡金柱，熊春秀，舒江波，等.一种改进的字符串模式匹配算法[J].模式识别与人工智能，2013，2（1）：103-106.