基于QS的字符串匹配改進算法

串匹配問題是計算機科學(xué)領(lǐng)域研究中的一個焦點問題，它在諸多非數(shù)值處理方面都有著非常廣泛的應(yīng)用。串匹配就是在一個大的正文T中搜索指定模式P的所有出現(xiàn)位置。按照功能，串匹配算法主要分為三類：精確串匹配算法、近似串匹配算法和正則表達式算法。其中，最有影響的是KMP算法、BM算法、RK隨機算法和SUANDAY算法以及由此而產(chǎn)生的一些改進算法。在實際應(yīng)用中，這些算法都各有千秋，各有側(cè)重。

1 BM和QC算法分析

字符串匹配問題描述：

1.1 BM算法

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

BM算法的預(yù)處理分為壞字符轉(zhuǎn)移表和好后綴轉(zhuǎn)移表。

壞字符移動表記錄的是字符char在模式串P中的最右出現(xiàn)位置。具體表述為：

BM算法的空間復(fù)雜度和預(yù)處理時間均為O（m+σ）。在最壞情況下，它的時間復(fù)雜度為O（nm）；在最好情況下，時間復(fù)雜度為O（n/m）。

從理論上講，BM算法的時間復(fù)雜度要大大高于KMP算法的時間復(fù)雜度O（m+n），但在實際應(yīng)用中，BM算法的搜索步長接近于模式長度m，所以執(zhí)行效率非常高。

1.2 QS算法

QS算法是一種簡單、快速、實用的算法。在模式匹配過程中，該算法將發(fā)生失配的字符與計算右移量兩者獨立開來的現(xiàn)象，其僅利用T[i+m]字符計算BadcharShift[T[i+m]]來決定模式轉(zhuǎn)移。通常情況下，模式轉(zhuǎn)移量為m+1，這大大提高了算法的搜索步長和匹配效率。

QS算法的預(yù)處理與BM算法的對壞字符啟發(fā)的預(yù)處理相同。

QS算法的匹配過程如下：

QS算法的空間復(fù)雜度和預(yù)處理時間均為O（m+σ）。在最壞情況下，它的時間復(fù)雜度為O（mn）；在最好情況下，時間復(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]在模式中時，QS算法的效率就會大打折扣。

2 新算法

2.1 算法基本思想及步驟

本文在上述分析的基礎(chǔ)上，充分挖掘了其潛在可利用的隱含信息，進一步優(yōu)化和完善了QS算法。在預(yù)處理方面，新算法與QS算法基本相同，不同的是當(dāng)模式在當(dāng)前模式匹配窗口內(nèi)自右向左匹配正文的過程中發(fā)生失配時，比較正文中T[i+m]和T[i+m-1]這兩個字符的移動距離，取其最大值進行移動，然后在新位置重新開始模式匹配。圖1為一個新算法匹配過程示例。

新算法的匹配過程如下：

新算法在QS算法的基礎(chǔ)上，充分利用了失配時T[i+m-1]和T[i+m]兩個字符引起的移動距離的最大值，使得移動距離增大，減少了模式匹配的比較次數(shù)。通常情況下，新算法的時間復(fù)雜度為O（n/m+1）。

2.2 性能測試

針對本文提出的新算法，從參考文獻[1]中抽取chapter 32 STring Matching中第一段內(nèi)容作為測試正文，并在同樣的軟硬件環(huán)境下對BF、BM、QS和新算法進行比較，以檢測新算法在性能和效率方面的表現(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ù)少、耗時小、效率高的快速字符串匹配算法。