字符串匹配

傳統的匹配算法

串匹配算法雖然發展了幾十年，然而非常實用的算法是近年才出現。串匹配問題的研究存在理論研究和實際應用的脱節。那些專門從事算法研究的學者關心的只是理論上看起來很美妙的算法——具有很好的時間複雜度。而開發人員只追求實際應用中儘可能快的算法。兩者之間從不注意對方在幹什麼。將理論研究和實際應用結合的算法(如BNDM算法)只是近年才出現。在實際應用中常常很難找到適合需求的算法——這樣的算法實際上是存在的，但是隻有資深專家才比較瞭解。考慮如下情況，一位軟件開發人員，或者一位計算生物學家，或者一位研究人員，又或者一位學生，對字符串匹配領域並沒有深入瞭解，可是現在需要處理一個文本搜索問題。那些汗牛充棟的書籍使得閲讀者淹沒在各種匹配算法的海洋中，卻沒有足夠的知識選擇最適用的算法。最後，常常導致這樣的局面：選擇一種最簡單的算法加以實現。這往往導致很差的性能，從而影響整個開發系統的質量。更糟糕的是，選擇了一個理論上看起來很漂亮的算法，並且花費了大量精力去實現。結果，卻發現實際效果和一個簡單算法差不多，甚至還不如簡單算法。因此，應該選用一種“實用”算法，即在實際應用中性能較好，並且一個普通程序員能在幾小時內完成算法的實現代碼。另外，在字符串匹配研究領域中，一個人所共知的事實是“算法的思想越簡單，實際應用的效果越好”。

傳統的串匹配算法可以概括為前綴搜索、後綴搜索、子串搜索。代表算法有KMP，Shift-And，Shift-Or，BM，Horspool，BNDM，BOM等。所用到的技術包括滑動窗口、位並行、自動機、後綴樹等。

它的應用包括生物信息學、信息檢索、拼寫檢查、語言翻譯、數據壓縮、網絡入侵檢測。例如在生物信息學中，啓動子有助於研究者從數以億計的ACGT序列中快速定位內含子的起始位置，這些啓動子中較常見的有TATA序列。它常常出現在CAATCT序列之後。它們之間並不是連續出現，而是間隔了30-50個通配符。又比如在信息檢索中，一個挑戰性的任務是，搜索出由用户自定義的模式對應在文本中的匹配位置，這種模式很可能帶有通配符。在上述應用背景下，一種更加靈活的帶有通配符的模式串應運而生。

1974年Fischer和Paterson將通配符don't cares引入模式匹配問題 ^[2]  ，之後模式匹配的定義出現了各種各樣非標準形式：按匹配方式分，有容錯的近似匹配，交換相鄰字母的交換匹配，服務於程序代碼查錯的參數匹配等；按匹配對象分，T、P可以是一張二維表，也可以分別含有通配符；按匹配結果分，有返回匹配位置和匹配數兩種定義。Muthukrishna等人將上述各類問題統稱為Non-standard Stringology ^[3]  。然而，通配符的引入會讓問題定義更加靈活，卻也帶來了複雜性。算法的設計有時不僅僅考慮時空效率，保證匹配結果的完備性很可能成為算法設計更重要的問題。甚至其中的某些問題被猜測具有NP難度。

在Fischer和Paterson於1974年將通配符*引入模式匹配問題之後，如何將通配符與傳統的模式匹配有效結合是研究的重點。這其中，最具代表性的定義是通配符指代的字符數不僅僅用一個固定的常數表示，而是一個可由用户自定義的區間 ^[4]  ，即帶有上下限約束，如TCT*(30,50)TATA。 ^[5]  將上述帶有區間的通配符擴展至任意兩兩相鄰的字符之間，然而所有的通配符上下限相同，如A*(1,3)C*(1,3)G*(1,3)C。為了進一步放寬約束， ^[6]  提出了不同通配符彼此獨立的思想，如A*(0,3)C*(2,4)G*(1,1)C。

