母 澤 平

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

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

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

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

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

2 字符串匹配技術(shù)常用算法分析

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

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

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

(4) BMH算法。1980 年, Horspool 提出了對(duì)BM 算法的一種改進(jìn)算法——BMH算法。首先比較文本指針?biāo)缸址湍Ｊ降淖詈笠粋€(gè)字符,如相等再比較其余m-1個(gè)字符。無(wú)論文本中哪個(gè)字符造成了匹配失敗,都將由文本中和模式最后一個(gè)位置對(duì)應(yīng)的字符來(lái)啟發(fā)模式向右的滑動(dòng)。即文本自位置I起與模式的從右至左的匹配檢查中, 一旦發(fā)現(xiàn)不匹配,就將I重新賦值為End+d[T[End]]。(End是一個(gè)中間變量,記錄了文本中每次從右至左匹配的起始位置)。

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

3 相關(guān)算法性能測(cè)試和結(jié)果分析

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

表1 匹配不成功時(shí)各算法所花時(shí)間 m

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

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

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

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

4 總 結(jié)

字符串匹配是模式匹配中最簡(jiǎn)單的一個(gè)問(wèn)題，但在文本處理領(lǐng)域中字符匹配是一個(gè)非常重要的主題。本文對(duì)字符串匹配技術(shù)進(jìn)行了詳細(xì)的分析與探討，總結(jié)了字符串匹配問(wèn)題的解決方法。重點(diǎn)對(duì)KMP模式匹配算法和BM模式匹配算法進(jìn)行了深入剖析，并分析和比較了常用字符串匹配算法的性能和效率。

參考文獻(xiàn)：

[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]. 計(jì)算機(jī)應(yīng)用與軟件，2012，29(3)：128-131

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