Aho—Corasick算法與Boyer—Moore算法

摘 要：在網(wǎng)絡(luò)安全的研究過程中，字符串匹配是一種非常很重要的技術(shù)，很多殺毒軟件的特征碼匹配，都需要用到字符串匹配。字符串匹配是計算機科學(xué)中最古老、研究最廣泛的問題之一。本文對多模式字符匹配的兩種關(guān)鍵算法Aho-Corasick算法與Boyer-Moore算法進行討論。

關(guān)鍵詞：Aho-Corasick；Boyer-Moore；算法

中圖分類號：TP393.08 文獻標(biāo)識碼：A 文章編號：1674-7712 （2013） 18-0000-01

一、Aho-Corasick（AC）算法

Aho-Corasick自動機算法：簡稱AC自動機，是一種多模式匹配算法。Aho-Corasick算法是目前應(yīng)用最為廣泛的一種多模式匹配的算法。它可以在目標(biāo)串查找多個模式串，出現(xiàn)次數(shù)和出現(xiàn)的位置。其適合用在一個長字符串里查找多個可能的子字符串。它所采用的思想是有限狀態(tài)自動機—將待檢測數(shù)據(jù)可視作一個流，用已有的多個模式串構(gòu)成一個有限狀態(tài)的自動機，而，這個流的每一個在字符進入狀態(tài)機以后，都會使自動機改變一種狀態(tài)，從而有可能得到某個模式串匹配發(fā)生。AC算法原理：設(shè)存在四個模式串的模式集合為{he，she，his，hers），在預(yù)處理過程中通可以得到以下三個函數(shù)：第一個函數(shù)：狀念跳轉(zhuǎn)函數(shù)Goto，如圖1所示：

下如上面的Fail函數(shù)所描述，在某個狀態(tài)i發(fā)生了匹配失敗時，有限狀態(tài)自動機將轉(zhuǎn)入下一個狀態(tài)“i”。第三個函數(shù)：輸出函數(shù)Output，如圖3所示

i表示的是自動機當(dāng)前的狀態(tài)，當(dāng)自動機進入到當(dāng)前狀態(tài)為2，5，7，9中任意其一的時候，也就是說匹配發(fā)生了，因而，從輸出函數(shù)output（i）的值可以知道發(fā)生匹配的具體是哪一個或者是哪幾個模式串。

Aho-Corasick算法同時，理論分析還表明，可以實現(xiàn)Goto函數(shù)和Fail函數(shù)算法，使得預(yù)處理階段的時間消耗與模式串集合的總長度成線性關(guān)系。

二、Boyer-Moore（BM）算法

Boyer-Moore算法是一種基于后綴匹配的模式串匹配算法，Aho-Corasick算法可以說是多模式匹配算法的基礎(chǔ)，對于多模式匹配來講是一個很好的結(jié)果。它提出了很多重要的思想都值得借鑒，而后的許多發(fā)展和優(yōu)化都建立在這種算法上。另一種模式匹配算法—BM算法在進行匹配時，可以讓模式串每次向右移動盡可能大的距離，BM算法是一種后綴匹配，這種算法模式串的比較是從右到左的，模式串的移動也是從左到右的匹配過程，可以說經(jīng)典的BM算法其實就是對后綴蠻力匹配算法為了實現(xiàn)更快移動模式串，BM算法定義了兩個規(guī)則：

（一）好后綴規(guī)則

當(dāng)某個字符不相同時使用壞字符規(guī)則右移模式串，通過delta1函數(shù)計算出來。

（二）壞字符規(guī)則

在不丟失真解的前提下確定一個新的移動距離delta。

如圖4給出定義：

圖4 好后綴規(guī)則，壞字符規(guī)則

當(dāng)某趟比較中出現(xiàn)不匹配時，BM算法采用兩條啟發(fā)性規(guī)則計算模式串右移的距離，即壞字符規(guī)則和好后綴規(guī)則。在算法中，模式串匹配不上母串的最壞情況，后綴蠻力匹配算法的時間復(fù)雜度最差的情況是O（n×m），最好是O（n），其中，n是母串的長度，m是模式串的長度。也就是說，BM算法時間復(fù)雜度最好是O（n/（m+1）），最差是O（n）。

三、算法比較

AC算法部分比AC自動機算法的實現(xiàn)要簡單，雖實際上要比BM算法本身的實現(xiàn)要復(fù)雜一點，因為這是對BM算法的多模式一種擴展。但是此算法不用去考慮失效函數(shù)的問題。BM算法在利用KMP算法的基礎(chǔ)上，發(fā)明了一條壞字符算法。AC算法在KMP算法基礎(chǔ)上，使用規(guī)則樹狀態(tài)機的算法可以滿足同時匹配多個模式串。還有一種改進的AC-BM算法。它是多模式匹配的算法。ACBM則是在BM算法基礎(chǔ)上，使用規(guī)則數(shù)狀態(tài)機的算法可以滿足同時匹配多個模式串。

參考文獻：

[1]杜浩陽.Snort中BM模式匹配算法的研究與改進[J].河南城建學(xué)院學(xué)報，2009，03.

[2]唐謙，張大方.入侵檢測中模式匹配算法的性能分析[J].計算機工程與應(yīng)用，2005，17.

[3]李海芳，王喜聰，陳俊杰.Snort下模式串匹配算法的研究與改進[J].太原理工大學(xué)學(xué)報，2010，03.

[基金項目]吉林省教育廳“十二五”科學(xué)技術(shù)研究基金資助項目（吉教科合字[2012]第371號）。