KMP模式匹配算法的研究分析

计算机与数字工程

Computer&DigitalEngineeringVol.38No.5

󰀁38

KMP模式匹配算法的研究分析

杨战海

(延安大学计算中心󰀁延安󰀁716000)

*

摘󰀁要󰀁通过对字符串模式匹配算法和KMP算法的研究,分析了一种改进KMP算法的方法,并通过对算法的复杂性进行计算,结果表明,改进后的KMP算法和KMP算法的时间复杂度均为O(m+n),但改进后算法的平均比较次数约为未改进算法的平均比较次数的0.833倍,因此改进后的KMP算法更能提高字符串模式匹配的工作效率。

关键词󰀁模式匹配;KMP算法;算法;next函数中图分类号󰀁TP301

ResearchandAnalysisofKMPPatternMatchingAlgorithm

YangZhanhai

(ComputerCenter,Yan󰀁anUnversity,Yan󰀁an󰀁716000)

Abstract󰀁ThispaperanalyzesanimprovedmethodofKMPalgorithmandcalculatesthecomplexityofthealgorithmthroughresearchingthestringpatternmatchingalgorithmandtheKMPalgorithm.Theresearchshowsthatthetimecom-plexityoftheimprovedKMPalgorithmandKMPalgorithmarebothO(m+n),buttheaveragenumberoftimesoftheim-provedalgorithmis0.833timesmorethanthatoftheunimprovedalgorithm.Therefore,theimprovedKMPalgorithmcanfurtherincreasetheworkefficiencyofstringpatternmatching.

KeyWords󰀁patternmatching,KMPalgorithm,algorithm,nextfunctionClassNumber󰀁TP301

1󰀁引言

模式匹配问题是计算机科学研究领域研究的热点问题之一[1]。子串在主串中的定位操作通常称为串的模式匹配,它是各种串处理系统中最重要的操作之一。模式匹配算法广泛应用在文本编辑、情报检索、拼写检查、基于字典的语言翻译、WWW搜索引擎、计算机病毒特征码匹配、数据压缩、DNA序列匹配等计算机应用系统中。串匹配从方式上可分为精确匹配、模糊匹配、并行匹配等,著名的匹配算法有BF算法、KMP算法、BM算法及一些改进算法研究。

[2~5]

2󰀁简单的模式匹配算法

简单的模式匹配问题[1]的基本描述为:给定一个特定的字符串P(称为模式串),在一个大的文本T(称为匹配主串)中进行查找,确定P是否在T中出现,如果出现,则给出相应的出现位置。

为了使用数学语言对简单的模式匹配算法进行描述,做以下符号约定:模式串记作P;要匹配的主串记作T;模式串长度记作m;要匹配的主串长度记作n;模式串第一个字符和最后一个字符分别记作P1和Pm;要匹配的主串第一个字符和最后一个字符分别记作T1和Tn。

有了以上约定,简单的模式匹配算法的数学语言描述为:

。本文主要在精确匹配方面对

KMP算法和改进后的KMP算法做了一定的分析

*

收稿日期:2010年1月18日,修回日期:2010年2月10日

基金项目:陕西省教育厅(编号:09BY37)资助。

作者简介:杨战海,男,硕士研究生,讲师,研究方向:计算机算法、网络安全。2010年第5期计算机与数字工程󰀁39

已知有一长度为n的文本字符串:T=T1,T2,󰀁,Tn

和一个长度为m(m󰀁n)的模式字符串:P=P1,P2,󰀁,Pm

其中文本字符串T和模式字符串P,两者都是由字符构成的有序集合,文本T定义在一个有限的字母表󰀁上,字母表长度大小为󰀁。

在主串T中是否存在长度为m的子串:T󰀁=Ti+1,Ti+2,󰀁,Ti+m能够满足

Ti-j=Pj(j=1,2,󰀁,m)

当主串T的长度n不是很大时,可以采用一种简易的强行搜索算法,算法描述如下:

1)令i󰀁1,j󰀁1,k󰀁1;

2)若(i󰀁n)且(j󰀁m),则转向步骤3)。否则,转向步骤4);

3)若Ti=Pj,则令i󰀁i+1,j󰀁j+1。否则令k󰀁k+1,i󰀁k+1,j󰀁1。然后转向步骤2);

