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

余飛

摘要：模式匹配算法是計算機領(lǐng)域的一個重要研究方向，是防火墻系統(tǒng)、安全掃描系統(tǒng)、入侵檢測系統(tǒng)等核心技術(shù)之一。該文分析了四種經(jīng)典算法，研究了算法原理，展示了模式匹配算法發(fā)展過程，研究表明模式匹配算法具有較高的用途和實用價值。

關(guān)鍵詞：模式匹配算法；算法原理；核心技術(shù)

中圖分類號：TP311 文獻標識碼：A 文章編號：1009-3044（2018）10-0251-02

Abstract： Pattern matching algorithm is an important research field in computer field. It is one of the core technologies of firewall system， security scanning system， intrusion detection system and so on. In this paper， four classical algorithms are analyzed， the algorithm principle is studied， and the development process of pattern matching algorithm is shown. The research shows that pattern matching algorithm has high practical and practical value.

Key words： Pattern matching algorithm； algorithm principle； core technologies

模式匹配算法是網(wǎng)絡(luò)安全系統(tǒng)的核心技術(shù)之一?，F(xiàn)在比較流行的網(wǎng)絡(luò)安全系統(tǒng)包括病毒防護系統(tǒng)，防火墻系統(tǒng)，安全掃描系統(tǒng)，入侵檢測系統(tǒng)等等。在病毒防護系統(tǒng)和入侵檢測系統(tǒng)中，模式匹配算法能夠幫助篩選或識別出病毒程序和入侵操作，在防火墻系統(tǒng)和安全掃描系統(tǒng)中，模式匹配算法可以按照特征庫掃描或過濾出符合要求的數(shù)據(jù)。因此，模式匹配算法是計算機領(lǐng)域的一個重要研究方向。

1 模式匹配算法概述

模式匹配算法具有廣泛的使用價值。字符串模式匹配算法可用于對文本的查找與搜索，可用于網(wǎng)絡(luò)安全中在數(shù)據(jù)流里對特征值的有效匹配和識別，可用于在生物科學中匹配DNA序列；圖像模式匹配算法可用于軍事上導航精確打擊武器的圖像匹配系統(tǒng)；點模式匹配算法可用于無人駕駛的物體識別系統(tǒng)以及安防人臉識別系統(tǒng)等等。這一切都是以經(jīng)典的模式匹配算法為基礎(chǔ)的。

以用途最廣的字符串單模式匹配算法為例，模式匹配算法就是指以匹配模式串P[0，1，2，…，m-1]為查找內(nèi)容，在文本串T[0，1，2，…，n-1]中進行查找的方法。最簡單的方法是按順序?qū)⒛Ｊ酱淖址鹨慌c文本串字符進行比較，直到在文本串中找到與模式串一模一樣的字符串，則匹配成功；如果找不到則匹配失敗。為了增加匹配的效率，縮短匹配的時間，大多數(shù)算法將模式串與文本串的比較次數(shù)減少，比較頻率降低。

2 字符串模式匹配算法

字符串模式匹配是指對于給定的字符集，判斷一個模式串是否在給定的文本串中出現(xiàn)。如果出現(xiàn)次數(shù)為0，則稱匹配失??；如果出現(xiàn)的次數(shù)大于0，則稱匹配成功。

設(shè) 文本串為T[0，1，2…n-1]，長度為n。

模式串P[0，1，2…m-1]，長度為m。

字符串單模式匹配算法以T[j]與P[0]為比較起始位，按字符順序?qū)⒛Ｊ酱甈逐一與文本串T進行比較。若比較到T[j+m-1]與P[m-1]處所有字符均相同，則匹配成功一次；若比較到T[i+j]與P[i]處字符不相同，則匹配失敗。比較結(jié)束后，模式串P按順序偏移一位，繼續(xù)下一輪的比較。

2.1 BF（Brute Force）算法

BF（Brute Force）算法將P[0]與T[0]，P[1]與T[1]，P[2]與T[2]，…，P[m-1]與T[m-1]逐一進行比較。如果全部相同，則匹配成功；如果有一個不相同，匹配模式串P[0，1，2，…，m-1]向右移一位繼續(xù)比較，即P[0]與T[1]，P[1]與T[2]，P[2]與T[3]，…，P[m-1]與T[m]逐一進行比較。若再不成功，繼續(xù)右移一位，直到匹配成功或?qū)⑽谋敬勘容^完為止。

2.2 KMP（Knuth-Morris-Pratt）算法

BF算法結(jié)構(gòu)簡單，容易理解和實現(xiàn)，但模式串要與文本串中的每一個字符反復比較，效率低下[2]。KMP算法對BF算法進行了改進。改進的措施是，當模式串與文本串從左向右按順序進行匹配，P[j]與T[i]不相同時，則文本串T保持不動，模式串P根據(jù)預先定義好的next數(shù)組中的next[j]的值，向右滑動一段距離繼續(xù)比較。

例如，next[j]等于2的話，模式串P向右滑動，使得T[i]與P[2]進行比較。若相等，繼續(xù)比較T[i+1]與P[3]，直至比較結(jié)束全部相同，則找到一個匹配；若不相等，模式串P繼續(xù)根據(jù)next[2]的值向右滑動。如圖1所示。

在KMP算法中，next數(shù)組的值起到了非常重要的作用，直接影響到了算法的質(zhì)量。next數(shù)組值有三種類型：

（1）next[j]值為-1

