一種新的字符串單模式匹配算法

摘要：在分析了BM模式匹配算法的基礎上，提出了一種新的字符串單模式匹配算法，該算法通過對模式中的字符進行等級劃分，設置模式中各個字符的優先級，改進模式串的移動方式，減少了模式匹配的次數和字符比較的次數，有效的提高了模式匹配的效率。實驗顯示，該算法有效的提高了模式匹配的效率。

關鍵詞：模式匹配；字符串；文本

中圖分類號：TP309文獻標識碼：A文章編號：1009-3044(2008)15-21070-02

A New Algorithm for String Single Pattern Matching

ZHANG Yong-ping，XU Dong-yang

(Computer Science and Technology Department，China University of Mining and Technology，Xuzhou 221008，China)

Abstract:This paper analyzed BM pattern matching algorithms firstly.On the basis of this，a new string single pattern matching algorithm was proposed，which Delaminated the pattern string，set priority of the characters of pattern string，improved the shift way of the pattern string.The algorithm can reduce the times of pattern matching and character comparing，it improves the efficiency of pattern matching effectively.By the experiments，the algorithm can improve the efficiency of pattern matching effectively.

Key words:Pattern matching;Character string;Text

1 引言

字符串的模式匹配問題的形式化定義是：在字符集∑上，給定一個長度為N的文本字符串T[1…N]，以及一個長度為M的模式字符串P[1…M]。如果對于1≤s≤N，存在T[s+1…s+M]，則模式P在文本T的位置s處出現，即模式與文本匹配。字符串的模式匹配問題就是要尋找P在T中是否出現，以及出現的位置。在字符串匹配的算法中，最著名的是BM算法。本文在對BM匹配算法分析的基礎上，提出一種改進的字符串匹配算法。

2 BM算法

首先，作如下假設：

字符集：X={x|x在正文中出現}；正文T：T[1…N]，長度為 N；模式P：P[1…M]，長度為 M；N≥M。

1977 年，Boyer 和 Moore 提出了一個全新的模式匹配算法——BM 算法。此算法在匹配過程中，模式P從左向右移動，但字符比較按照 P[M]、P[M-1]、…、P[1]的次序從右向左進行。該算法的一個最主要的特點是：在匹配過程中，可以跳過很多無用的字符。通過這種跳躍式的匹配，獲得了極高的匹配效率。BM算法的關鍵是根據給定的模式P，定義一個從字母到正整數的映射函數dist1: x→{1，2， …，m}，這里x∈∑ (∑是字符集)，函數dist1也稱為滑動距離函數，它給出了正文中可能出現的任意字符x在模式串P中的位置，dist1函數的具體定義如下：

BM算法思想是：假如在執行正文中自位置i起“返前”的一段與模式匹配（自右向左）檢查中，一旦發現不匹配（無論在哪個位置），立即執行由P[M]與T[i+d(T[i])]起始的自右向左的匹配檢查。

例如：文本T為“foucchsixvchhnseerch”，模式P為“seerch”，按照BM算法，字符集X和dist1函數值如表1所示，具體的匹配過程如表2所示（粗體字符為匹配失敗的字符；括號中顯示的數字為當前匹配時，字符比較的次數）。

注釋：第一次匹配，i=4，dist1[c]=1，P向右滑1個字符。第二次匹配，i=7，dist1[s]=5，P向右滑5個字符。第三次匹配，i=10，dist1[v]=6，P向右滑6個字符。第四次匹配，i=18，dist1[r]=2，P向右滑2個字符。第五次匹配成功。

3 一種新的字符串單模式匹配算法

通過上面算法特點的分析，我們可以看出影響字符串模式匹配效率和速度的關鍵因素是：模式P和文本T在某個位置匹配失敗時，如何使模式向右移動的幅度最大，即盡可能多的跳過不需要比較的文本字符，從而減少匹配的次數和匹配過程中字符比較的次數。

基于上面的因素，提出了一種改進的字符串匹配算法，該算法簡單實用，易于理解。算法的基本規則如下：

3.1 比較順序

與BM算法相同，進行模式匹配時，模式串P沿著文本T從左到右移動，字符的比較按照從右至左的順序進行。

3.2 算法的初始化

在開始之前，作如下假設：

字符集：X={x|x在正文中出現}；正文串 T：T[1…N]，長度為 N；模式串 P：P[1…M]，長度為 M；N≥M。

首先定義一個函數S來確定正文T中出現的字符x在模式P中是否存在。定義如下：

我們對模式P中的字符按等級進行優先級別的分類，分類方法如下：

(1)將模式的末尾字符P[M]作為最優先的等級獨立出來進行處理。

(2)將模式中子串P[1…M-1]中的字符以字符重復出現的次數為標準進行分類，出現一次的所有字符列為第一級，把出現兩次的所有字符列為第二級，依此類推，直至將所有的字符分配完畢。

(3)字符比較的優先級別按照重復次數的多少，從小到大排列，重復次數越少的優先級越高。同一級別的字符，按照模式P中從左至右出現的順序排列。

