字符串匹配算法探討

母 澤 平

(重慶電子工程職業(yè)學院 軟件學院 重慶401331)

字符串匹配是模式匹配中最簡單的一個問題，但在文本處理領域中字符匹配是一個非常重要的主題。它可用于數據處理、數據壓縮、文本編輯、信息檢索等多種應用中，大多數操作系統(tǒng)中軟件實現(xiàn)的字符匹配算法是基本組件之一。字符串匹配技術通常也和其他字符問題有一定關聯(lián)。在實際應用中字符串匹配技術不僅適用于計算機科學，在語義學、分子生物學等領域也具有相當重要的應用，在以模式匹配為特征的網絡安全應用中也發(fā)揮了舉足輕重的作用。

1 字符串匹配算法研究現(xiàn)狀

字符串匹配分為精確字符串匹配與非精確字符串匹配，是計算機科學的重要組成部分，隱含眾多信息科學理論、算法思想以及算法技巧，其應用滲透了信息技術的各個領域。隨著網絡信息大眾化的快速發(fā)展，用戶對信息檢索提出了更高要求，功能上要求提高查全率、查準率以及精確定位，操作上要求簡單、靈活、快捷。作為信息檢索的基礎，字符串匹配越來越重要，成為信息檢索的瓶頸技術，直接影響到信息檢索的檢索方式、檢索功能、檢索效果、用戶界面等。非精確字符串匹配方法主要包括容錯糾錯匹配 、最大匹配 、相似匹配 等。非精確字符串匹配允許出現(xiàn)有限的錯誤，通過相似度或距離等方式進行約束，返回匹配結果以及匹配位置。

從上個世紀六十年代開始，非精確字符串匹配一直采用基于錯誤因素進行匹配的研究思路。錯誤因素主要包括插入錯誤(Insertion) 、刪除錯誤(Deletion)、交換錯誤(Swap)、替換錯誤(Substitution)等[1]。由于錯誤因素種類較多，非精確字符串匹配通常綜合處理部分錯誤因素，采用距離計算模型，從不同應用角度、各種技術，形成了線性時間復雜性到NPC(Non deterministic polynomial complete)復雜性的各種解決方案 ，用于解決允許有限錯誤的字符串匹配問題[2]。 為便于問題的討論，本文聚焦于單模式字符串匹配。在分析BM和KMP算法特點的基礎上，對這些算法進行了深入探討和剖析。

2 字符串匹配技術常用算法分析

(1) BF算法。BF(Brute Force)算法是效率最低的算法。其核心思想是：T是文本串，P是模式串。首先S[1]和P[1]比較，若相等，則再比較S[2]和P[2]，一直到P[M]為止；若S[1]和P[1]不等，則P向右移動一個字符的位置，再依次進行比較。如果存在t，1≤t≤N，且S[t+1，t+2，…，t+M]=P[1，2，…，M],則匹配成功；否則失敗。該算法最壞情況下要進行M*(N-M+1)次比較，時間復雜度為O(M*N)。

(2) KMP算法：KMP(Knuth-Morris-Pratt)算法是D.E.Knuth、J.H.Morris和V.R.Pratt 3 人于1977年提出來的。其核心思想是：在匹配失敗時，正文不需要回溯，而是利用已經得到的“部分匹配”結果將模式串右移盡可能遠的距離，繼續(xù)進行比較[3]。在此要強調的是，模式串不一定向右移動一個字符的位置，右移也不一定必須從模式串起點處重新試匹配，即模式串一次可以右移多個字符的位置，右移后可以從模式串起點后的某處開始試匹配。KMP算法的時間復雜度是O(m+n)，最壞情況下時間復雜度為O(m*n)?？臻g復雜度是O(m)，對BF算法進行了很大的改進。雖然，KMP算法有著它自身的局限性，但是，在現(xiàn)代科學的眾多領域中的應用仍然普遍。

(3) BM算法。1977 年，Boyer 和Moore 提出了一個全新的模式匹配算法——BM 算法。該算法在匹配過程中，模式串從左向右移動，但字符比較按照P[M]、P[M-1]、…、P[1]的次序從右向左進行[4]。BM 算法的一個最主要的特點是：在匹配過程中，可以跳過很多無用的字符。通過這種跳躍式的匹配，獲得了極高的匹配效率。該算法的核心思想是：對于模式串P，定義一個函數d：Σ→{1, 2,…,M} ，函數d給出了正文中可能出現(xiàn)的字符在模式中的位置。該算法最壞情況下的時間復雜度為O(N*M)。但由于在實際應用中這種情況極少出現(xiàn)，因此BM算法仍得到廣泛的應用。