當模式串P與文本串T在P[j]和T[i]處失配，next[j]的值為-1，表明模式串P向右滑動，使得P[0]與T[i+1]對齊。

（2）next[j]值為k（1≤k

當模式串P與文本串T在P[j]和T[i]處失配，next[j]的值為k，表明模式串P向右滑動，使得P[k]與T[i]對齊。

（3）next[j]值為0

當模式串P與文本串T在P[j]和T[i]處失配，next[j]的值為k，表明模式串P向右滑動，使得P[0]與T[i]對齊。

2.3 BM（Boyer-Moore）算法

BM算法是由R.S.Boyer，J.S.Moore共同提出的。不同于BF和KMP算法，BM算法是一種全新的算法。近些年產(chǎn)生的模式匹配新算法都是在BM算法的基礎(chǔ)上進行的改良，因此BM算法是模式匹配算法中一個非常重要的經(jīng)典算法。

BM算法的第一個特別之處就在于，在匹配過程中，文本串T不動，模式串P從左向右移動，但是在字符比較的時候，卻是自右向左進行的。即先匹配T[j+m-1]和P[m-1]，再比較T[j+m-2]與P[m-2]是否相等……直到比較至T[j]和P[0]處。如果全部相等，則匹配成功。大多數(shù)的時候，都會在中間處發(fā)現(xiàn)不相等的字符，該處的位置可以認為是T[i+j]，P[i]。這個時候需要調(diào)用偏移函數(shù)Goodsuffix（好后綴函數(shù)）與Badchar（壞字符函數(shù)）[3]，若函數(shù)Goodsuffix得出偏移的位數(shù)大于Badchar，則使用Goodsuffix得出偏移的位數(shù)；反之，使用Badchar得出的位數(shù)[4]。

Badchar函數(shù)：

在T[i+j]與P[i]處失配，則在模式串中尋找與T[i+j]相等的字符P[k]。找到，T[i+j]與模式串中P[k]處對齊；找不到，則T[i+j+1]與P[0]對齊。

Goodsuffix函數(shù)：

在P[i]與T[j+i]處失配，但T[j+i]…T[j+m-1]與P[i]…P[m-1]都是匹配的，這些相同的字符串，標記為u。如果u再次出現(xiàn)在模式串P中，并且后綴u的前一個字符不是a，則將模式串P中u前的一個字符與文本串中u前的一個字符對齊。如果文本串T有一個后綴v，與模式串的一個前綴相同，并且是能夠匹配的最長的后綴與前綴，則將它們相同的部分對齊。

2.4 BMH（Boyer-Moore-Horspool）算法

BM算法的Badchar函數(shù)的應用次數(shù)遠遠大于Goodsuffix函數(shù)。因為在模式串P中能找到后綴u的次數(shù)非常少，大部分的偏移都在Badchar函數(shù)處執(zhí)行。BMH算法直接刪掉了Goodsuffix函數(shù)，并對Badchar函數(shù)進行了改進[5]。其改進思想是：模式串P與文本串T進行匹配，從右向左比較P[m-1]和T[j+m-1]，若相同則繼續(xù)比較P[m-2]和T[j+m-2]，…，一直比較至P[0]與T[j]為止。如果都相同，則匹配成功；如果中間發(fā)現(xiàn)P[i]與T[j+i]不相等，則分為如下情況：

如果在P[i]與T[j+i]處失配，但T[j+i]…T[j+m-1]與P[i]…P[m-1]都是匹配的，這些相同的字符串，標記為u。在u中，最后一個字符T[j+m-1]，標記為d。如果在模式串P中，除P[m-1]外，還能找到P[k]處值為d。則模式串P向右滑動，讓T[j+m-1]與P[k]對齊，并從模式串末端開始，從右向左繼續(xù)比較[6]。如果除P[m-1]外，在模式串P中，d沒有找到。則從模式串末端開始，模式串繼續(xù)向右滑動m位，從右向左開始新的一輪比較。如圖2所示。

3 小結(jié)

本文探討了四種經(jīng)典的模式匹配算法及其原理和實現(xiàn)過程，包括BF，KMP，BM，BMH算法。早期的BF和KMP算法雖然匹配結(jié)果精確，但效率低下。BM算法的出現(xiàn)改變了這種狀況，是模式匹配算法發(fā)展的里程碑。BMH算法是BM算法的改進算法，進一步提高了匹配效率。

參考文獻：

[1] 潘超，楊良懷，龔衛(wèi)華，古輝，等.模式匹配研究進展[J].計算機系統(tǒng)應用，2010（19）：265-277.

[2] 徐周波，張永超，古天龍，寧黎華.面向入侵檢測系統(tǒng)的模式匹配算法研究[J].計算機科學，2017（9）：125-130.

[3] 尹志喜，甄國涌.基于模式匹配的大規(guī)模數(shù)據(jù)分析軟件設(shè)計與實現(xiàn)[J].計算機系統(tǒng)應用，2010，19（2）：185-188.

[4] 夏念，嵩天.短規(guī)則有效的快速多模式匹配算法[J].計算機工程與應用，2017（7）：1-8.

[5] 劉順江，劉國華，李潁.基于數(shù)據(jù)源信息語境的復雜模式匹配方法[J].計算機工程與應用，2010，46（9）：120-122.

[6] 單懿慧，蔣玉明，田詩源.面向入侵檢測的改進BMHS模式匹配算法[J].計算機工程，2009，35（24）：170-173.