一種快速的單模式匹配算法

摘要：在對Boyer Moore(BM)算法及其改進的Tuned Boyer Moore(TunedBM)算法進行分析的基礎上，提出了一種更加快速的單模式匹配算法——NFS。該算法利用當前嘗試中匹配失敗字符的位置信息進行更大的嘗試位置移動，使算法具有更高的效率。實驗結果表明，NFS算法的性能優(yōu)于同類的其他算法，特別是在模式長度較短的情況下，優(yōu)勢更為明顯。

關鍵詞：模式匹配；BM算法；TunedBM算法；新的快速搜索算法

中圖分類號：TP301．6文獻標志碼：A

文章編號：1001－3695(2008)01－0045－02



0引言

模式匹配是計算機技術領域的一個基本問題。它在入侵檢測、數據壓縮、WWW搜索引擎以及計算機病毒特征碼匹配等系統中都有十分重要的應用價值。模式匹配就是在給定的文本串中查找模式串的出現次數。若出現次數為0，稱匹配失敗；若出現的次數大于或等于1，則稱匹配成功。

本文使用P=P[0..m-1]表示要匹配的模式串，長度為m；文本串表示為T=T[0..n 1]，長度為n；字符表以Σ表示，大小為σ。將匹配過程中P與T中長度為m的子串作一次比較稱為一次嘗試，并將當前嘗試中與模式串對齊的T的子串稱為當前窗口。

在通常應用中，BM[1]算法被看做是最有效的單模式匹配算法。它采用從右向左的比較方式，并利用當前嘗試中的已匹配信息和匹配失敗的字符，查找預處理好的好后綴跳躍表(good suffix shift table)和壞字符跳躍表(bad character shift table)，使嘗試跳躍式地進行。其最大可能跳躍距離為m。TunedBM[2]算法則是BM算法的簡化實現。由于它只使用了壞字符跳躍表，有效地減少了字符比較次數，在實際應用中效率比BM算法高，但最壞情況時的性能不如BM。本文在對這兩種算法進行簡要介紹和分析的基礎上，綜合兩者之長，提出了一種更加快速的單模式匹配算法，即NFS。該算法充分利用當前嘗試中匹配失敗字符的位置信息，以期在每一次跳躍中跳躍盡量大的距離。實驗結果表明，與其他同類算法相比，NFS算法更加有效。尤其是在模式長度較短的情況下，表現出優(yōu)越的查找性能。考慮到漢語詞的平均長度約為4 Byte，故該算法對中文信息處理中的信息檢索問題尤為適用。

1BM和TunedBM算法

1)BM算法

BM算法在當前窗口中對模式P自右向左進行掃描。當匹配失敗或完全匹配時，用兩個預先計算的偏移函數BadCha racter和GoodSuffix來確定文本指針的右移距離。該算法預處理階段的時間復雜度為O(m+σ)；匹配階段的時間復雜度為O(mn)，但當匹配一個非周期化的模式時至多需要匹配3n個文本字符，最好情況下的時間復雜度為O(n/m)。

2)TunedBM算法

考慮到字符的比較操作是模式匹配算法中最費時的部分，可以在實際比較前盡量向前移動模式。TunedBM算法只使用了BadCharacter偏移函數。在匹配階段，算法在文本串中查找P[m-1](即模式P的最后一個字符)。若不匹配則指針一直向前移動，直到找到它。在找到P[m-1]的情況下，再比較模式中的其他字符。此后無論相等與否都將使文本指針向前移動P[m-1]對應的偏移位置。預處理階段的時間復雜度為O(m+σ)。匹配階段時間復雜度最壞情況下可達到平方級，但在實際應用中效率很高。

2NFS算法

進一步提高模式匹配算法效率的主要途徑是利用當前嘗試中可以獲取的信息進一步增大跳躍距離。綜合BM和TunedBM算法的優(yōu)點，本文提出了NFS算法。它采用TunedBM的BadCharacter和BM的GoodSuffix對模式進行預處理；然后根據當前嘗試中匹配失敗字符的位置信息，決定是查找好后綴跳躍表還是壞字符跳躍表，以期獲得更大的跳躍距離。算法分為模式的預處理階段和文本的查找階段。

2．1預處理階段

預處理階段的任務是計算BadCharacter和GoodSuffix兩個偏移量函數。

1)BadCharacter函數的計算

5結束語

NFS算法綜合了BM和TunedBM算法的優(yōu)點，使每一次匹配不成功后都能跳過盡可能多的字符以進行下一輪匹配，有效地提高了匹配速度。由于查找問題的普遍性，該方法具有廣闊的應用前景。

參考文獻：

［1］BOYER R S，MOORE J S.A fast string searching algorithm[J].Commun ACM，1977，20(10):762 772.

[2]CHARRAS C，LECROR T.Exact string matching algorithms[EB/OL].(1997).http://www igm.univ mlv.fr/~lecroq/string/.

[3]COLE R.Tight bounds on the complexity of the Boyer Moore string matching algorithm[J].SIAM J Comput，1994，23(5):1075 1091.

[4]LECROQ T.Experimental results on string matching algorithms[J].Software Practice and Experience，1995，25(7):727 765.

[5]HORSPOOL R N.Practical fast searching in strings[J].Software Practice and Experience，1980，10(6):501－506.

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