有關(guān)KMP模式匹配算法的探索

摘 要：通過(guò)改進(jìn)的KMP算法對(duì)字符串模式匹配算法與傳統(tǒng)的KMP算法進(jìn)行研究，在改進(jìn)之后，平均比較次數(shù)下降明顯，能夠快速提高字符串模式匹配的工作效率，在應(yīng)用方面更加節(jié)約成本，提高效益。

關(guān)鍵詞：KMP；改進(jìn)；模式匹配算法；字符；分析；算法

中圖分類號(hào)：TP309

隨著計(jì)算機(jī)技術(shù)的不斷發(fā)展，需要處理的數(shù)據(jù)內(nèi)容不斷呈現(xiàn)出大量化的特點(diǎn)。近年來(lái)，在計(jì)算機(jī)研究領(lǐng)域內(nèi)模式匹配問(wèn)題受到了極大的關(guān)注。在串處理系統(tǒng)中，子串在主串中的定位操作是一種重要的過(guò)程中，稱之為串的模式匹配。隨著計(jì)算機(jī)網(wǎng)絡(luò)搜索引擎技術(shù)的發(fā)展、病毒技術(shù)的進(jìn)步以及數(shù)據(jù)壓縮方面的不斷發(fā)展，模式匹配算法在計(jì)算機(jī)應(yīng)用系統(tǒng)中得到了廣泛的應(yīng)用。目前主要的匹配算法有BF算法、KMP算法與一些改進(jìn)的算法，從方式上，可以分為精確匹配、模糊匹配、并行匹配等。本文重點(diǎn)對(duì)KMP算法進(jìn)行分析，另外對(duì)于改進(jìn)的KMP算法進(jìn)行研究與展望。

1 簡(jiǎn)單的模式匹配算法

現(xiàn)代計(jì)算機(jī)技術(shù)不斷發(fā)展，人們的工作、生活與互聯(lián)網(wǎng)有著密切的聯(lián)系，同時(shí)網(wǎng)絡(luò)內(nèi)容也不斷豐富，每一個(gè)終端幾乎都有可能會(huì)上傳與下載數(shù)據(jù)，造成網(wǎng)絡(luò)上的類似相信也非常多，如何能夠從大量的信息中進(jìn)行查找同樣的信息，則需要經(jīng)過(guò)一定的算法。[1]這種典型的應(yīng)用系統(tǒng)將會(huì)使用到匹配算法。簡(jiǎn)單的模式匹配算法主要是一種查找過(guò)程，給出一個(gè)特定的字符串P，在一大型的文本中進(jìn)行查找，從而確定出P是否在大型文本中出現(xiàn)過(guò)，如果存在，同時(shí)給出相應(yīng)的出現(xiàn)位置。在以上的算法定義中，為了對(duì)數(shù)學(xué)模式進(jìn)行簡(jiǎn)單描述，進(jìn)行以下符號(hào)定義。模式串為P，需要匹配的大型文本主串為T，模式串的長(zhǎng)度為m，需要匹配的大型文本主串長(zhǎng)度為n，在模式串中首字符與末字符分別為P1與Pm，而需要匹配的主串文本首字符與末字符分別為T1與Tn。文本字符串T與模式字符串P分別是由字符組成的一種集合，強(qiáng)行搜索模式實(shí)質(zhì)上就是把模式P與文本T進(jìn)行自左向右的挨個(gè)搜索，如果模式字符串P在某一點(diǎn)的匹配失敗，則立即將T向右移動(dòng)一個(gè)字符的位置，繼續(xù)從模式字符串P的第一位向右來(lái)搜索。[2]這種算法基本上是最符合原理的，但同時(shí)它的工作量十分巨大，體現(xiàn)出的效率并不高，需要進(jìn)行m（n-m+1）次的字母匹配運(yùn)算，往往給過(guò)程浪費(fèi)大量的時(shí)間?，F(xiàn)代社會(huì)是高效社會(huì)，一旦在網(wǎng)絡(luò)搜索中速度過(guò)慢，用戶將會(huì)失去耐心。目前更多的手持設(shè)備在應(yīng)用搜索時(shí)一般是即時(shí)搜索，對(duì)時(shí)間的要求較高，運(yùn)算量太大的低效搜索模式已經(jīng)不再滿足現(xiàn)代需求。每個(gè)網(wǎng)站的用戶數(shù)量都在不斷增大，形成的用戶名與密碼都需要進(jìn)行數(shù)據(jù)儲(chǔ)存，利用模式匹配法可以對(duì)賬戶與密碼進(jìn)行匹配，從而判斷是否可以登入，否則就進(jìn)行拒絕，有效提高時(shí)間，保護(hù)網(wǎng)站利用與用戶隱私。這是模式算法的典型應(yīng)用，隨著算法的不斷進(jìn)步，將會(huì)在多個(gè)網(wǎng)絡(luò)領(lǐng)域內(nèi)得以廣泛應(yīng)用。[3]

