字元串匹配

字元串匹配是計算機科學中最古老、研究最廣泛的問題之一。一個字元串是一個定義在有限字母表∑上的字元序列。例如，ATCTAGAGA是字母表∑ = {A,C,G,T}上的一個字元串。字元串匹配問題就是在一個大的字元串T中搜尋某個字元串P的所有出現位置。其中，T稱為文本，P稱為模式，T和P都定義在同一個字母表∑上。

基本介紹

• 中文名：字元串匹配
• 套用：生物信息學、信息檢索、拼寫檢查
• 匹配種類：柔性字元串匹配
• 性質：最古老、研究最廣泛的問題

傳統算法

傳統的匹配算法

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

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

套用

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

匹配種類

柔性字元串匹配

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

非標準字元串匹配

帶有通配符的串匹配

在Fischer和Paterson於1974年將通配符*引入模式匹配問題之後，如何將通配符與傳統的模式匹配有效結合是研究的重點。這其中，最具代表性的定義是通配符指代的字元數不僅僅用一個固定的常數表示，而是一個可由用戶自定義的區間，即帶有上下限約束，如TCT*(30,50)TATA。將上述帶有區間的通配符擴展至任意兩兩相鄰的字元之間，然而所有的通配符上下限相同，如A*(1,3)C*(1,3)G*(1,3)C。為了進一步放寬約束，提出了不同通配符彼此獨立的思想，如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資源還需要記憶體資源，儘管目前記憶體的容量較以前大得多，但為了提高速度，人們常利用特殊硬體。通常，特殊硬體中記憶體訪問速度很快但容量偏小，這時，占用資源少的算法將更具優勢。

未來的工作

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