4)若j>m,则输出得到匹配的信息,结束。否则,输出匹配失败信息,结束。

强行搜索算法的本质上就是将模式P和文本T从左向右逐个搜索,如果模式P在某一位匹配失败,则将模式T向右移动一位,仍从模式P的第一位向右开始进行搜索。这种算法的正确性是显然的,但是存在的问题也是明显的,那就是效率不高,在最坏的情况下,要执行m(n-m+1)次字母的匹配的运算

[6]

成功的匹配,将j右移尽可能地大,而提高匹配的效率,因此问题的关键是寻找模式串自身的规律。

假设在模式匹配过程中,当前正执行到Ti和Pj(1󰀁i󰀁n,1󰀁j󰀁m)。

1)若Ti=Pj,则继续向右匹配,即检查Ti+1和Pj+1是否相匹配。

2)若Ti󰀁Pj,则需要考虑以下情况:

若j=1,则执行Ti+1和Pj+1的匹配,即把模式和主串各自向右移动一个字符位置后再从头开始进行匹配。

若1󰀁j󰀁m,则需要选择模式的适当位置,记作next[j],执行Ti和Pnext[j]的匹配,此时,相当于把模式模式和主串各自向右移动j-next[j]个字符。模式next[j]位置前面的各个字符己与主串中最前面的字符匹配,因此只需要从模式的next[j]位置的字符开始继续匹配即可。

重复上述过程,直到j>m或者i>n-m+1为止。

一般在某次试匹配时,若Ti󰀁Pj,即模式的前j-1个字符全能匹配,如果事先知道子模式有一个最长的部分首字串和它的部分尾串相等,即P1,P2,󰀁,Ps=Pj-s,Pj-s+1,󰀁,Pj-1,那么,在下一次匹配时,可把模式串向右移动j-s-1个字符位置,使得P1与Tj-s对齐,但是这时候只需从Ps+1(它与Ti对齐)起检查匹配情况。

为了达到不遗漏可能完全匹配的情况,上述的部分首字串必须是最长的,所以对于任何一个子模式P1,P2,󰀁,Pj(1󰀁j󰀁n),󰀁自匹配󰀁的部分字串是唯一的,它只和模式自身的结构有关。

数组next[j]表示当模式中第j个字符与主串中相应字符匹配失败时,在模式中需重新和主串中该字符进行比较的字符的位置,其值取决于模式本身,与主串无关。选择模式的适当位置,即计算next[j]是KMP算法中的关键,函数表达如下:

voidget_next(sstringP,int&next[],intm){

//求模式串P的next函数值并存入数组next。intj,k;

j=0;k=-1;next[0]=-1;while(j󰀁󰀁if(k==-1||P[j]==P[k])󰀁󰀁󰀁󰀁{j++;k++;next[j]=k;}󰀁󰀁else

󰀁󰀁󰀁󰀁k=next[k];}。

3󰀁KMP算法

KMP算法是一种改进的字符串匹配算法,由D.E.Knuth与V.R.Pratt和J.H.Morris同时发现[1,6,8],因此人们称它为克努特-莫里斯-普拉特操作。该算法主要消除了主串指针(i指针)的回溯,利用已经得到的部分匹配结果将模式串右滑尽可能远的一段距离再继续比较,从而使算法效率有某种程度的提高,KMP算法的时间复杂度都为O(m+n)

KMP算法的基本思想

[6~10]

[9~10]

。

是,当Ti和Pj匹配

成功时,主串指针i和模式串指针j各加1,继续向后进行匹配。而如果Ti和Pj匹配不成功时,主串指针i不动,j指针也不回到第一个位置,而是回到一个恰当的位置,如果这时让j指针回到第一个位置,就可能错过有效的匹配,所以在主串指针i不动的前提下,j指针回到哪个位置是问题的关键,既不能将j右移太大,而错过有效的匹配,另一方面,又要利用󰀁40杨战海:KMP模式匹配算法的研究分析第38卷

利用模式串的next函数求模式串P在主串T中KMP模式匹配函数如下:

intkmp(sstringP,sstringT,intnext[]){

inti=0,j=0;m=len(P);n=len(T);

while(j󰀁󰀁if(j==-1||P[j]==T[i])󰀁󰀁󰀁󰀁{i++;j++;}󰀁󰀁else

󰀁󰀁󰀁󰀁j=next[j];if(j>=m)󰀁󰀁return(i-m);else

󰀁󰀁return(0);}

法中的i不是保持不变,而是增加了,这就意味着加快了模式匹配的进度。4.2󰀁算法的分析

KMP算法时间复杂度可分两部分来进行分析,一部分是扫描算法中T[i]与P[j]的比较次数,另一部分是根据模式来计算next[j]的工作量。计算next[j]与模P的长度m有关,与主串无关,其算法时间复杂度为O(m)。因为KMP算法与改进的KMP算法涉及的计算next[j]的工作量相同,所以这两个算法的时间复杂度主要区别在是否有󰀁if(i+j-k󰀁m&&P[j]!=T[i+j-k])i=i+j-k;󰀁这句上,设p(m,n)与q(m,n)分别为KMP算法和改进KMP算法中T[i]与P[j]的平均比较次数,则考虑到:

if语句的两个分支出现的概率相等,平均出现次数为n/2;

else分支语句取得n/2个next[j]后,i不得增加却又投入了比较,使得在同一个i位置上增加了一次比较,因此:

p(m,n)=n+n/2+m=1.5n+m。

在改进的KMP算法中的语句󰀁if(i+j-k󰀁n&&P[j]!=T[i+j-k])i=i+j-k;󰀁的平均出现次数为n/2,该分支语句使得i向右󰀁滑动󰀁的机会增加了n/4次,这些机会不是使i保持不变,而是使i朝着匹配处前进了亦即促进了模式匹配的进度,因此:

q(m,n)=1.5n-n/4+m=1.25n+m令m为恒定值,故而

q(m,n)1.25n+m=lim=0.833

p(m,n)n󰀁󰀂1.5n+m

可见,p(m,n)与q(m,n)同阶,它们的时间复limn󰀁󰀂

杂度都为O(m+n),但q(m,n)的系数要比p(m,n)的低,因此改进后的KMP算法更能提高字符串模式匹配的工作效率。

4󰀁改进的KMP算法

4.1󰀁算法的基本思想

虽然模式匹配KMP算法的引入避免了BM算法中频繁的回溯

[6~7]

,普遍提高了模式匹配的工

作效率,但是经过分析,对KMP算法扫描部分还可做进一步的改进,下面介绍改进KMP算法的基本思想。

基本思想:每当某趟匹配失败时,i指针不必回溯,而是利用己经得到的󰀁部分匹配󰀁结果,看看是否有必要将i的值进行调整,然后再将模式向右󰀁滑动󰀁若干位置后继续比较。在计算KMP算法中计算next[j]是,加入语句󰀁if(i+j-k󰀁m&&P[j]!=T[i+j-k])i=i+j-k;󰀁。因此,主串指针i增加了变化,从而适当的提高匹配的效率。

根据改进的KMP算法的基本思想,对于字符串模式匹配实例P=\"abaabc\"和T=\"abaab-ghjwabaabch\"匹配过程如下:

第一次匹配结束时,在j=6处不匹配,i指针的值为6,j指针的值为6。为描述方便起见,当前正在匹配的字符用括号加以标记,匹配状态如下:

abaab(g)hjwabaabchabaab(c)

5󰀁结语

本文针对模式匹配算法中KMP模式匹配算法在匹配过程中存在的一些不足进行了改进,给出了一种改进的KMP改进算法的设计思想、原理,并对其进行了详细的描述和分析,改进后的算法在某种程度上可以减少不必要的比较次数,提高了模式匹配的效率。

参考文献

[1]俞文洋,张连堂,段淑敏.KMP模式匹配算法的研究模式串向右移动3位后,开始第二次匹配开始,此时i指针的值为9,j指针的值为3,匹配状态如下:

abaabghj(w)abaabchab(a)abc

即从主串的第9位开始比较,改进的KMP算

2010年第5期

[J].郑州轻工业学院学报,2007,22(5):64~66

计算机与数字工程

2003:79~84

󰀁41

[2]秦锋,汤文兵,章曙光,等.数据结构[M].合肥:中国科

学技术大学出版社,2007:101~102

[3]刘玉龙,刘啸.一种模式匹配快速算法[J].计算机科

学,2008,35(1):219~220

[4]李小英.一种改进的KMP字符串匹配算法[J].忻州师

范学院学报,2006,22(5):119~121

[5]王战红,张柯,姚瑶.一种KMP算法中求nextval数组的

改进算法[J].信阳师范学院学报,2008,21(2):285~287[6]严蔚敏,吴伟民.数据结构[M].北京:清华大学出版社,

[7]汤亚玲.KMP算法中next数组的计算方法研究[J].计

算机技术与发展,2009,19(6):98~101

[8]李桂玲.一种改进的KMP模式匹配算法[J].吉林工程

技术师范学院学报,2009,25(10):75~77

[9]鲁宏伟,魏凯,孔华峰.一种改进的KMP高效模式匹配

算法[J].华中科技大学学报,2006,34(10):92~97[10]NavarroG,FredrikssonK.Averagecomplexityofexact

andapproximatemultiplestringmatching[J].TheoreticalComputerScience,2004,321(223):283~290

(上接第24页)

󰀁󰀁1)目标点1坐标为(50km,-50km),󰀁1=1.8,󰀁1=8.2,Pi1=0.21;目标点2坐标为(48km,-40km),󰀁2=3.5,󰀁2=6.4,Pi2=0.26,t=0.7;

2)导弹1的位置(0,0);导弹2的位置(9km,-2km);导弹3的位置(5km,-13km);导弹4的位置(1km,-19km);

