多模式串匹配之AC自動機算法

1、多模式串匹配之AC自動機算法（Aho-Corasick算法）簡介與C語言程序?qū)崿F(xiàn)源碼參考· 任俠 發(fā)布于 2011-03-22  22:27:53  一、概述AC自動機算法全稱Aho-Corasick算法，是一種字符串多模式匹配算法。該算法在1975年產(chǎn)生于貝爾實驗室，是著名的多模匹配算法之一。AC算法用于在一段文本中查找多個模式字符串，即給你很多字符串，再給你一段文本，讓你在文本中找這些串是否出現(xiàn)過，出現(xiàn)過多少次，分別在哪里出現(xiàn)。該算法應用有限自動機巧妙地將字符比較轉(zhuǎn)化為了狀態(tài)轉(zhuǎn)移。此算法有兩個特點，一個是掃描文本時完全不需要回溯，另一個是時間復雜度為

2、O(n)，時間復雜度與關鍵字的數(shù)目和長度無關，但所需時間和文本長度以及所有關鍵字的總長度成正比。AC算法有三個主要步驟，一個是字典樹tire的構(gòu)造，一個是搜索路徑的確定（即構(gòu)造失敗指針），還有就是模式匹配過程。學習AC自動機算法之前，最好先熟悉KMP算法，因為KMP算法與字典樹tire的構(gòu)造很是類似。KMP算法是一種經(jīng)典的單字符串匹配算法。二、AC算法思想 AC算法思想：用多模式串建立一個確定性的樹形有限狀態(tài)機，以主串作為該有限狀態(tài)機的輸入，使狀態(tài)機進行狀態(tài)的轉(zhuǎn)換，當?shù)竭_某些特定的狀態(tài)時，說明發(fā)生模式匹配。下圖是多模式he/ she/ his /hers構(gòu)成的一個確定性有限狀態(tài)機，做

3、幾點說明：圖2.11、 該狀態(tài)機優(yōu)先按照實線標注的狀態(tài)轉(zhuǎn)換路徑進行轉(zhuǎn)換，當所有實線標注的狀態(tài)轉(zhuǎn)換路徑條件不能滿足時，按照虛線的狀態(tài)轉(zhuǎn)換路徑進行狀態(tài)轉(zhuǎn)換。如：狀態(tài)0時，當輸入h，則轉(zhuǎn)換到狀態(tài)1；輸入s，則轉(zhuǎn)換到狀態(tài)3；否則轉(zhuǎn)換到狀態(tài)0。2、 匹配過程如下：從狀態(tài)0開始進行狀態(tài)轉(zhuǎn)換，主串作為輸入。如主串為：ushers，狀態(tài)轉(zhuǎn)換的過程是這樣的：圖2.23、 當狀態(tài)轉(zhuǎn)移到2，5，7，9等紅色狀態(tài)點時，說明發(fā)生了模式匹配。如主串為：ushers，則在狀態(tài)5、2、9等狀態(tài)時發(fā)生模式匹配，匹配的模 式串有she、he、hers。定義：在預處理階段，AC自動機算法建立了三個函數(shù)，轉(zhuǎn)向函數(shù)goto，

4、失效函數(shù)failure和輸出函數(shù)output，由此構(gòu)造了一個樹型有限自動機。轉(zhuǎn)向函數(shù)，指的是一種狀態(tài)之間的轉(zhuǎn)向關系。g(pre, x)=next：狀態(tài)pre在輸入一個字符x后轉(zhuǎn)換為狀態(tài)next（上圖中的實線部分）。如果在模式串中不存在這樣的轉(zhuǎn)換，則next=failstate。失效函數(shù)，指的也是狀態(tài)和狀態(tài)之間一種轉(zhuǎn)向關系。f(per)=next：是在比較失配的情況下使用的轉(zhuǎn)換關系。在構(gòu)造轉(zhuǎn)向函數(shù)時，把不存在的轉(zhuǎn)換用failstate表示，但是failstate不是一個具體的狀態(tài)，狀態(tài)機轉(zhuǎn)換轉(zhuǎn)換到failstate狀態(tài)的時候就不知道該往哪轉(zhuǎn)了。所以就要在狀態(tài)機中找到一個有意義的狀態(tài)代替fails

