多模式匹配快速算法的設(shè)計(jì)

《多模式匹配快速算法的設(shè)計(jì)》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。

1、http://www.paper.edu.cn多模式匹配快速算法的設(shè)計(jì)李勝才北京航空航天大學(xué)北京100083E-mail：buaalsc@163.com摘要：字符串匹配速度是關(guān)鍵字檢測(cè)和過(guò)濾系統(tǒng)的核心。本文在有限狀態(tài)自動(dòng)機(jī)的AC算法的基礎(chǔ)上，綜合BM算法的跳躍思想和QS算法的優(yōu)點(diǎn)，提出了一個(gè)快速的多模式字符串匹配算法。該算法能充分利用每次匹配過(guò)程中匹配不成功的信息和已經(jīng)成功的信息，盡可能多地跳過(guò)待查文本串中的字符，從而不需要匹配目標(biāo)文本串的每個(gè)字符，而在比較次數(shù)最少的情況下，能一次性無(wú)須回溯的實(shí)現(xiàn)對(duì)文本的快速搜索。實(shí)驗(yàn)證明在模式串較長(zhǎng)和較短的情況下，算法都能有效地改善關(guān)鍵字檢測(cè)過(guò)濾系統(tǒng)的匹配

2、性能。關(guān)鍵詞：多模式串匹配；有限自動(dòng)機(jī)；關(guān)鍵字檢測(cè)過(guò)濾；匹配中圖分類號(hào)：TP301引言在信息檢索領(lǐng)域,串匹配問(wèn)題一直都是研究的焦點(diǎn)之一。在拼寫檢查、基于字典的語(yǔ)言翻譯、WWW搜索引擎、計(jì)算機(jī)病毒特征碼匹配、數(shù)據(jù)壓縮以及DNA序列匹配等應(yīng)用中也都需要進(jìn)行串匹配。同時(shí)在基于特征匹配的入侵檢測(cè)系統(tǒng)中，模式匹配的效率直接決定這類入[2][6]侵檢測(cè)系統(tǒng)的性能。因此字符串匹配速度的提高有著深淵的意義。當(dāng)前的多模式速度是[3][5]很多系統(tǒng)以及軟件的瓶頸。對(duì)于單模式匹配問(wèn)題,有三種經(jīng)典的匹配算法:①KMP算法,它在最壞情況下也能保持線[1][5]性查找過(guò)程,其時(shí)間復(fù)雜度為Omn(+)，②BM算法,它采用

3、“跳躍式”查找策略,多數(shù)情況下無(wú)須對(duì)文本進(jìn)行一次完整的掃描,在模式中字符在文本中出現(xiàn)很少時(shí)時(shí)間復(fù)雜度能到最[4][5][6][8]好的Onm(/),平均情況下其時(shí)間復(fù)雜度為Omn(+)。③QS算法，在那些待匹配模式集中未使用的字符在文本T中大量出現(xiàn)時(shí),可以利用它們的信息加快匹配速度。在最優(yōu)情況下(模式串較短、模式串中出現(xiàn)的字母數(shù)較少)比BM算法更快,其時(shí)間復(fù)雜度為Onm(/)，最壞[5]情況時(shí)為Onm(×)。目前的多模式匹配中沒(méi)有一個(gè)很好的算法能結(jié)合以上各個(gè)單模式的優(yōu)點(diǎn)，本文在充分分析各個(gè)單模式匹配算法的基礎(chǔ)上提出了一個(gè)新的多模式匹配的算法。該算[8]法結(jié)合了Boyer_Moore(BM)算

4、法從右向左跳躍的思想，以及能實(shí)現(xiàn)最大跳躍和盡可能少的比較次數(shù)的QuickSearch(QS)算法的優(yōu)點(diǎn)，能充分利用每次匹配過(guò)程中匹配不成功的信息和已經(jīng)成功的信息，盡可能多地跳過(guò)待查文本串中的字符，從而不需要匹配目標(biāo)文本串的每個(gè)字符，而在比較次數(shù)最少的情況下，就能一次性無(wú)須回溯的實(shí)現(xiàn)對(duì)文本的快速搜索。1.新算法設(shè)計(jì)設(shè)待查找文本為T[1,2,??n],其定義在一個(gè)有限的字母表∑(本文處理背景選擇處理ANSI字符集0??256)上。多模式匹配則是從文本T中一次查找多個(gè)模式串PPP,,,??P（這里patten_num代表模式串的數(shù)目）,最短模式串的長(zhǎng)度用minlen123pattennum_表示。

5、算法設(shè)計(jì)的主要思想在于匹配不成功后充分挖掘已經(jīng)成功匹配的信息結(jié)合當(dāng)前匹配失-1-http://www.paper.edu.cn敗信息得到向后跳躍的距離t_shift[]。整個(gè)算法可以分為預(yù)處理和搜索兩個(gè)部分。1.1預(yù)處理階段1.1.1構(gòu)建模式匹配自動(dòng)機(jī)，即構(gòu)建狀態(tài)轉(zhuǎn)移函數(shù)state_shift[][],輸出函數(shù)output[]記錄該狀態(tài)下匹配成功的模式串下標(biāo)，matched[state]記錄當(dāng)前狀態(tài)state時(shí)已經(jīng)匹配的字符串。構(gòu)建多模式匹配自動(dòng)機(jī)，也就是構(gòu)建多模式下的搜索樹。首先用待搜索的模式集構(gòu)建一棵搜索樹，然后將樹的節(jié)點(diǎn)作為自動(dòng)機(jī)的狀態(tài)，樹的分支作為自動(dòng)機(jī)的狀態(tài)轉(zhuǎn)換函數(shù)。當(dāng)字符在整個(gè)搜

6、索樹內(nèi)進(jìn)行匹配時(shí)，由于搜索樹是預(yù)先知道的，故可用AC算法預(yù)先構(gòu)造一個(gè)包含所有模式信息的反向樹型有限自動(dòng)機(jī)。然后再利用BM算法，在文本中用搜索樹對(duì)文本進(jìn)行跳躍式的搜索。在構(gòu)建搜索樹時(shí)，將模式串的右邊對(duì)齊，從右向左進(jìn)行構(gòu)建，樹上相同的分支節(jié)點(diǎn)進(jìn)行合并。這樣匹配窗內(nèi)文本最右面的字符就不需要和搜索樹中的每一個(gè)字符進(jìn)行匹配，而是直接將這個(gè)字符輸入到匹配自動(dòng)機(jī)，得到搜索樹的匹配輸出。在反向有限自動(dòng)機(jī)的構(gòu)造中，每個(gè)模式串的字符是從后向前輸入到反向樹型有限自動(dòng)機(jī)的；匹配過(guò)程中，目標(biāo)串的輸入也是從后向前進(jìn)行逆向掃描的。為方便描述本文的有限自動(dòng)機(jī)是通過(guò)二維矩陣state_shift[MAXSTATE][M1]來(lái)

7、表示的，其中MAXSTATE事先定義，代表最大可能狀態(tài)數(shù)，M1代表模式匹配的文本集合總數(shù)（本文限制在0~256之間）。以添加li，sheng，cai為例，介紹反向樹的構(gòu)造過(guò)程（如圖1）-{i}0i1l2Step1添加liStep2添加sheng圖1:Step3添加cai圖中灰色狀態(tài)表示該狀態(tài)成功匹配模式串。1.1.2計(jì)算在掃描階段可能出現(xiàn)的任何字符可以跳躍的最大距離:要獲得更快的匹配算法，關(guān)鍵是在模式串匹配失