字符串匹配算法Sunday的改进*

朱宁洪

(西安科技大学 计算机科学与技术学院，陕西 西安 710054)

摘要：字符串的模式匹配应用十分广泛，在信息的搜索查询等方面具有重要作用，研究串匹配算法的效率具有重要的理论价值和实际意义。在分析几种经典模式匹配算法的基础上，对当前应用最广泛的Sunday算法提出了改进的算法Zhusunday.算法主要改进之处是：在字符串从右向左匹配过程中，当文本字符中出现不匹配模式字符串的字符且该文本字符不是坏字符时，算法从右向左搜索当前文本字符在模式串中出现的位置；找到当前字符在模式串中的位置后继续再向左匹配模式串字符一次，如果仍不匹配时，模式窗口比Sunday算法多向右移动一个字符。改进的算法提高了模式匹配的执行效率，通过大量对比实验证明了该算法的有效性。最后得出结论：在实际应用中，坏字符大量存在的情况下，改进算法的最优时间复杂度可达O(n/m)，在同一时间复杂度下，比Sunday算法效率提高25～50%.

关键词：Sunday算法；Zhusunday算法；模式匹配；坏字符

0引言

字符串匹配问题是计算机科学中的最基本的问题，如何能在最短的时间内确定特征字符串在文本中是否出现过具有重要的意义。在现实中，串匹配的应用十分广泛，主要领域包括：文档编辑、内容管理、计算机病毒检测、信息检索、符号操作、搜索引擎、DNA序列检测以及入侵攻击检测等等[1]。而且，串匹配是这些应用中的关键模块，优良的串匹配算法能大幅地提高应用系统整体的效率[2]。因此，研究字符串的模式匹配算法的效率具有重要的理论价值和实际意义[3]。

设文本串T=T0…Tn-1，n为文本串T的长度；模式串P=P0…Pm-1，m为模式串的长度(n≫m)。在T中寻找等于P的子串，如果在T中存在等于P的子串，则称匹配成功，函数值返回P第一次出现在文本串T中时P的首字符的在T中的下标，否则称为匹配失败，这个搜索过程就是模式匹配[4]。

按照匹配遍历时被查找的模式串个数划分，字符串匹配算法又可以分为2种：单模式匹配和多模式匹配。单模式匹配算法遍历一次可以搜索一个字符串，多模式匹配算法能够在遍历一次的情况下，搜索出文本中模式串里多个模式串的所有出现位置。目前，国内外对于模式匹配算法已有不少的研究成果，比如典型的单模式算法有BF算法、KMP算法、BM算法、Sunday算法，多模式算法主要有AC算法、Wu_Mander算法[5]。鉴于许多单模式搜索算法能够扩展成多模式搜索算法，在此简要介绍4种经典单模式匹配算法。

1几种经典的模式匹配算法

BF算法是效率最低的算法，又称蛮力匹配算法[6]。在文本串中从左到右进行匹配。首先将T[0]与P[0]进行比较，若相等，则逐个比较后续字符；否则，就将T[1]与P[0]进行比较，继续开始下一趟的比较，重复上述过程。算法特点是简单易理解，但时间复杂度较大，为O(m*n)[7]。

KMP算法是由BF改进后不产生回溯的一种算法，每当匹配过程中出现字符串匹配不等时，不需回溯指针，而是利用已得到的“部分匹配”结果将模式向右滑动尽可能远的一段距离后，继续进行比较。模式串不一定向右移动一个字符的位置，右移也不是必须从模式串起点处重新试匹配，也就是模式串可以一次向右移动多个字符的位置，右移后可以从模式串起点后的某处开始试匹配。理论上时间最优复杂度可达到O(m+n)；空间复杂度O(n)[8]。

BM算法在匹配过程中方向是由左向右，但是在比较过程中方向是由右向左[9]，也就是把P同T进行比较时从右向左。当某趟匹配失败时，采用坏字符(在T串中存在而P串中没有的字符称为坏字符)规则和好后缀规则计算模式串右移的距离，并取两者最大值来决定模式串的右移量，移动尽可能远的距离，直到匹配成功或文本串匹配结束。匹配时从右至左进行。BM算法的最坏时间复杂度为O(m*n)，但由于实际应用中这种情况极少出现，因此BM算法仍然得到广泛应用。特别是当发现不匹配的字符时可以使用好后缀和坏字符进行跳转，降低无效的匹配次数[10]。

