摘  要： 本文在分析BM和QS算法特點(diǎn)的基礎(chǔ)上，綜合利用了正文T[i+m-1]和T[i+m]位置上的字符信息，提出一種移動距離不小于模式長度的快速字符串匹配算法。該算法解決了QS算法在skip[i+m-1]<skip[i+m]時(shí)低效的問題。
關(guān)鍵詞： 模式匹配  串搜索  算法

　　串匹配問題是計(jì)算機(jī)科學(xué)領(lǐng)域研究中的一個(gè)焦點(diǎn)問題，它在情報(bào)檢索、自然語言翻譯、基因序列匹配、壓縮數(shù)據(jù)、圖像處理、網(wǎng)絡(luò)入侵檢測以及事務(wù)管理系統(tǒng)等諸多非數(shù)值處理方面都有著非常廣泛的應(yīng)用。串匹配就是在一個(gè)大的正文T中搜索指定模式P的所有出現(xiàn)位置。按照功能，串匹配算法主要分為三類：精確串匹配算法、近似串匹配算法和正則表達(dá)式算法。其中，最有影響的是KMP算法、BM算法、RK隨機(jī)算法和SUANDAY算法以及由此而產(chǎn)生的一些改進(jìn)算法。在實(shí)際應(yīng)用中，這些算法都各有千秋，各有側(cè)重。
1  BM和QC算法分析
　　字符串匹配問題描述：

1.1 BM算法
　　BM是由Boyer和Moore于1977年提出的，它是一種簡單、快速、通用的工程算法。它的特點(diǎn)是在窗口內(nèi)部從右向左逆向匹配，采用壞字符啟發(fā)和好后綴啟發(fā)兩種方法，通過預(yù)處理模式分別計(jì)算BadcharShift[char]和GoodSufShift[char]轉(zhuǎn)移表。當(dāng)發(fā)現(xiàn)不匹配時(shí)，選擇兩者中的最大值作為模式向右移動的距離。
BM算法的預(yù)處理分為壞字符轉(zhuǎn)移表和好后綴轉(zhuǎn)移表兩個(gè)階段。
　　壞字符移動表BadcharShift[char]記錄的是字符char在模式串P中的最右出現(xiàn)位置。具體表述為：
　　

　　BM算法的空間復(fù)雜度和預(yù)處理時(shí)間均為O(m+σ)。在最壞情況下，它的時(shí)間復(fù)雜度為O（nm）；在最好情況下，時(shí)間復(fù)雜度為O（n/m）。
　　從理論上講，BM算法的時(shí)間復(fù)雜度要大大高于KMP算法的時(shí)間復(fù)雜度O（m+n），但在實(shí)際應(yīng)用中，BM算法的搜索步長接近于模式長度m，所以執(zhí)行效率非常高。
1.2 QS算法
　　QS算法是一種簡單、快速、實(shí)用的算法。在模式匹配過程中，該算法將發(fā)生失配的字符與計(jì)算右移量兩者獨(dú)立開來的現(xiàn)象，其僅利用T[i+m]字符計(jì)算BadcharShift[T[i+m]]來決定模式轉(zhuǎn)移。通常情況下，模式轉(zhuǎn)移量為m+1，這大大提高了算法的搜索步長和匹配效率。
　　QS算法的預(yù)處理與BM算法的對壞字符啟發(fā)的預(yù)處理相同。
　　QS算法的匹配過程如下：
　　

　　QS算法的空間復(fù)雜度和預(yù)處理時(shí)間均為O（m+σ）。在最壞情況下，它的時(shí)間復(fù)雜度為O(mn)；在最好情況下，時(shí)間復(fù)雜度為O(n/m+1)。
　　QS算法利用了失配情況下T[i+m]字符引起的Badchar-
　　Shift[T[i+m]]，大大簡化了初始化過程，使其編碼簡單且調(diào)試迅速。通常情況下，QS算法比BM算法要快，但是當(dāng)T[i+m-1]不在模式中，而T[i+m]在模式中時(shí)，即(m-BadcharShift[T[i+m-1]])>(m-BadcharShift[T[i+m]])時(shí)，QS算法的效率就會大打折扣。
2  新算法
2.1 算法基本思想及步驟
　　針對上述分析，本文在吸收BM算法在模式窗口內(nèi)自右向左逆向搜索的特點(diǎn)和QS算法利用BadcharShift[T[i+m]]向右最大移動模式串的特點(diǎn)的基礎(chǔ)上，充分挖掘了BadcharShift[T[i+m-1]]的潛在可利用的隱含信息，進(jìn)一步優(yōu)化和完善了QS算法。在預(yù)處理方面，新算法與QS算法基本相同，不同的是當(dāng)模式在當(dāng)前模式匹配窗口內(nèi)自右向左匹配正文的過程中發(fā)生失配時(shí)，比較正文中T[i+m]和T[i+m-1]這兩個(gè)字符的移動距離，取其最大值進(jìn)行移動，然后在新位置重新開始模式匹配。圖1為一個(gè)新算法匹配過程示例。

　　新算法的匹配過程如下：

　　新算法在QS算法的基礎(chǔ)上，充分利用了失配時(shí)T[i+m-1]和T[i+m]兩個(gè)字符引起的移動距離的最大值，使得移動距離增大，減少了模式匹配的比較次數(shù)。通常情況下，新算法的時(shí)間復(fù)雜度為O（n/m+1）。
2.2 性能測試
　　針對本文提出的新算法，從參考文獻(xiàn)[1]中抽取chapter 32 String Matching中第一段內(nèi)容作為測試正文，并在同樣的軟硬件環(huán)境下對BF、BM、QS和新算法進(jìn)行比較，以檢測新算法在性能和效率方面的表現(xiàn)。表1為各種算法性能比較結(jié)果。

　　測試正文：
　　Finding all occurrences of a pattern in a text is a problem that arises frequently in text editing programs.Typically，the text is a document being edited，and the pattern searched for is a particular word supplied by the user.Efficiedt algorithms for this problem can greatly aid the responsiveness of the test editing program.String matching algorithms are also used，for example，to search for particular patterns in DNA sequences.
　　搜索模式：the pattern searched
　　由表1可知：新算法是一種比較次數(shù)少、耗時(shí)小、效率高的快速字符串匹配算法。

參考文獻(xiàn)
1   Knuth D E，Morris J H，Pratt V R.Fast pattern matching in  string.SIAM Journal on Computing，1977；6(2)
2   Boyer R S，Moore J S.A fast string searching algorithm.  Communications of ACM，1977；20(10)
3   Sunday D M.A very fast substring search algorithm.Communication of the ACM，1990；33(1)
4   Cormen T H，Leiserson C E，Rivest R L.TNTRODUCTION TO ALGORITHM(secondd edition).The Massachusetts Institute of Technology，2001；907