3)各导弹对同一目标的攻击能力相同,杀伤率为某一定值,且攻击是独立的;

4)遗传算法代数设置100代,种群大小设置100,A=9.0903438,Pcmax=0.9,Pcmin=0.2,Pmmax=0.12,Pmmin=0.009,󰀁1=󰀁2=0.5。

仿真得到优化后的航路如图5所示,图中航路有交叉点,但是导弹经过这些交叉点的时间不同,所以不存在相

图5󰀁协同航路规划结果

6󰀁结语

本文提出的协同航路规划方法能够对攻击目标进行合理分配,并保证导弹能以较小的代价同时到达各自指定的目标点以达到任务的突然性。实验结果也表明该方法能够有效地分配目标和得到较好的协同航路。

参考文献

[1]王有为,周智超.反舰导弹航迹规划决策分析[J].飞航

导弹,2009(2):11~15

[2]沈建锋,许诚,陈峰.遗传算法在反舰导弹航路规划中

的应用[J].飞行力学,2005,23(3):52~55

[3]沈建锋,王丕毅,杨大鹏,等.利用遗传算法进行倾斜发

射反舰导弹航路规划[J].海军航空工程学院学报,2008,23(2):174~180

[4]徐清华,李中良,沈闽峰,等.基于遗传算法反舰导弹航路

规划研究[J].火力与指挥控制,2008,33(增刊):57~61[5]JohnBellingham,MiehaelTillerson,ArthurRichardsand

JonathanP.How,mult-itaskallocationandPathPlanningforCooperatingUAVsCooperativeControl[C]//Medels,ApplicationsandAlgorithmsattheConferenceonCoord-ination,ControlandOptimization,2001,11

[6]BrownD.T.RoutingUnmmannedAerialVehicles

whileConsideringGeneralRestrictedOperatingZones[D].Master󰀁Sthesis,AirForceInstituteofTechnolo-

碰撞的问题。

这4枚导弹在满足时间协同的同时,也使编队整体的威胁和航路代价最小化了,同时使目标的毁伤效能最大化了。从仿真结果来看,该方法达到了预期的效果。图6是航路总长的进化曲线,表明该方法在50代左右就已基本满足协同的要求。图7是费效比的进化曲线,可以看出此方案和航路使费效比达到了最大。

gy,Wright-PattersonAirForceBase,Ohio,USA,2001,3

[7]柳长安,王和平,李为吉.攻击无人机的协同航路规划

[J].西北工业大学学报,2003,21(6):707~710[8]叶媛媛.多UCAV协同任务规划方法研究[D].国防科

学技术大学工学博士学位论文,2005

[9]金晶,苏勇.一种改进的自适应遗传算法[J].计算机工

程与应用,2005(18):63~68