一種改進的字符串模式匹配算法

蔡婷++楊衛帥

摘 要：高效快速的字符串模式匹配算法有助于網絡信息處理的相關應用。文章在分析相關字符串匹配算法的基礎之上，針對模式串中字符重復次數較多匹配應用，提出了一種快速的字符串匹配改進算法。該算法利用文本串中當前失敗字符與模式串右對齊端的文本串下一個字符來啟發模式串向右移動。結合這兩個字符在模式串中匹配的情況及以這兩個字符為首末的特征字符串在模式串中的匹配情況來使計算模式串向右移動最大距離，盡可能地排除無效匹配。實驗結果表明，該算法能有效減少模式匹配中字符的比較次數，提高模式匹配效率。

關鍵詞：字符串匹配；KMP算法；BM算法；Sunday算法；移動距離

中圖分類號：TP301.6 文獻標識碼：A 文章編號：2095-1302（2017）07-00-03

0 引 言

隨著信息技術的高速發展，如何在海量數據中提取有用信息是網絡信息技術研究的熱點。字符串模式匹配主要用于文本串的處理領域，如信息檢索、拼寫檢查、數據處理、信息測試、數據壓縮、搜索引擎、網絡入侵檢測、DNA序列匹配等。如何用高效快速的字符串模式匹配算法解決網絡信息處理的相關問題已成為目前研究的重要領域之一。

字符串匹配問題的形式化定義是[1]：在有限字母表∑上的字符序列上，給定一個長度為n的文本串T[0…n-1]以及一個長度為m的模式串P[0…m-1]，m

1 相關算法介紹

1.1 KMP算法

KMP算法是經典的字符串匹配算法，主要在模式匹配過程中執行T[i]和P[j]的匹配檢查。若T[i]=P[j]，則繼續匹配T[i+1]與P[j+1]；若T[i]≠P[j]，則分成兩種情況：若j=0，模式串P向右移一位，繼續匹配T[i+1]和P[0]；若1

（1）

其中：

1.2 Horspool算法

Horspool算法是字符串匹配算法中從右向左匹配的創始者。當失配發生時，模式串P要向右移動，T串的失配字符T[i]可能是正確結果中的一個元素，也可能不是。如果不是，可將P串的首位與T串中的T[i+1]對齊，繼續進行比較；如果是，那么從P串失配位置j開始向左任意一位與P[i]相等的字符c確定的比較位置可能完全匹配，其產生的位移依次為k1，k2…，ki（k1為j-location（c））。綜合這兩種情況，選擇位移最小值k1，以保證不會錯過正確匹配的情況。

1.3 BM算法

BM（Boyer-Moore，BM）算法是基于Horspool算法的一種改進算法，其廣泛應用于實際項目中。BM算法實際包含兩個并行算法，壞字符算法和好后綴算法。匹配時，同Horspool算法；當失配時，計算P串失配字符的右邊已經匹配的字符串（稱為“好后綴”），在P串中其他位置出現的位置得到一個右移大小值（實際該值是預先計算好的），將該值與Horspool失配時P串移動大小的值進行比較，并選擇其中較大者。P串移動后，繼續進行比較。

1.4 Sunday算法

Sunday算法是一種高效算法，可以看成BM算法的簡化形式。在匹配過程中，模式串P不一定要按從左向右的順序比較或從右向左進行匹配。在失配情況下，選中T串與P串右對齊端的下一個字符T[i]，從P串末位向左尋找與該字符相等的字符P[j]，找到后，T[i]與P[j]對齊，繼續從右到左比較；若找不到，則P串左端與T[i]的下一個字符對齊，從右到左比較。

2 改進的字符串匹配算法

字符串模式匹配算法要解決的關鍵問題是在模式與文本某個位置比較失敗時，如何使模式串窗口向右移動最佳距離，盡量跳過無需比較的字符，減少匹配次數，并使產生這種距離的算法復雜度降低且易于理解。通過對現有各種字符串匹配算法的研究，我們提出一種改進算法，該算法主要針對模式串重復率較多的情況使用。當文本串T與模式串P發生匹配時，判斷模式串最右端對應文本串下一個字符Ti+m是否在模式串中，若不在，匹配規則同Sunday算法；若在，記下在模式串P0P1…Pm-1中的位置q，同時記下文本串中當前失敗的字符Ti+j在模式串P0P1…Pj-1出現的位置k，根據q、k的值以及Ti+j+1Ti+j+2…Ti+m-1與Pk+1Pk+2…Pm-1的比較情況來計算模式串向右移動的最大距離。

2.1 比較順序

與BM算法類似，在模式串的匹配過程中，字符串采用從右向左的順序依次比較。

2.2 模式串移動距離的確定

假設當前匹配的比較窗口是TiTi+1…Ti+m-1，在某次比較過程中失敗于Pj處，即后m-j個字符匹配成功：Ti+j+1Ti+j+2…Ti+m-1=Pj+1Pj+2…Pm-1，而Ti+j≠Pj，如圖1所示。