Sunday算法是最新的对BM算法进行了大幅改进的算法，Sunday算法采用BM算法中的坏字符启发规则，和BM算法相比效率有了较大的提高，在实践中得到了广泛使用，具有新颖性和代表性。下面以在T串“abcoefcacdxdbcd”中查找模式串P“dbcd”的过程来介绍Sunday算法，算法的匹配过程如图1所示。

T串abcoefcacdxdbcd匹配次数Sunday算法模式串p位置×　　　　　　　　　　　　　　　dbcd　　　　　　　　　　　　　　　　　　　　　　　　　　　　od不匹配,o不存在,且下一字符e1=p[0],P窗口向左移5.×　　　　　　　　　　　　　　　dbcd　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　cd不匹配,p中c与T中c对齐,右移1.×√√　　　　　　　　　　　　　　　dbcd　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　ab不匹配,将P中右侧第2个d与T当前d对齐,P窗口右移3.×　　　　　　　　　　　　　　　dbcd　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　bd不匹配,p中右侧第1个b与T当前b对齐,P窗口右移2.√√√√　　　　　　　　　　　　　　　dbcd　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　匹配成功12345(成功)

图1Sunday算法执行情况

Fig.1Implementation of Sunday algorithm

Sunday算法过程叙述如下：开始时模式串P的左边与文本串T的左边对齐；模式匹配过程中进行P与T的比较时，从右向左反向进行比较，反复比较匹配，直到找到模式串或文本串比较完。比较过程中有2种情况1)和2)

1)在发现与P最右侧第一个字符对应位置的T字符不匹配时，又分2种情况A和B：A.当前字符是坏字符因此发生不匹配时，如果T当前字符右面的字符依然不匹配模式串P的第一个字符p[0]，模式窗口向右移动m+1(m为P长度)，如果当前的字符匹配，模式窗口则只向右移动m(m为P模式串的长度)继续下一轮匹配(此时情况与图1中的Sunday算法第一次匹配的情况相同)；B.如果不是坏字符，则在P中由右向左查找T中当前字符，让模式窗口从右向左第一次出现该字符的地方与T中当前字符对齐，继续下一轮的匹配(此时情况最常见，与图1中的Sunday算法第2次和第4次匹配的情况相同)；

2)在发现与P最右侧第一个字符对应位置的T字符匹配时，P向左取第二个和T再向左取的第二个字符继续匹配，一直匹配到字符不同或匹配完p串。也有2种情况C和D：C.如果未能匹配完，则T当前的不匹配字符d与在模式串中从右侧第一次出现d的位置对齐，继续下一轮的匹配；(此时情况与图1中的Sunday算法第3次匹配的情况相同)D.如果一直匹配，直到P所有字符匹配完，则返回T中与P[0]对应的开始位置作为匹配位置，算法结束(此时情况与图1中的Sunday算法第5次匹配的情况相同)。

Sunday算法在最坏情况下的计算复杂度为O(m*n)。但是在实际使用中文本串的坏字符出现概率非常高，最好情况(在找到P串以前遇到的字符都是坏字符)下的时间复杂度可达到O(n/m)，所以在实践中应用广泛。Sunday算法是目前单模式匹配算法中比较成熟，且效率最高的一种。

2Sunday算法的改进

下面是用Sunday算法和改进的算法(称之为Zhusundays算法)进行模式串匹配的一个例子，具体说明2个算法相同部分和不同

文本串T=“abcoefcacdxdbcd”，模式串P=“dbcd”.Sunday算法和Zhusunday算法在模式窗口中都由右向左匹配。Sunday算法匹配过程(如图1所示)上面已经叙述完毕，下面叙述Zhusuanday算法，其具体匹配过程如图2所示。

Zhusunday算法针对Sunday算法最常见的(1)B和(2)C情况进行了改进，其余部分和Sunday算法一样。改进之处在于