對模式P中字符進行優先級分類的同時，將各字符在模式P中對應的位置記錄下來，位置按字符在P中從左至右出現的順序進行記錄，這里定義一個三維數組lev[L][F][G](L記錄級別，F記錄字符，G記錄字符在P中的位置)；位置的記錄，便于字符的迅速定位。

此外，我們采用BM算法中的dist1函數。

3.3 算法中模式P移動方式

我們假設：文本串T中和模式串P最后一個字符對應的位置為end。

本算法移動距離的計算，利用了文本串T中的字符T[end+1]，還有dist1函數和S函數。具體步驟如下：

(1)首先比較T[end]和P[M]，如果字符匹配，執行2）；如果字符不匹配，執行3）；

(2)按照字符的優先級別，利用記錄的字符位置，在P中定位字符，并與T中對應位置的字符進行比較，直至匹配失敗，記錄下T中失敗字符對應的位置i。然后，判斷S(end+1)，如果S(end+1)＝0（即T中該字符不在P中），模式P向右移動（M+1）個字符（即移動到T[end+2]），進入下一輪匹配；如果S(end+1)=1（即T中該字符在P中），模式串P向右移動max(dist1[T[i]]， dist1[T[end+1]])個字符。

(3)如果T[end]不在P中，模式P向右移動（M）個字符（即跳過T[end]）；如果T[end]在P中，判斷S(end+1)，若S(end+1)＝0，模式P向右移動（M+1）個字符，若S(end+1)=1，模式P向右移動max(dist1[T[end]]， dist1[T[end+1]])個字符。

3.4 實例說明

例如，同樣的文本T:“foucchsixvchhnseerch”，模式P:“seerch”，字符集X和dist1函數值如表1所示，P中字符的優先級別為：最高級：h；第一級：s， r， c；第二級：e。用改進算法進行匹配的過程如表3所示（括號中顯示的數字為當前匹配時，字符比較的次數）。

改進算法的匹配過程如下：

第一次匹配：T[h]=P[h]，依據步驟2，比較第一層字符，T[f]≠P[s]，判斷S(T[s])，S(T[s])=1，(dist1[T[f]]=6)>(dist1[T[s]]=5)，所以模式串P向右移動6個字符，第一次匹配結束。

第二次匹配：T[h]=P[h]，依據步驟2，比較第一層字符，T[s]=P[s]，繼續比較，T[v]≠P[r]，判斷T[h]，S(T[h])=1，(dist1[T[v]]=6)=(dist1[T[h]]=6)，所有模式串P移動6個字符，第二次匹配結束。

第三次匹配：T[r]≠P[h]，依據步驟3，T[r]∈P，判斷S(T[c])， S(T[c])=1，(dist1[T[r]]=2)>(dist1[T[c]]=1)，所以模式串P向右移動2個字符，第三次匹配結束。

第四次匹配：匹配成功。

在BM算法中，同樣的文本串T和模式串P，一共需要5次匹配，14次字符比較。而使用改進的算法時，只需要4次匹配，12次字符比較。

可以看出，改進算法可以加快字符串模式匹配的速度，提高了字符串模式匹配的效率。

4 實驗結果

本文共測試兩種模式匹配算法，分別是：BM算法、改進算法。文本串T由英文組成，測試結果如表4所示。

通過上面的測試，可以看出本文提出的改進算法有效地減少了模式串匹配地次數，提過了模式匹配的速度。

5 結束語

我們在實際應用中，應用改進算法，在多數字符串比較的情況下，能夠提高字符串模式匹配的速度，減少匹配次數和字符比較的次數，有效的提高了字符串模式匹配的效率，因此具有較大的實用價值。本文作者創新點：在分析BM模式匹配算法的基礎上，利用對模式串P分層，設置模式串P中各個字符的優先級和改進模式移動方式，提出了一種改進的字符串模式匹配算法。實驗表明，算法能夠減少模式匹配的次數和字符比較的次數，提高了模式匹配的速度，具有較好的性能。

參考文獻：

[1]Berry T，Pavindran S.A fast string matching algorithm and experim ental results [C].Prague，Czech Republic:Proceedings of the Prague Stringology Club Workshop，1999:16-28.

[2]Charras C.Exact String Matching Algorithms[Z].http://www-igm.univmlv.fr/-lecroq/string/.[3]HORSPOOL RN.Practical fast searching in strings[J].Software Practice and Experience，1980，10(6):501-506.[4]巫喜紅，凌捷.單模式匹配算法研究[J].微計算機信息，2006，8-3:202-204.

收稿日期：2008-02-25

作者簡介：張永平（1958-），男（漢族），遼寧丹東人，中國礦業大學計算機科學與技術學院，副教授，碩士生導師，研究方向：計算機網絡與信息安全，密碼學；徐冬陽（1983-），男（漢族），江蘇南通人，中國礦業大學計算機科學與技術學院碩士研究生，研究方向：計算機網絡與信息安全。

注：“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。”