2 KMP算法

KMP算法目前已經(jīng)經(jīng)過(guò)了多年的發(fā)展，最早是由克努特、莫里斯與普照拉特同時(shí)發(fā)現(xiàn)，是一種改進(jìn)的字符串匹配算法，在這種算法中，對(duì)主串指針回溯進(jìn)行了消除，利用已經(jīng)得到的部分匹配結(jié)果把模式串右行一段較遠(yuǎn)的距離，再次進(jìn)行比較與匹配，從而使算法的效率得到大幅地提升。這主要是因?yàn)樵谇捌诘钠ヅ溥^(guò)程經(jīng)驗(yàn)總結(jié)中，一旦某字符不符合模式串的匹配要求，在附近的一段文本中也將不會(huì)出現(xiàn)匹配的對(duì)象。[4]

KMP的算法思想是當(dāng)Ti與Pj匹配完成時(shí)，主串的指針i與模式的串指針j將會(huì)分別加1，不斷向后面進(jìn)行再次匹配，如果Ti與Pj匹配不成功時(shí)，主串的指針i保持不動(dòng)，模式的串指針j將不會(huì)回到第一個(gè)位置，而是回到一個(gè)合適的位置，一旦j回到了第一個(gè)位置，將有可能會(huì)對(duì)需要匹配的文本字符進(jìn)行錯(cuò)過(guò)。主串的指針i保持不動(dòng)時(shí)，算法的關(guān)鍵就在于模式的串指針j指回到了哪一個(gè)位置。模式的串指針j不可右移太大的距離，避免錯(cuò)過(guò)有效匹配，同時(shí)也要右移盡可能地大，以提高匹配效率。在某次字符匹配時(shí)，一旦不匹配，模式的前j-1個(gè)字符能夠匹配，則在下一次匹配時(shí)，可以把模式串向右移動(dòng)j-s-1個(gè)字符位置，從而使P1與Tj-s對(duì)齊，需要從P3+1開(kāi)始進(jìn)行匹配情況檢查。為了避免遺漏問(wèn)題，在以上的首字串必須是最長(zhǎng)的，自匹配的部分字串是唯一的，與模式自身結(jié)構(gòu)有關(guān)。當(dāng)模式的第j個(gè)字條與主串里的該字符進(jìn)行比較位置時(shí)，它的值主要是取決于模式本身，與主串無(wú)關(guān)。這時(shí)關(guān)鍵是要選擇模式的適當(dāng)位置。

3 改進(jìn)的KMP算法

模式匹配的KMP算法有效地避免了BM算法中頻繁回溯的問(wèn)題，極大地提高了模式匹配的效率，但這種算法并不是最優(yōu)秀的。經(jīng)過(guò)長(zhǎng)時(shí)間的探索與分析，KMP算法中的掃描部分仍然可以進(jìn)一步改進(jìn)。[5]

在改進(jìn)的KMP算法中，當(dāng)某一次匹配失敗時(shí)，i指針不需要進(jìn)行回溯，而是使用已經(jīng)匹配到的結(jié)果，查看是否對(duì)i的調(diào)整進(jìn)行必要性評(píng)估，之后再?zèng)Q定與向右滑動(dòng)的位置模式進(jìn)行比較。主串指針i的有效變化可以有效提高匹配的效率。在進(jìn)行第一次匹配結(jié)束時(shí)，j=6處，無(wú)法進(jìn)行匹配時(shí)，i指針將會(huì)定為6，j指針為6，當(dāng)模式串向右移動(dòng)三個(gè)位置時(shí)，開(kāi)始進(jìn)行第二次的匹配，i的指針為9，而j的指針值為3，也就是說(shuō)從主串的第九位開(kāi)始進(jìn)行比較，i值的不斷增加也就加快了模式匹配的進(jìn)度，提高了工作效率。

