資源描述：
《多模式匹配快速算法的設計》由會員上傳分享，免費在線閱讀，更多相關內容在行業(yè)資料-天天文庫。
1、http://www.paper.edu.cn多模式匹配快速算法的設計李勝才北京航空航天大學北京100083E-mail：buaalsc@163.com摘要：字符串匹配速度是關鍵字檢測和過濾系統(tǒng)的核心。本文在有限狀態(tài)自動機的AC算法的基礎上，綜合BM算法的跳躍思想和QS算法的優(yōu)點，提出了一個快速的多模式字符串匹配算法。該算法能充分利用每次匹配過程中匹配不成功的信息和已經成功的信息，盡可能多地跳過待查文本串中的字符，從而不需要匹配目標文本串的每個字符，而在比較次數(shù)最少的情況下，能一次性無須回溯的實現(xiàn)對文本的快速搜索。實驗證明在模式串較長和較短的情況下，算法都能有
2、效地改善關鍵字檢測過濾系統(tǒng)的匹配性能。關鍵詞：多模式串匹配；有限自動機；關鍵字檢測過濾；匹配中圖分類號：TP301引言在信息檢索領域,串匹配問題一直都是研究的焦點之一。在拼寫檢查、基于字典的語言翻譯、WWW搜索引擎、計算機病毒特征碼匹配、數(shù)據(jù)壓縮以及DNA序列匹配等應用中也都需要進行串匹配。同時在基于特征匹配的入侵檢測系統(tǒng)中，模式匹配的效率直接決定這類入[2][6]侵檢測系統(tǒng)的性能。因此字符串匹配速度的提高有著深淵的意義。當前的多模式速度是[3][5]很多系統(tǒng)以及軟件的瓶頸。對于單模式匹配問題,有三種經典的匹配算法:①KMP算法,它在最壞情況下也能保持線[1]
3、[5]性查找過程,其時間復雜度為Omn(+)，②BM算法,它采用“跳躍式”查找策略,多數(shù)情況下無須對文本進行一次完整的掃描,在模式中字符在文本中出現(xiàn)很少時時間復雜度能到最[4][5][6][8]好的Onm(/),平均情況下其時間復雜度為Omn(+)。③QS算法，在那些待匹配模式集中未使用的字符在文本T中大量出現(xiàn)時,可以利用它們的信息加快匹配速度。在最優(yōu)情況下(模式串較短、模式串中出現(xiàn)的字母數(shù)較少)比BM算法更快,其時間復雜度為Onm(/)，最壞[5]情況時為Onm(×)。目前的多模式匹配中沒有一個很好的算法能結合以上各個單模式的優(yōu)點，本文在充分分析各個單模式匹
4、配算法的基礎上提出了一個新的多模式匹配的算法。該算[8]法結合了Boyer_Moore(BM)算法從右向左跳躍的思想，以及能實現(xiàn)最大跳躍和盡可能少的比較次數(shù)的QuickSearch(QS)算法的優(yōu)點，能充分利用每次匹配過程中匹配不成功的信息和已經成功的信息，盡可能多地跳過待查文本串中的字符，從而不需要匹配目標文本串的每個字符，而在比較次數(shù)最少的情況下，就能一次性無須回溯的實現(xiàn)對文本的快速搜索。1.新算法設計設待查找文本為T[1,2,??n],其定義在一個有限的字母表∑(本文處理背景選擇處理ANSI字符集0??256)上。多模式匹配則是從文本T中一次查找多個模式
5、串PPP,,,??P（這里patten_num代表模式串的數(shù)目）,最短模式串的長度用minlen123pattennum_表示。算法設計的主要思想在于匹配不成功后充分挖掘已經成功匹配的信息結合當前匹配失-1-http://www.paper.edu.cn敗信息得到向后跳躍的距離t_shift[]。整個算法可以分為預處理和搜索兩個部分。1.1預處理階段1.1.1構建模式匹配自動機，即構建狀態(tài)轉移函數(shù)state_shift[][],輸出函數(shù)output[]記錄該狀態(tài)下匹配成功的模式串下標，matched[state]記錄當前狀態(tài)state時已經匹配的字符串。構建多
6、模式匹配自動機，也就是構建多模式下的搜索樹。首先用待搜索的模式集構建一棵搜索樹，然后將樹的節(jié)點作為自動機的狀態(tài)，樹的分支作為自動機的狀態(tài)轉換函數(shù)。當字符在整個搜索樹內進行匹配時，由于搜索樹是預先知道的，故可用AC算法預先構造一個包含所有模式信息的反向樹型有限自動機。然后再利用BM算法，在文本中用搜索樹對文本進行跳躍式的搜索。在構建搜索樹時，將模式串的右邊對齊，從右向左進行構建，樹上相同的分支節(jié)點進行合并。這樣匹配窗內文本最右面的字符就不需要和搜索樹中的每一個字符進行匹配，而是直接將這個字符輸入到匹配自動機，得到搜索樹的匹配輸出。在反向有限自動機的構造中，每個模
7、式串的字符是從后向前輸入到反向樹型有限自動機的；匹配過程中，目標串的輸入也是從后向前進行逆向掃描的。為方便描述本文的有限自動機是通過二維矩陣state_shift[MAXSTATE][M1]來表示的，其中MAXSTATE事先定義，代表最大可能狀態(tài)數(shù)，M1代表模式匹配的文本集合總數(shù)（本文限制在0~256之間）。以添加li，sheng，cai為例，介紹反向樹的構造過程（如圖1）-{i}0i1l2Step1添加liStep2添加sheng圖1:Step3添加cai圖中灰色狀態(tài)表示該狀態(tài)成功匹配模式串。1.1.2計算在掃描階段可能出現(xiàn)的任何字符可以跳躍的最大距離:要獲
8、得更快的匹配算法，關鍵是在模式串匹配失