(4) BMH算法。1980 年, Horspool 提出了對BM 算法的一種改進算法——BMH算法。首先比較文本指針所指字符和模式的最后一個字符,如相等再比較其余m-1個字符。無論文本中哪個字符造成了匹配失敗,都將由文本中和模式最后一個位置對應的字符來啟發(fā)模式向右的滑動。即文本自位置I起與模式的從右至左的匹配檢查中, 一旦發(fā)現(xiàn)不匹配,就將I重新賦值為End+d[T[End]]。(End是一個中間變量,記錄了文本中每次從右至左匹配的起始位置)。

(5) RK算法：RK算法是Turing獎獲得者R.M.Karp和M.O.Rabin在1981年提出來的，該算法采用了與KMP算法和BM算法完全不同的方法。該算法利用Hash方法和素數理論，首先定義一個Hash函數，然后將模式串P和文本串T中長度為m的子串利用Hash函數轉換成數值。顯然只需比較那些與模式串具有相同Hash函數值的子串，從而提高了效率。當然因為Hash沖突的存在，還要進一步進行字符串比較，但只要選擇適當的素數Hash沖突的概率就會很小。RK算法的時間復雜度是O(n+m)。

3 相關算法性能測試和結果分析

對上述的字符串模式匹配算法從時間方面進行測試 ,從而分析各算法的效率。實驗中分別從4個方面對各算法進行了測試 ,分別是模式串在正文串中的匹配不成功、模式串在主串中的頭部匹配成功、模式串在主串中的中部匹配成功、模式串在主串中的尾部匹配成功。在這四個方面中采用相同長度的文本串 ,分別為 50,100,150,200,但文本串的內容不一樣；模式串的長度均為 5,內容也不一樣。在這些用例的基礎上對 KMP、BM、RK算法進行測試 ,得到的結果如表1-表 4所示。

表1 匹配不成功時各算法所花時間 m

表2 在正文頭部匹配成功時各算法所花時間 m

表3 在正文中部匹配成功時各算法所花時間 m

表4 在正文尾部匹配成功時各算法所花時間 m

從表 3-表 4的數據可以看出 ,在相同長度的正文串中 ,BM算法所花的時間總是最少的。由于 BM算法是從右向左的把模式同正文做比較 ,當模式符號做比較的文本符號在模式中沒有出現(xiàn)時,模式可以在這個文本符號之后移位m個位置 ,從而避免不必要的回溯,所以它的速度較快、效率高。

4 總 結

字符串匹配是模式匹配中最簡單的一個問題，但在文本處理領域中字符匹配是一個非常重要的主題。本文對字符串匹配技術進行了詳細的分析與探討，總結了字符串匹配問題的解決方法。重點對KMP模式匹配算法和BM模式匹配算法進行了深入剖析，并分析和比較了常用字符串匹配算法的性能和效率。

參考文獻：

[1] PODICHUK C, DELP E. Digital Watermarking：Algorithms and Applications[J]. IEEE Signal Processing Mag., 2001,18(4)：33-46

[2] PATTERSON R. A Pulse Ribbon Model of Monaural Phase Perception [J]. JASA,1997,82(5)：1560-1586

[3] BASSIA P, PITAS I, NIKOLAIDIS N. Robust Audio Watermarking in the Time Domain [J]. IEEE Trans. on Multimedia, 2001, 3(2)：232-241

[4] CRAVER S, MEMON N, BOON-LOCK Y. Resolving Rightful Ownerships with Invisible Watermarking Techniques：limitations, Attack, and Implications[J]. IEEE Journal on Selected Areas in Communication, 1998,16(4)：573-586

[5] 劉許剛； 黃海； 馬宏. 一種基于分段匹配的字符串匹配算法[J]. 計算機應用與軟件，2012，29(3)：128-131

[6] 廖秀玲， 邵劍飛， 李小武. 一種高效的字符串匹配算法[J]. 鄭州輕工業(yè)學院學報：自然科學版，2012，27(1)：65-68.