4 利用改進(jìn)算法進(jìn)行多次模式匹配

與單模式匹配算法相比，多模式匹配算法的優(yōu)勢(shì)在于一趟遍歷可以對(duì)多個(gè)模式進(jìn)行匹配，從而大大提高了匹配效率。對(duì)于單模式匹配算法，如果要匹配多個(gè)模式，那么有幾個(gè)模式就需要幾趟遍歷。當(dāng)然多模式匹配算法也適用于單模式的情況。在入侵檢測(cè)系統(tǒng)中，一條入侵特征可能匹配或部分匹配很多條規(guī)則，如果采用單模式匹配，在匹配每條規(guī)則時(shí)都需要重新運(yùn)行匹配算法，效率很低。然而，日益增多的網(wǎng)絡(luò)攻擊使得入侵檢測(cè)的規(guī)則數(shù)目仍在不斷增長(zhǎng)。

在實(shí)際的應(yīng)用中，模式串與主串一般需要多次的匹配，才能找到主串中是否有多次存在相同的子串，如在數(shù)據(jù)庫(kù)中進(jìn)行查找。[6]通過(guò)多次模式的匹配可以實(shí)現(xiàn)多個(gè)子串在文本中的位置，同時(shí)可以進(jìn)行標(biāo)記，有利于現(xiàn)代計(jì)算機(jī)龐大數(shù)據(jù)量的數(shù)理與分析。我國(guó)人口眾多，網(wǎng)民數(shù)量龐大，姓名與用戶名很可能會(huì)出現(xiàn)重復(fù)的情況，所以需要提前在數(shù)據(jù)庫(kù)中進(jìn)行查找，以確定是否可用，另外對(duì)匹配但其他特性不符的對(duì)象進(jìn)行排除。

5 結(jié)束語(yǔ)

隨著現(xiàn)代計(jì)算機(jī)技術(shù)的不斷發(fā)展，越來(lái)越多的新技術(shù)得以應(yīng)用與改進(jìn)。網(wǎng)絡(luò)安全發(fā)展形勢(shì)也要求提高網(wǎng)絡(luò)入侵檢測(cè)系統(tǒng)的性能。模式匹配的效率問(wèn)題引起了足夠的重視。通過(guò)對(duì)傳統(tǒng)的KMP模式匹配算法與其發(fā)展?fàn)顩r進(jìn)行分析，明確未來(lái)發(fā)展思路，為其實(shí)踐應(yīng)用奠定理論基礎(chǔ)。

參考文獻(xiàn)：

[1]李桂玲.一種改進(jìn)的KMP模式匹配算法[J].吉林工程技術(shù)師范學(xué)院學(xué)報(bào)，2009（10）：75-77.

[2]楊戰(zhàn)海.KMP模式匹配算法的研究分析[J].計(jì)算機(jī)與數(shù)字工程，2010（05）：38-41.

[3]陳冬文，張帆，王斌，周啟海.模式匹配算法——KMP算法的改進(jìn)[A].2008中國(guó)信息技術(shù)與應(yīng)用學(xué)術(shù)論壇論文集（一）[C].成都：西南財(cái)經(jīng)大學(xué)信息技術(shù)應(yīng)用研究所，2008.

[4]明廷堂.BF與KMP模式匹配算法的實(shí)現(xiàn)與應(yīng)用[J].電腦編程技巧與維護(hù)，2013（23）：24-28+34.

[5]范洪博.快速精確字符串匹配算法研究[D].哈爾濱：哈爾濱工程大學(xué)，2011.

[6]趙森嚴(yán)，黃偉，李陽(yáng)銘.一種改進(jìn)的KMP入侵檢測(cè)的模式匹配算法[J].井岡山大學(xué)學(xué)報(bào)（自然科學(xué)版），2013（01）：55-57.

作者簡(jiǎn)介：張燕飛（1992-），男，江蘇泰興人，本科，計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)；李亞瓊（1992-），女，貴州凱里人，本科，計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)。

作者單位：河南大學(xué)國(guó)際教育學(xué)院，河南開(kāi)封 475001