《基于kmp算法的改进算法kmpp-李莉.pdf》由会员分享，可在线阅读，更多相关《基于kmp算法的改进算法kmpp-李莉.pdf（5页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、cD挣驴秘盯E挖gi嚣gP以摊g口搿d彳弹&affo拜s计算机工程与应用 2016，52(8) 33基于KMP算法的改进算法KMPP李 莉1，江育娥1，林 劫1，江秉华2LI Lil，JIANG Yue1，LrN Jiel，JIANG Binghua21福建师范大学软件学院，福州3501002南京医科大学病理系，南京2100291Faculty of Software，Fujian Nomal UniVersity，Fuzhou 350100，China2，Department of Pathology，Nanjing Medical UniVersity，Nanjing 2 1 0029，C
2、hinaLI Li，JIANG Yue，LIN Jie，et a1Improved algorithm KMPP based on KMP：Computer Engineering and AppHcations，2016，52(8)：3337Abstract：KMP algorithm and BM algorithm are classical single pattem matching algorithms，because the pointer“n thetext can only moVe one character at each time in KMP algorithm，th
3、e oVerall matching emciency is not hi曲，the improVedalgorithm(KMPP)accordingly to combine the adVantages of the KMP algorithm with BM algorithm together is proposedThe core of KMPP algorithm is when a mismatch occurs at position，it calculates the position in the text where the lastcharacter of pattem
4、 will align wim aRer the pattem moVing the Value of以眈，】If the last character of pattem does notmatch with the corresponding text position，the bad character rules are叩pliedThe moving distance of pointer f in thetext is a twostep jumping distance，thus the pointer can move farthest at each timeThe expe
5、rimental result shows that thecomparison number of KMPP algorithm is far 1ess than the KMP algorithms number and it improves the emciency ofpattem matching algorithmKey words：pattem matching；KMP algorithm；BM algorithm；KMPP algorithm摘 要：KMP算法和BM算法是经典的单模式匹配算法，但KMP算法中文本指针f每次只能移动一个字符，整体的匹配效率并不高，结合KMP算法和
6、BM算法的优点提出一种改进算法(KMPP)。算法的思想是模式串与文本在7处不匹配时，预算出模式串移动n蹦f力后末字符在文本中的位置，当该位置的文本字符与末字符不匹配时，则用该字符进行坏字符匹配，这两步的跳跃距离就是文本指针f移动的距离，从而使指针f每次移动的距离达到最大。实验结果表明，该算法匹配次数远低于KMP算法的匹配次数，提高了模式匹配的效率。关键词：模式匹配；KMP算法；BM算法；KMPP算法文献标志码：A 中图分类号：TP311 doi：103778iissn10028331140504261 引言在当前大数据的时代，无论是金融、文学、生物信息还是计算机领域，文本都是必不可少的信息组成
7、元素。面对不断出现的大量文本，如何快速精确地找到文本中需要的信息成为研究的重点。目前的互联网正面临着越来越严重的网络安全问题，网络入侵涉及到网络信息的保密性、完整性、可用性、真实性和可控性，因此入侵检测技术成为当前的研究热点，而精确字符匹配算法效率的提升对提高网络入侵检测系统(NIDs)的性能起到很大的作用。随着各个基金项目：国家自然科学基金重大国际(地区)合作研究项目(No81320108叭9)；福建省自然科学基金(No2014J01220)。作者简介：李莉(1991一)，女，硕士，研究方向为软件工程、数据挖掘，Email：529396211qqcom；江育娥(1970一)，女，博士，教授，
8、研究领域为数据挖掘；林劫(1972一)，通讯作者，男，博士，副教授，研究领域为序列算法、生物信息学、数据挖掘；江秉华(1962一)，男，博士，教授，研究领域为分子生物学、生物信息学。收稿日期：20140603 修回日期：20140814 文章编号：10028331(2016)08003305cNKl网络优先出版：2014121l，http：wwwcn kinetkcmsdetail川2127TP201412111526043_html万方数据c0州，“幼一E，lg砌PPrf刀g耐彳即zic口ffD胛J计算机工程与应用领域的关联性的提高，产生的文本数据量越来越大，很多领域都需要在大量信息中查找特
9、定的信息。例如生物信息领域中的DNA测序定位、航海领域中的海洋数据查询、计算机领域中的高效搜索引擎等。由此可见，寻找更有效的字符串匹配算法是当务之急。本文结合经典的单模式匹配算法KMP和BM的优点，提出一种更高效率的匹配算法KMPP(KMP Plus)，该算法不仅仅在匹配次数上远低于经典算法BF与KMP，而且在时间性能上也大大提高了，KMPP算法针对文本查找信息的效率有很大的提高。2相关算法分析在介绍相关的算法前，先作以下的定义：文本表示为丁=丁0，l，以一1】，长度为力；模式串表示为尸=P0，1，m一1】，长度为m；并且满足条件力m。如果存在f1吏得：rf】=Po，rf+1=P1，rp+，l
10、一1=Pm1，那么模式串P就出现在文本丁的f处。单模式匹配问题就是找出文本丁中所有匹配的模式串P的起始位置。单模式匹配经典算法包括基于字符比较的匹配算法、基于自动机的匹配算法、基于位平行的匹配算法、常量空间字符串的匹配算法“，。本文论述的算法是基于字符比较的单模式匹配算法。基于字符比较的主要匹配算法有BF(BruteForce)算法“、KMP(KnuthMorrisPratt)算法、BM(Boyer-Moore)算法等，其改进算法主要有BMH算法例、QS算法M、AKc算法、针对next函数进行修改的KMP改进算法(下文称为NKMP算法)91等。本文主要是在KMP算法的基础上，提出新的改进算法K
11、MPP(KMP Plus)，并将KMPP与KMP、BM、NKMP算法的性能做了对比，理论与实验均证明KMPP的性能高于BM、KMP、NKMP算法。21 KMP算法1969年Knuth、Morris和Pratt提出快速单模式匹配算法KMP算法。1。KMP算法消除了BF算法中的指针f回溯问题。比较过程中模式串是从左往右移动，字符比较也是从左往右比较。若丁f=P力，则继续比较丁f+1-P，+1】；若rf】!=PL力，则f值不变，值等于以蹦f刀，再进行下一轮的匹配。其中n甜f刀的值表示尸0，l，1】中最长后缀的长度，且这个最长后缀等于相同字符序列的前缀，对next数组的定义如下：蹦f(，)=一1，黝=
12、o时m瓮鬻警篱一2 0一tt一川0一，存在)0，其他情况在下一次匹配时只需确定u，的位置即可，从而提高模式匹配的效率，KMP算法的时间复杂度为D(埘+”)。表1表1 KMP算法匹配过程序号文本串第一次第二次第三次第四次第五次第六次第七次为KMP算法匹配过程，其中辟“acbccadbacbacc”，尸=“acbacc”。2001年，复旦大学朱洪教授主要针对KMP匹配算法的预处理next函数进行修改，在计算，l甜f刀值时，多加一步判断P，z“f佃P刀“。这种改进算法主要针对的是特殊的字符串，例如仁“aabaabaac”，即在模式串中出现P胛似rL力-pL力的次数越多，且文本出现这种模式串越多，提高
13、的效率就越高。NKMP算法的时间复杂度为0(m+，z)，2010年杨俊丽也对此改进算法进行分析研究州。2006年华东科技大学鲁宏伟教授根据自定义的特征值|提出一种新的模式匹配算法。当此改进算法的七值几乎为1时，即，l眈f力的值大部分为0时，该算法的提高效率并不高n“。综合两种改进算法的比较结果，最终采用运行效率更好的NKMP算法进行比较论述。22 Boye卜Moore(BM)算法1977年Boyer和Moore提出了著名的BM算法H，BM算法在进行匹配的时候，从文本丁左边向右移动模式串P，而模式串尸与文本r在字符比较的时候是从右往左比较。BM算法在匹配的时候要同时根据坏字符跳跃表和好后缀跳跃表
14、，取两者中的最大值作为模式串的右移量。BM算法的最坏时间复杂度为D伽胛)，最好时间复杂度为D(胛川)。坏字符跳转规则定义如下，其中c为文本丁与模式P比较时出现的不匹配文本字符：fm；P卅c(1，研)，即ciz在P中未出现Bc。J】i)=脚一；=maxP刀=如，1朋一1)， (2)其他情况以文本产“acbccadbacbacc”和模式串P=“acbacc”为例，文本丁与模式串P从右往左比，当模式串P的7处字符与文本的f+处不匹配时，即Hf+刀!=PL力，则移动模式串的距离为Bcp(rp+刀)。好后缀跳跃规则定义如下：fsKP+1，珑一1】=P一s+1，G印(，)=min ，l一1一s】)&P卅尸
15、，一s】(Js) (3)fJPJ+1，m一1】=P1，一，ms】(，s)例子的匹配过程见表2所列。万方数据李莉，江育娥。林劫，等：基于KMP算法的改进算法KMPP表2 BM算法匹配过程序号 0 l 2 3 4 5 6 7 8 9 lO ll 12 13文本串 a c b c c a d b a c b a c c第一次 a c b a c c第二次 a c b a c c第三次 a c b a c c第四次 a c b a c c3 KMPP算法31 KMPP算法思路KMP算法消除了BF算法中的文本指针f回溯问题，但指针f每次只能移动一个字符，而且模式串每次的跳转量都小于当前，值，当字符不匹配
16、概率大时，值往往很小，所以KMP的整体匹配效率并不高”“。本文结合KMP算法和BM算法坏字符跳转规则的优点，提出一种改进算法KMPP，该算法可以增加指针f每次移动的距离，从而提高匹配效率u。”，与BM不同，该算法的最坏时间复杂度为D(柳+力)，理论上也优于BM算法。KMPP算法思路如下：预处理阶段得到两个数组，分别是next数组和bmBc数组。匹配阶段在遇到丁，P不匹配时进行两个部分操作。第一部分是计算模式串移动以蹦f刀后末字符在文本中的位置；第二部分是比较文本和模式串在该位置的字符是否匹配，如果两字符不匹配，则文本该位置的字符应用bmBc数组进行坏字符跳转，否则按照KMP的匹配过程继续比较。
17、算法流程如图1。图1 KMPP算法流程图32预处理阶段预处理阶段包含两部分：KMP算法预处理和BM算法坏字符规则预处理。KMP算法预处理得到的是next数组，next数组在KMP算法中是用来改变下一轮比较窗口的_，值，在KMPP算法中，它还起到确定模式串移动以“f忉后末字符在文本中的位置的作用；运用BM算法中的坏字符跳转规则得到的是bmBc数组，在KMPP算法中匹配阶段的第二部分中，如果两字符不匹配，则利用bmBc数组作文本该位置字符的坏字符跳转。由于KMP算法预处理的时间复杂度为D)，坏字符的时间复杂度为D+I鄙，I司为字符集大小，所以KMPP预处理阶段具有线性的时间复杂度D仰+I琊。KMP
18、预处理核心代码如下：while(i=O&Pi】=P【j】)i+；j+；nexti-j；elsej=next啪；坏字符预处理核心代码如下：fbr(i=0；iASIZE；i+)bmBci】=m；f-or(i=O；im一1；i+)bmBcxi】2mli；33 匹配阶段匹配函数核心代码如下：while(ilength)if(jl llT【i】=P【j】)if(匹配成功)找到一个匹配i+；j=0；else(i+；j+；else计算模式串移动next【j】后末字符在文本中的位置tLast=T【i+pLennextj一1；该位置的文本字符与末字符不匹配万方数据cD以p“据r E仃g抽已P，f帽日盯d爿印，f
19、c口ffons计算机工程与应用i“tLastf_pLast)j=0；进行坏字符跳转i=i+bmBctLast一nextD】；else按照KMP的匹配过程继续比较j=nextj】；以文本串产“acbccadbacbacc”，模式串JP=“acbacc”为例，匹配过程如表3所示；预处理后得到的两个数组值分别为：，z蹦f6】_一1，0，0，0，l，26聊曰ca=2，6朋Bcb】=1，6卅Bcc=3表3 KMPP算法匹配过程序号 O 1 2 3 4 5 6 7 8 9 10 11 12 13文本串 a c b c c a d b a c b a c c第一次 a c b a c c第二次 a c b
20、a c c第三次 a c b a c c在第一次遇到不匹配时，先计算出该位置的文本字符为儿日sf=丁p+，竹一即蹦f，】一l】=丁3+60一l】=r8=a，模式串的末字符为c，a与c不匹配，则用字符a进行坏字符匹配，第一步next数组跳的距离为一，z烈刀=3一甩眈f3_3，第二步用bmBc数组跳的距离6mBca-2，两步的跳跃距离和就是f移动的距离，即f值等于f+6肌Bc(a)一门甜札卅=5，此时，值重新赋值为0，再进行下一次窗口的匹配，如表4所示；若两字符匹配，则按照KMP的匹配过程进行比较，即，值等于订蹦f卅值，再进行下一轮的比较。表4符不匹配的情况O 1 2 3 4 5 6 7 8 9
21、10 1l 12 13a c b c c a d b a c b a c ca c b a c ca c b a c c34 KMPP算法分析KMPP算法的目的是尽量使文本中的指针i每次移动的距离达到最大。从而减少移动窗口次数，字符比较次数，从而降低运行时间。BM算法的最大移动量是朋，而KMPP算法的最大移动量可以接近2研通过大量实验证明当字符集三较大且字符(r睢口sf)出现在Pattem中的概率较低的情况下，可以显著提高KMPP算法的最大移动量。当该字符与模式串的末字符不匹配时，f移动的距离为两步的跳跃距离和，第一步移动的距离由next数组决定，第二步跳跃的长度由bmBc数组决定。在第一步的
22、移动距离接近朋且第二步跳跃的距离为m的条件下，i移动的长度将接近2埘。从以上分析可以得出KMPP算法在最好情况下的时间复杂度应该接近D(甩2埘)，是BM算法最好情况下的两倍，但是KMPP算法在搜索过程要多一步匹配工作，所以要考虑到KMPP算法的平均比较次数。假设If语句的两个分支出现的概率相同，平均出现次数为l2川，两字符的匹配部分出现在else分支中，所以它的平均出现次数为l4脚，在最好情况下KMPP算法的平均比较次数为(门2埘+行4聊)，接近BM算法的133倍。综上所述，在字符集三的大小较大的情况，KMPP算法在运行性能上高于KMP算法和BM算法。4实验结果本文针对BM算法、KMP算法、K
23、MPP算法和NKMP算法进行对比实验分析。算法是在Vc60编译器上实现，并运行在cPu为Intel230 GHz，内存为4 GB的计算机上，算法采用c+语言实现。本文实验的文本是“100M128txt”和“bibletxt”。“l 00M 1 28txt”是随机生成的1 00 MB大小的文本，字符集三大小为1 28；“bibletXt”文本来源于坎特伯雷语料(http：co叩uscanterbu吖ac-nz)，字符集三大小为63。实验随机构建长度为3、5、10、17、25、50的模式串，每组测试的次数为10次，执行上述算法程序，统计出模式串不同长度时各算法的运行时间和比较次数。从图23，表56
24、可以看出，KMPP算法在比较次数和运行时间上都明显低于KMP算法和NKMP算法，NKMP算法的运行效率高于KMP算法，但效果并不是很明显，此算法主要针对查找特殊的模式串，它的应用领域较小；KMPP算法的运行效率高于BM算法，说明在摸长度I冬I 2 四种弹法运i川州对比(“100M128”文本)二=!=三兰 iKMPINKMP3 5 lO 1 7 25 50模式长度警I 3 四种弹法运行时问对比(“Bible”文本万方数据李莉。江育娥，林劫，等：基于KMP算法的改进算法KMPP 2016，52(8) 37表5四种算法的比较次数(“100M128”文本)表6四种算法的比较次数(“Bible”文本)
25、这个区域内KMPP算法每次移动的距离高于BM算法每次移动的距离。5结语本文通过分析BM算法和KMP算法并结合两者的优点，提出一种改进算法KMPP算法，该算法与KMP相同，最坏时间复杂度为D沏+压l+行)，明显优于BM的最差时间复杂度Dm以)，并且通过实验证明在字符集较大的情况下，在窗口比较次数和运行时间上都低于KMP算法、BM算法和NKMP算法。在理论上，最好情况下KMPP算法运行效率接近BM算法的133倍。综上所述，KMPP算法提高了匹配效率，具有广阔的应用前景。参考文献：【l】Faro S，Lecroq TThe exact online string matching problem：a
26、 review of the most recent resultsJ】ACM Computing Surveys，2013【2王成，刘金刚一种改进的字符串匹配算法【J】计算机工程，200632(2)：62643】Knuth D E，Mofris J H，Pratt V RFast pattem matchingin stringJSIAM Joumal on Computing，1 977，20(6)：3233504Boyer R S，Moore J SA fast s仃ing searching algorithmJCommunications of the ACM197720(10)：7
27、627725Horspool R NPmctical fast searching in stringsJSoftwa玉e：Practice and Experjence，1980，10：5015066】Daniel M Svery fast substring search algorithmJ】Communications of the ACM，1990，33(8)：132一1427】万晓榆，杨波，攀自甫改进的sunday模式匹配算法J计算机工程，2009，35(7)：1251298】Ahmed M，Kaykobad M，Chowdhu呵R AA new stringmatching al
28、gorithmJIntemational Joumal of ComputerMathematics，2003，80(7)：825-8349】杨俊丽，吕晓燕，满晰基于改进的KMP算法的词频统计J，微计算机信息，2010，26(9)：16116210】苏德福，钟诚计算机算法设计与分析M】2版北京：清华大学出版社，2001：575911鲁宏伟，魏凯，孔华峰一种改进的KMP高效模式匹配算法J】华中科技大学学报，2006，34(10)：414312】严蔚敏，吴伟民数据结构【M】2版北京：清华大学出版社，199813】Rajesh S，Prathima S，Reddy L S SUnusual patt
29、em detec-tion in DNA database usiIlg KMP algorimm【J】IntemationalJoumal of Computer Applications，2010，l(22)：15【14赵森严，黄伟，李阳铭一种改进的KMP入侵检测的模式匹配算法J井冈山大学学报：自然科学版，2013，34(1)：555815】解晨，王瑜KMP算法研究与实现【J电脑知识与技术，20139(20)(上接32页)7】谢箭，刘国良基于神经网络的不确定性空间机器人自适应控制方法研究【J】宇航学报，2010，31(1)：123一1298】Guo Y S，Chen LAd印tive ne
30、ural network con订ol of freefloating space manipulator system in joint spaceC】ChinaControl Conference，2007：1171209张文辉，齐乃明自由漂浮空间机器人神经网络自适应补偿控制J】宇航学报，20ll，32(6)：1312131710刘福才，高娟娟不同重力环境下空间机械臂神经自适应鲁棒控制【J】宇航学报，2013，34(4)：503510【11】Dubowsky s，Papadopoulos E GThe kinematics，dynamics【12【1314】15】and control o
31、f freenying space robotic systems【J】IEEE1rans on Robotics and Automation，1993，9(5)：531543xu Y S，Kanade TSpace robotics：dynamics and con缸ol【MS1：Kluwer Academic Publishers，1 992魏承，赵阳空间机器人捕获漂浮目标的抓取控制【J航空学报，2叭O，3l(3)：632637韩力群人工神经网络理论、设计及应用M】j匕京：化学工业出版社，2007NewtOn R T，Xu YNeural network contml of a spacemanipulatorp】IEEE Comrol Systems Magazine，l 993，13(6)：1422万方数据