T串abcoefcacdxdbcd匹配次数zhusuanday算法模式串p位置×　　　　　　　　　　　　　　　dbcd　　　　　　　　　　　　　　　　　　　　　　　　　　　　od不匹配,o不存在,且下一字符e1=p[0],P窗口向左移5.×　　　　　　　　　　　　　　　dbcd　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　cd不匹配,P中右侧第1个c与T中c对齐,P窗口右移1;同时,P串c左侧b与对应T串c左侧字符a不同,P窗口需再右移1.×　　　　　　　　　　　　　　　dbcd　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　dx不匹配,x不在P串,T下一字符d==p[0],P窗口右移4.√√√√　　　　　　　　　　　　　　　dbcd　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　匹配成功1234(成功)

图2Zhusunday算法执行情况

Fig.2Implementation of Zhusunday algorithm

1)在Sunday算法最常见的(1)B情况(也就是不匹配，且不是坏字符，向前不能完全匹配，与图1中的Sunday算法第2次和第4次匹配的情况相同)下，只让P中当前字符与T对应的字符对齐，对齐是假定T当前字符左侧的字符与P当前字符左侧的字符相同(2个连续字符都相同一般情况下是不常见的)，已经在P中从右向左查找到了当前字符，但是，如果假定不成立，就可以多移动一个字符的位置，算法开销的成本就是多比较一个字符，这种情况和图2中Zhusunday算法第2次匹配一样。如果相同，就和原来移动步数一样。让我们来分析一下改动之后效率：如果比较一次，字符不匹配时将多移动模式窗口一个字符位置(这是大概率事件)，如果不比较，按照Sunday算法移动模式窗口一个字符位置，需要的执行步数，首先要判断对应位置字符是否匹配(需要比较1次)，不匹配(大概率事件)，则先判断是否属于坏字符，需要m次比较，如果不是坏字符，再查找在模式串中的位置，查找位置平均需要m/2次，才决定移动字符数(最多m个字符，最少1个字符，平均(m+1)/2个字符，各种情况下总比较次数为1+m+m/2，除以平均次数(m+1)/2，大约为3，也就是平均移动一个字符，比较要3次)；而改进后的算法，基本上属于移动一次，需要比较一次(大概率事件)，这样就显著提高了算法效率。针对图1，Sungday算法第2次匹配和Zhusunday算法第2次匹配面临相同的情况，两算法却做出了不同操作，Zhusunday算法第2次匹配多向右移动了一步，导致最后算法效率的不同。同样的情况发生在(2)C情况下，这里也对Sunday算法进行了改进；这时也向左多判断一个字符，多数情况下也会让匹配窗口多向右移动一步。在本示例中，以上算法的改动让Zhusunday算法匹配次数比Sunday算法少了一次。

3算法实现

根据上面的算法分析，采用C语言实现了Zhusunday算法，该算法整体采用循环结构，首先是双分支，分出前面叙述的(1)和(2)2种情况

1)又分成A和B 2种情况，在B情况下，再向前判断，又分2种情况：①不匹配，模式窗口前进多增加1字符；②匹配，模式窗口按照原来Sunday算法计算的步长移动；

2)又分成C和D 2种情况，和上面的叙述一致，下面是C语言的实现该算法的源程序，相关注释进行了说明。

int zhusunday(char *T，char *p，int pos)//pos是T中下标开始位置，主体算法