近似匹配是一種允許誤差的串匹配。這種誤差的度量一般用編輯距離，記為k。衡量編輯距離的操作包括插入、刪除、替換。問題的輸入是文本T，模式P和編輯距離k，輸出是匹配數或匹配位置。常用的方法包括動態規劃、自動機、位並行和過濾算法。近似匹配也屬於Non-standard Stringology問題。它最常見的應用背景來源於生物信息學。問題定義上，近似匹配中的k可以對模式中的任何字符的編輯操作進行計數。例如，給定文本T的子串T’= ……aacct……，P = aaacc，從P到T’要經過兩次替換操作，因此k= 2。

將兩個或多個序列排列在一起，標明其相似之處。序列中可以插入間隔。序列比對中也允許錯誤匹配，也需要計算編輯距離。與近似匹配相比，序列比對將文本和模式都看作序列，且長度接近。序列比對最廣的應用是生物信息學，將未知序列同已知序列進行相似性比較是一種強有力的研究手段。例如，序列的片段測定，拼接，基因的表達分析，RNA和蛋白質的結構功能預測。

序列模式挖掘是數據挖掘的一個重要分支，是基於時間或者其他序列的經常發生的模式。序列模式的一個例子就是“一個9個月前買了一台PC的顧客有可能在一個月內買一個新的CPU”。很多數據都是這種時間序列形式的，我們就可以用它來市場趨勢分析，客户保留和天氣預測等等。序列模式首先是由R.Agrawal和R.Srikant提出的，隨後幾年研究者所提出的算法都是基於Apriori原理的改進算法。隨後Zaki等人提出了基於垂直數據表示的SPADE算法。Han等提出了不產生候選集的基於模式增長的FP-Growth算法。接着Han等又研究出了基於投影數據庫的FreeSpan和PrefixSpan算法。

一般而言，好的字符串匹配算法要有以下特點:

這是評價一個字符匹配算法最重要的標準。通常要求字符匹配能以線性速度執行。目前，網絡安全應用中的基於誤用的NIDS使用字符串匹配算法進行入侵檢測，因此，隨着網速的提高，對字符串匹配速度的需求同樣也在提高。

有幾種時間複雜性的評價指標：

1)預處理時間的複雜性:有些算法在進行字符串匹配前需要對模式特徵進行預處理;

2)匹配階段的時間複雜性:字符串匹配過程中執行查找操作的時間複雜性，它通常和文本長度及模式長度相關;

3)最壞情況下的時間複雜性:對一個text進行字符模式匹配時，設法降低各算法的最壞情況下的時間複雜性是目前的研究熱點之一;

4)最好情況下的時間複雜性:對一個text進行字符模式匹配時的最好的可能性。

執行預處理和模式匹配不僅需要CPU資源還需要內存資源，儘管目前內存的容量較以前大得多，但為了提高速度，人們常利用特殊硬件。通常，特殊硬件中內存訪問速度很快但容量偏小，這時，佔用資源少的算法將更具優勢。 ^[7] 

字符串匹配工作一直是IDS研究領域中的熱點之一。在網絡速度迅速發展的今天，基於字符匹配技術的網絡應用存在着性能瓶頸，提高系統的整體性能是研究和設計者的主要工作。字符匹配是其實現網絡入侵檢測的主要技術之一，因此，高效的算法將是提高系統總體性能的手段之一。在字符匹配算法中存在這樣的幾個定理:一個是“任何的字符串匹配算法在最糟的情況下必須檢查至少n-m+1個text中的字符”，這説明沒有哪一個算法會比KMP或BM有更好的計算複雜性。算法的平均性能可以得到提高，但最糟情況下的結果是一個嚴格的限制;另一個定理是“任何字符匹配算法至少檢查n/m個字符”，這個是顯而易見的。基於以上的結論，接下來研究的主要方向是設法提高算法的平均性能和減少資源耗費:主要的途徑可以採用在實際的網絡應用中設法減少m或n的值來減少實際匹配的次數;設法將部分匹配算法移植到硬件的實現中或在並行的體系結構卜實現等，以減少匹配所耗費的時問。 ^[7]