5、tate，當出現(xiàn)failstate狀態(tài)時，自動切換到那個狀態(tài)。這個狀態(tài)節(jié)點應該具有這樣的特征：從這個狀態(tài)節(jié)點向上直到樹根節(jié)點（狀態(tài)0）所經(jīng)歷的輸入字符，和從產(chǎn)生failstate狀態(tài)的那個狀態(tài)節(jié)點向上所經(jīng)歷的輸入字符串完全相同。而且這個狀態(tài)節(jié)點，是所有具備這些條件的節(jié)點中深度最大的那個節(jié)點。如果不存在滿足條件的狀態(tài)節(jié)點，則失效函數(shù)為0。累死了。舉例子說吧，對狀態(tài)9輸入任何一個字符都會產(chǎn)生failstate狀態(tài)，需要失效函數(shù)。狀態(tài)3向上到狀態(tài)0經(jīng)過的輸入字符串為s；而由狀態(tài)9向上的輸入字符串為sreh。字符串s相同，并且狀態(tài)3是滿足此條件的唯一節(jié)點，則f(9)=3。說來說去，失效函數(shù)就是要干這么

6、件事兒：圖2.3意思就是說，在比較模式串1發(fā)生失配時，找一個模式串2，使得P20.j-1 = P1i-j+1.i。然后繼續(xù)比較模式串2?？瓷厦婺莻€圖，想起點兒什么東西沒有？對了，是KMP算法。有人說AC算法就是KMP算法在多模式匹配情況下的擴展。輸出函數(shù)，指的是狀態(tài)和模式串之間的一種關系。output(i)=P，表示當狀態(tài)機到達狀態(tài)i時，模式串集合P中的所有模式串可能已經(jīng)完成匹配。 例：模式串為：he/ she/ hers/ his 時，如圖2.4所示。轉(zhuǎn)向函數(shù)：圖2.4失效函數(shù)：圖2.5輸出函數(shù)：圖2.6 三、字典樹tire的構(gòu)造這個比較好理解，就是把要匹配的一些字符串添

7、加到樹結(jié)構(gòu)中去。樹邊就是單詞中的字符，單詞中最后一個字符的連接節(jié)點添加標志，以表示改節(jié)點路徑包含1個字典中的字符串，搜索到此節(jié)點就表示找到了字典中的某個單詞，可以直接輸出。Trie是一個樹形結(jié)構(gòu)的狀態(tài)裝換圖，從一個結(jié)點到它的各個子結(jié)點的邊上有不同的標號。Trie的葉子結(jié)點表示識別到的關鍵字。當我們的模式串在Tire上進行匹配時，如果與當前節(jié)點的關鍵字不能繼續(xù)匹配的時候，就應該去當前節(jié)點的失敗指針所指向的節(jié)點繼續(xù)進行匹配。例子：某字典P=he,she,his,hers對應的字典樹如下圖：圖3.1圖中有數(shù)字的節(jié)點到根節(jié)點的路勁正好對應字典中的字符串，數(shù)字表述單詞在字典中的順序，也可以是其他標志。四

8、、搜索路徑的確定我的理解是：利用后綴字符串來確定。后綴字符串就是某個字符串的后面的一部分。比如abcde的后綴字符串有bcde,cde,de和e。假定目標字符串為ushers，字典為上圖（圖1）所示。搜索過程目標字符串指針指向的字符和字典中的字符會有以下幾種情況：a. 當前字符匹配。表示從當前節(jié)點沿著樹邊有一條路徑可以到達目標字符，此時只需沿該路徑走向下一個節(jié)點繼續(xù)匹配即可，目標字符串指針移向下個字符繼續(xù)匹配；如：當指針指到s處，此時字典樹指針處于根，要從根到s處，可以看到圖中有一條從根經(jīng)s連接到的節(jié)點，因此字典樹節(jié)點指針指向此節(jié)點，目標字符串指針移動到下一字符h繼續(xù)匹配；顯然當前節(jié)點有一條經(jīng)

9、h連接到的節(jié)點，于是重復操作到有數(shù)字標志的節(jié)點2處，表示已找到，該匹配字符串就是"she"，輸出該字符串的位置后，目標字符串指針增1指向"r"，字典指針指向數(shù)字2節(jié)點，進行下次匹配。b. 當前字符無匹配。表示當前節(jié)點的任何一條邊都無法達到要匹配的字符，此時不能沿現(xiàn)有路徑前進，只能回溯，回溯到存在的最長的后綴字符串處，如果沒有任何后綴字符串匹配則回溯到樹根處。然后從當前回溯節(jié)點判斷是否可以到達目標字符串字符。如：接上，由于數(shù)字2節(jié)點無經(jīng)"r"的連接，因此回溯，she的后綴字符串he在字典樹中，因此字典樹指針指向帶有數(shù)字1的標志節(jié)點，由于

10、帶有標志，直接輸出該節(jié)點"HE"(存疑，很多文章沒有提到此處需要輸出，正常路徑移動的字典指針節(jié)點要判斷是否可以輸出，那么由回溯路徑改變的字典指針指向的節(jié)點要不要判斷是否輸出？)，然后從數(shù)字1節(jié)點判斷是否有經(jīng)"r"到下一節(jié)點的路徑，顯然圖中有。因此字典樹節(jié)點指向下一節(jié)點，重復以上操作，最后找到"hers"，此時匹配搜索也結(jié)束了。以上兩種情況直到目標字符串指針直到末尾結(jié)束匹配。在匹配過程中遇到有標志的節(jié)點說明找到了字典中的某個詞，可以直接輸出。 輸出說明：每次目標串指針移動前都需要判斷當前節(jié)點是否可以輸出，并遞歸的判斷當前節(jié)點回