{int Tindex=pos+lengthP-1；

int pindex=lengthP-1；

//Tindex是在T中搜索的当前位置，采用从右向左探索

int pipeipos；

while(Tindex≤lengthT-1)//遍历源串T

{

pipeicishu++；//2种情况1和2.

if(T[Tindex]!=p[pindex])//不匹配模式串p最后一个字符，有2种情况，分别是1和2.

{if(dist[T[Tindex]]==lengthP)//1A：目标字符不在模式串中，是坏字符；dist是模式串预处理数组，对0～127的ASCII字符能使模式窗口向右移动距离进行了预先统计。

if(T[1+Tindex]!=p[0])//多验证坏字符左侧的一个字符。

Tindex+=lengthP+1；//跳跃模式串长度个字符探索，验证成功比坏字符多跳一个。

else //验证不成功，跳跃模式串长度个字符。

Tindex+=lengthP；

else//1B：改进处：目标字符在模式串中，但不是模式串最后一个字符；

{intx=lengthP-2-dist[T[Tindex]]；//x是由右向左第一次不匹配时字符的下标，因为没有全匹配，其值不能小于0.

if(p[x]!=T[Tindex-1]&&x>=0)

Tindex+=dist[T[Tindex]]+1；

else //这种情况多数不成立(而Sunday算法假定这里始终成立)。

Tindex+=dist[T[Tindex]]；

}

}

else//2：匹配模式串的最后一个字符，回溯追查，对应2种情况，分别是C和D.

{pipeipos=quanpipei(T，p，Tindex，lengthP-1)；//从最后一个字符向前进行匹配

if(pipeipos!=0)//C：由后向前部分字符匹配，没有全匹配。这里也对Sunday进行了改进。

{intx=lengthP-2-dist[T[Tindex]]；

//x是由右向左最后一次匹配的字符左侧的字符的下标，因为没有全匹配，其值不能小于0.

if(p[x]!=T[Tindex-1]&&x>=0)

Tindex+=dist[T[Tindex]]+1；//多移动

else

Tindex+=dist[T[Tindex]]；

}

else//D：所有字符全匹配。

return Tindex-lengthP+1；//返回匹配的起始下标。

}

}

if(Tindex>=lengthT)//匹配结束，依然没有返回，表示未匹配成功。

return-1；

}

4实验结果评测

为了评测该算法的性能，对算法运行的匹配次数和语句执行次数进行了比较。针对图1和图2列举的情况，两算法运行结果显示如图3，程序对前面的实例进行了验证，得出了Sunday算法匹配5次和Zhusunday匹配4次的结果；同时，在两算法的执行语句的位置旁都添加了全局变量count的自增语句作为计数器，来统计两者时间复杂度的依据，运行结果显示，优化后的Zhusunday执行了17步，Sunday算法执行了25步，是原算法执行步数的68%，同时针对不同数据进行了多次验证，结果都显示Zhusunday优于Sunday算法，特别是针对模式串P后缀在文本串T重复率高的情况，优化比率更明显。由于该实例T中大量包含模式串P中的字符，Zhusunday的执行次数在1.1n左右，达到17次；Sunday执行次数为1.7n左右，达到25次。在实际中经过大量测试，在坏字符大量存在的情况下，二者的时间复杂度逐渐接近O(n/m)，基本一致，但Zhusunday算法的执行次数始终优于Sunday算法，Zhusunday算法的执行次数约为Sunday算法执行次数的65%～80%之间，效率提高25%～50%.限于篇幅，更多的比较结果这里不再一一列举显示结果。

图3　2种算法比较程序运行结果Fig.3　Comparison of two algorithm program results

5结论

文中针对当前研究的热点字符串匹配算法(Sunday算法)，提出了改进的算法Zhusunday，并对两者算法进行了分析和实现，并通过实验验证了Zhusunday优于Sunday算法。经过大量实际测试，在坏字符大量存在的情况下，Zhusuanday算法能达到O(n/m)的时间复杂度，且Zhusunday算法的效率比Sunday算法提高25%～50%.

参考文献References

[1]潘冠桦.单模式字符串匹配算法效率的研究[D].太原：太原理工大学，2013.

PAN Guan-hua.Research on the efficiency of single mode string matching algorithm[D].Taiyuan:Taiyuan University of Technology, 2013.

[2]孙艺珍，季小迪，张京涛.基于.Net的全文搜索引擎设计与实现[J].西安科技大学学报,2014，34(6)：701.

SUN Yi-zhen,JI Xiao-di,ZHANG Jing-tao.Design and implementation of full text search engine based on .Net[J].Journal of Xi’ an University of Science and Technology，2014，34(6)：701.

[3]马莉，李树刚，肖鹏，等.云计算环境下煤矿应急管理海量数据存储技术[J].西安科技大学学报,2014，34(5)：596.

