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

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

1 BM和QC算法分析

字符串匹配問(wèn)題描述：

1.1 BM算法

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

BM算法的預處理分為壞字符轉移表和好后綴轉移表。

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

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

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

1.2 QS算法

QS算法是一種簡(jiǎn)單、快速、實(shí)用的算法。在模式匹配過(guò)程中，該算法將發(fā)生失配的字符與計算右移量?jì)烧擢毩㈤_(kāi)來(lái)的現象，其僅利用T[i+m]字符計算BadcharShift[T[i+m]]來(lái)決定模式轉移。通常情況下，模式轉移量為m+1，這大大提高了算法的搜索步長(cháng)和匹配效率。

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

QS算法的匹配過(guò)程如下：

QS算法的空間復雜度和預處理時(shí)間均為O（m+σ）。在最壞情況下，它的時(shí)間復雜度為O（mn）；在最好情況下，時(shí)間復雜度為O（n/m+1）。

QS算法利用了失配情況下T[i+m]字符引起的Badchar-

Shift[T[i+m]]使其編碼簡(jiǎn)單且調試迅速。通常情況下，QS算法比BM算法要快，但是當T[i+m-1]不在模式中，而T[i+m]在模式中時(shí)，QS算法的效率就會(huì )大打折扣。

2 新算法

2.1 算法基本思想及步驟

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

新算法的匹配過(guò)程如下：

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

2.2 性能測試

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

測試正文：

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