11、溯路徑上的節(jié)點是否可以輸出（其實就是判斷所有后綴字符串，she匹配時，其后綴he也會匹配，即使she不匹配，其后綴he也可能匹配，因此需遞歸判斷后綴字符串），直到樹根結(jié)束遞歸。由于固定字典的字符串的后綴字符串都是已知的，因此可以在字典樹結(jié)構(gòu)中存儲匹配失敗的路徑方向，因此只要字典樹構(gòu)造完畢，就可以根據(jù)字典樹的路徑進行匹配了，效率非?？?。以上就是我對該算法的全部過程的理解，疏漏之處在所難免。附錄：附1：含匹配失敗的情況的路徑選擇的字典樹，實線表示匹配成功的正常路徑，虛線表示失敗的回溯路徑圖 附1.1附2：AC算法的偽代碼實現(xiàn)描述T為目標字符串，長度為m，q為字典樹的節(jié)點指針，g函數(shù)返回從節(jié)點q經(jīng)過

12、路徑Ti到達的下一節(jié)點指針，f函數(shù)返回節(jié)點q的回溯節(jié)點指針。flag判斷節(jié)點是否為標志節(jié)點q := 0; / initial state (root)for i := 1 to m do    while g(q,Ti) = NULL do        q := f(q); / 回溯    q := g(q,Ti); / 前進    node:=q;    while(node!=root)&#

13、160;       if flag(node) exist ; then print i, out(node);        node = f(node);   /查找回溯節(jié)點    end for;   附3：一個簡單的AC算法實現(xiàn)源碼示例參考： /*程序說明：多模式串匹配的AC自動機算法自動機算法可以參考柔性字符串匹配里的相應章節(jié)，講的很清楚*/#include <

14、;stdio.h>#include <string.h>  const int MAXQ = 500000+10;const int MAXN = 1000000+10;const int MAXK = 26; /自動機里字符集的大小struct TrieNode       TrieNode* fail;       TrieNode* nextMAXK;  

15、0;    bool danger;   /該節(jié)點是否為某模式串的終結(jié)點       int cnt;    /以該節(jié)點為終結(jié)點的模式串個數(shù)       TrieNode()                   

16、;  fail = NULL;              memset(next, NULL, sizeof(next);              danger = false;            

17、60; cnt = 0;       *queMAXQ, *root;/文本字符串char msgMAXN;int   N;void TrieInsert(char *s)       int i = 0;       TrieNode *ptr = root;       while(si) &#

18、160;                   int idx = si-'a'              if(ptr->nextidx = NULL)         

19、0;           ptr->nextidx = new TrieNode();              ptr = ptr->nextidx;              i+;   

20、60;          ptr->danger = true;       ptr->cnt+; void Init()       int i;       char s100;       root = new TrieN

21、ode();       scanf("%d", &N);       for(i = 0; i < N; i+)                     scanf("%s", s);    &

22、#160;         TrieInsert(s);        void Build_AC_Automation()       int rear = 1, front = 0, i;       que0 = root;       roo

23、t->fail = NULL;       while(rear != front)                     TrieNode *cur = quefront+;              for(

24、i = 0; i < 26; i+)                     if(cur->nexti != NULL)                       

25、                          if(cur = root)                      

26、60;            cur->nexti->fail = root;                            else     

27、60;                                                  &#

28、160;      TrieNode *ptr = cur->fail;                                   while(ptr != NULL)  &

29、#160;                                                  

30、                        if(ptr->nexti != NULL)                      

31、0;                                                  

32、60;                 cur->nexti->fail = ptr->nexti;                           

33、;                      if(ptr->nexti->danger = true)                       

34、;                                 cur->nexti->danger = true;            &#

35、160;                                    break;             &

36、#160;                                                  

37、                    ptr = ptr->fail;                           

38、0;                                          if(ptr = NULL) cur->nexti->fail = root;  

39、;                                                  

40、0;   querear+ = cur->nexti;                            int AC_Search()       int i = 0, ans = 0;   

41、60;   TrieNode *ptr = root;       while(msgi)                     int idx = msgi-'a'           &#

42、160;  while(ptr->nextidx = NULL && ptr != root) ptr = ptr->fail;              ptr = ptr->nextidx;              if(ptr = NULL) ptr = root;              TrieNode *tmp = ptr;              while(tmp != NULL && tmp->cnt != -1)