MA Li,LI Shu-gang,XIAO Peng,et al. Mass data storage technology of coal mine emergency management in cloud computing environment[J].Journal of Xi’ an University of Science and Technology，2014，34(5)：596.

[4]李军民，李立博.人工鱼群和蒙特卡罗混合算法的应用[J].西安科技大学学报，2014，34(2)：224.

LI Jun-min,LI Li-bo.Application of artificial fish swarm and Monte Carlo hybrid algorithm[J].Journal of Xi’ an University of Science and Technology，2014，34(2)：224.

[5]巫喜红，凌捷.基于字符频率的字符串模式匹配算法的研究[J].制造业自动化，2013，35(9)：11-14.

WU Xi-hong,LING Jie.Research on string pattern matching algorithm based on character frequency[J].Manufacturing Automation,2013,35(9):11-14.

[6]许元飞 基于纹理的图像检索算法研究[J].西安科技大学学报,2013，33(4)：470.

XU Yuan-fei.Research on texture based image retrieval algorithm[J].Journal of Xi’ an University of Science and Technology，2013，33(4)：470.

[7]徐珊，袁小坊.Sunday字符串匹配算法的效率改进[J]．计算机工程与应用，2011，47(29)：96-98.

XU Shan,YUAN xiao-fang. Efficiency improvement of Sunday string matching algorithm[J].Computer engineering and Application,2011，47(29)：96-98.

[8]潘冠桦，张兴忠.Sunday算法效率分析[J].计算机应用，2012，32(11)：3 082-3 084.

PAN Guan-hua,ZHANG Xing-zhong.Efficiency analysis of Sunday algorithm[J].Computer Applications,2012，32(11):3 082-3 084.

[9]冯川放.规则引擎技术的可配置EOS平台的设计与实现[J].西安科技大学学报，2013，33(3)：353.

FENG Chuan-fang. Design and implementation of configurable EOS platform for rule engine technology[J].Journal of Xi’ an University of Science and Technology，2013，33(3)：353.

[10]李明月，张善卿，陆剑锋，等.一种改进的Sunday匹配算法[J].杭州电子科技大学学报，2015，35(1)：93-97.

LI Ming-yue,ZHANG Shan-qing，LU Jian-feng,et al.An improved Sunday matching algorithm[J].Journal of Hangzhou Electronic and Science University,2015，35(1)：93-97.

Improvement of Sunday pattern matching algorithm

ZHU Ning-hong

(CollegeofComputerScienceandEngineering,Xi’anUniversityofScienceandTechnology,Xi’an710054,China)

Abstract:String pattern matching is widely used in information search and query，and it is important to study the efficiency of the string matching algorithm with theoretical value and practical significance.On the basis of the analysis of several classical pattern matching algorithms，the paper puts forward a Zhusunday algorithm which is improved from the most widely used Sunday algorithm.The improved position of the algorithm is：in the matching process from the right of the text string to the left，when the character of the text does not match the character of the pattern string，it is not a bad character，the algorithm searches the position of the current text character from the right to the left in the pattern string.After finding the position，the improved algorithm continues to match the two characters in the left for another time.If there is no match，the pattern window will move to right one step more than the movement of Sunday algorithm.The improved algorithm improves the efficiency of the pattern matching，and the effectiveness of the proposed algorithm is proved by a lot of experiments.Finally the paper draws a conclusion：in practical application there are a large number of the bad characters，the optimal time complexity of the improved algorithm isO(n/m)，and at the same time complexity，the improved algorithm is more efficient than the Sunday algorithm by 25～50%.

Key words：Sunday algorithm；Zhusunday algorithm；pattern matching；bad character

中图分类号：TP 391

文献标志码：A

作者简介：朱宁洪(1969-)，男，山东兖州人，讲师，E-mail:zhuninghong@sohu.com

基金项目：国家自然基金(煤炭联合基金)(U1261114)

收稿日期：*2015-07-29责任编辑：高佳

文章编号：1672-9315(2016)01-0111-05

DOI：10.13800/j.cnki.xakjdxxb.2016.0119