基于QS的字符串匹配改進(jìn)算法

串匹配問題是計(jì)算機(jī)科學(xué)領(lǐng)域研究中的一個(gè)焦點(diǎn)問題，它在諸多非數(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年提出的，它是一種簡(jiǎn)單、快速、通用的工程算法。它的特點(diǎn)是在窗口內(nèi)部從右向左逆向匹配，采用壞字符啟發(fā)和好后綴啟發(fā)兩種方法，通過預(yù)處理模式分別計(jì)算BadcharShift[char]和GoodSufShift[char]轉(zhuǎn)移表。當(dāng)發(fā)現(xiàn)不匹配時(shí)，選擇兩者中的最大值作為模式向右移動(dòng)的距離。

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

壞字符移動(dòng)表記錄的是字符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算法是一種簡(jiǎn)單、快速、實(shí)用的算法。在模式匹配過程中，該算法將發(fā)生失配的字符與計(jì)算右移量兩者獨(dú)立開來的現(xiàn)象，其僅利用T[i+m]字符計(jì)算BadcharShift[T[i+m]]來決定模式轉(zhuǎn)移。通常情況下，模式轉(zhuǎn)移量為m+1，這大大提高了算法的搜索步長和匹配效率。

QS算法的預(yù)處理與BM算法的對(duì)壞字符啟發(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]]使其編碼簡(jiǎn)單且調(diào)試迅速。通常情況下，QS算法比BM算法要快，但是當(dāng)T[i+m-1]不在模式中，而T[i+m]在模式中時(shí)，QS算法的效率就會(huì)大打折扣。

2 新算法

2.1 算法基本思想及步驟

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

新算法的匹配過程如下：

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

2.2 性能測(cè)試

針對(duì)本文提出的新算法，從參考文獻(xiàn)[1]中抽取chapter 32 STring Matching中第一段內(nèi)容作為測(cè)試正文，并在同樣的軟硬件環(huán)境下對(duì)BF、BM、QS和新算法進(jìn)行比較，以檢測(cè)新算法在性能和效率方面的表現(xiàn)。表1為各種算法性能比較結(jié)果。

測(cè)試正文：

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í)小、效率高的快速字符串匹配算法。