?

AC自動機算法及模板

2016-05-08 18:58?226人閱讀?評論(0)?收藏?舉報 ?分類： AC自動機（1）?

版權(quán)聲明：本文為博主原創(chuàng)文章，未經(jīng)博主允許不得轉(zhuǎn)載。

目錄(?)[+]

• 關(guān)于AC自動機

1. AC自動機：Aho-Corasickautomation，該算法在1975年產(chǎn)生于貝爾實驗室，是著名的多模匹配算法之一。一個常見的例子就是給出n個單詞，再給出一段包含m個字符的文章，讓你找出有多少個單詞在文章里出現(xiàn)過。要搞懂AC自動機，先得有模式樹（字典樹）Trie和KMP模式匹配算法的基礎(chǔ)知識。AC自動機算法分為3步：構(gòu)造一棵Trie樹，構(gòu)造失敗指針和模式匹配過程。
2. 簡單來說，AC自動機是用來進行多模式匹配（單個主串，多個模式串）的高效算法。

• AC自動機的構(gòu)造過程

使用Aho-Corasick算法需要三步：

1. 建立模式串的Trie
2. 給Trie添加失敗路徑
3. 根據(jù)AC自動機，搜索待處理的文本

我們以下面這個例子來介紹AC自動機的運作過程

這里以?hdu 2222 KeywordsSearch?這一道題最為例子進行講解，其中測試數(shù)據(jù)如下：

給定5個單詞：say she shr he her，然后給定一個字符串? yasherhs。問一共有多少單詞在這個字符串中出現(xiàn)過。

• 確定數(shù)據(jù)結(jié)構(gòu)

首先，我們需要確定AC自動機所需的數(shù)據(jù)存儲結(jié)構(gòu)，它們的用處之后會講到。
[plain]?view plaincopy

1. struct?Node??
2. {??
3. ????int?cnt;//是否為該單詞的最后一個結(jié)點???
4. ????Node?*fail;//失敗指針???
5. ????Node?*next[26];//Trie中每個結(jié)點的各個節(jié)點???
6. }*queue[500005];//隊列，方便用BFS構(gòu)造失敗指針???
7. char?s[1000005];//主字符串???
8. char?keyword[55];//需要查找的單詞???
9. int?head,tail;??
10. Node?*root;//頭結(jié)點???

第一步：構(gòu)建Trie

根據(jù)輸入的 keyword 一 一 構(gòu)建在Trie樹中

[plain]?view plaincopy

1. void?Build_trie(char?*keyword)//構(gòu)建Trie樹???
2. {??
3. ????Node?*p,*q;??
4. ????int?i,v;??
5. ????int?len=strlen(keyword);??
6. ????for(i=0,p=root;i<len;i++)??
7. ????{??
8. ????????v=keyword[i]-'a';??
9. ????????if(p->next[v]==NULL)??
10. ????????{??
11. ????????????q=(struct?Node?*)malloc(sizeof(Node));??
12. ????????????Init(q);??
13. ????????????p->next[v]=q;//結(jié)點鏈接???
14. ????????}??
15. ????????p=p->next[v];//指針移動到下一個結(jié)點???
16. ????}??
17. ????p->cnt++;//單詞最后一個結(jié)點cnt++，代表一個單詞???
18. }??

構(gòu)建完成后的效果如下圖：

• 構(gòu)建失敗指針

• 構(gòu)建失敗指針是AC自動機的關(guān)鍵所在，可以說，若沒有失敗指針，所謂的AC自動機只不過是Trie樹而已。

• 失敗指針原理：

• 構(gòu)建失敗指針，使當前字符失配時跳轉(zhuǎn)到另一段從root開始每一個字符都與當前已匹配字符段某一個后綴完全相同且長度最大的位置繼續(xù)匹配，如同KMP算法一樣，AC自動機在匹配時如果當前字符串匹配失敗，那么利用失配指針進行跳轉(zhuǎn)。由此可知如果跳轉(zhuǎn)，跳轉(zhuǎn)后的串的前綴必為跳轉(zhuǎn)前的模式串的后綴，并且跳轉(zhuǎn)的新位置的深度（匹配字符個數(shù)）一定小于跳之前的節(jié)點（跳轉(zhuǎn)后匹配字符數(shù)不可能大于跳轉(zhuǎn)前，否則無法保證跳轉(zhuǎn)后的序列的前綴與跳轉(zhuǎn)前的序列的后綴匹配）。所以可以利用BFS在Trie上進行失敗指針求解。

• 失敗指針利用：

• 如果當前指針在某一字符s[m+1]處失配，即(p->next[s[m+1]]==NULL)，則說明沒有單詞s[1...m+1]存在，此時，如果當前指針的失配指針指向root，則說明當前序列的任何后綴不是是某個單詞的前綴，如果指針的失配指針不指向root，則說明當前序列s[i...m]是某一單詞的前綴，于是跳轉(zhuǎn)到當前指針的失配指針，以s[i...m]為前綴繼續(xù)匹配s[m+1]。

• 對于已經(jīng)得到的序列s[1...m]，由于s[i...m]可能是某單詞的后綴，s[1...j]可能是某單詞的前綴，所以s[1...m]中可能會出現(xiàn)單詞，但是當前指針的位置是確定的，不能移動，我們就需要temp臨時指針，令temp=當前指針，然后依次測試s[1...m],s[i...m]是否是單詞。

• >>>簡單來說，失敗指針的作用就是將主串某一位之前的所有可以與模式串匹配的單詞快速在Trie樹中找出。

第二步：構(gòu)建失敗指針

1. 在構(gòu)造完Tire樹之后，接下去的工作就是構(gòu)造失敗指針。構(gòu)造失敗指針的過程概括起來就一句話：設(shè)這個節(jié)點上的字母為C，沿著它父親節(jié)點的失敗指針走，直到走到一個節(jié)點，它的子結(jié)點中也有字母為C的節(jié)點。然后把當前節(jié)點的失敗指針指向那個字母也為C的兒子。如果一直走到了root都沒找到，那就把失敗指針指向root。具體操作起來只需要：先把root加入隊列(root的失敗指針指向自己或者NULL)，這以后我們每處理一個點，就把它的所有兒子加入隊列。
2. 觀察構(gòu)造失敗指針的流程：對照圖來看，首先root的fail指針指向NULL，然后root入隊，進入循環(huán)。從隊列中彈出root，root節(jié)點與s,h節(jié)點相連，因為它們是第一層的字符，肯定沒有比它層數(shù)更小的共同前后綴，所以把這2個節(jié)點的失敗指針指向root，并且先后進入隊列，失敗指針的指向?qū)?yīng)圖中的(1)，(2)兩條虛線；從隊列中先彈出h(右邊那個)，h所連的只有e結(jié)點，所以接下來掃描指針指向e節(jié)點的父節(jié)點h節(jié)點的fail指針指向的節(jié)點，也就是root，root->next['e']==NULL,并且root->fail==NULL,說明匹配序列為空，則把節(jié)點e的fail指針指向root,對應(yīng)圖中的(3),然后節(jié)點e進入隊列；從隊列中彈出s，s節(jié)點與a,h(左邊那個)相連，先遍歷到a節(jié)點，掃描指針指向a節(jié)點的父節(jié)點s節(jié)點的fail指針指向的節(jié)點，也就是root，root->next['a']==NULL,并且root->fail==NULL,說明匹配序列為空,則把節(jié)點a的fail指針指向root,對應(yīng)圖中的(4),然后節(jié)點a進入隊列。接著遍歷到h節(jié)點，掃描指針指向h節(jié)點的父節(jié)點s節(jié)點的fail指針指向的節(jié)點，也就是root，root->next['h']!=NULL,所以把節(jié)點h的fail指針指向右邊那個h,對應(yīng)圖中的(5),然后節(jié)點h進入隊列...由此類推，最終失配指針如圖所示。
   

構(gòu)建失敗指針的代碼：
[plain]?view plaincopy

1. void?Build_AC_automation(Node?*root)??
2. {??
3. ????head=0,tail=0;//隊列頭、尾指針???
4. ????queue[head++]=root;//先將root入隊???
5. ????while(head!=tail)??
6. ????{??
7. ????????Node?*p=NULL;??
8. ????????Node?*temp=queue[tail++];//彈出隊頭結(jié)點???
9. ????????for(int?i=0;i<26;i++)??
10. ????????{??
11. ????????????if(temp->next[i]!=NULL)//找到實際存在的字符結(jié)點???
12. ????????????{?//temp->next[i]?為該結(jié)點，temp為其父結(jié)點???
13. ????????????????if(temp==root)//若是第一層中的字符結(jié)點，則把該結(jié)點的失敗指針指向root???
14. ????????????????????temp->next[i]->fail=root;??
15. ????????????????else??
16. ????????????????{??
17. ????????????????????//依次回溯該節(jié)點的父節(jié)點的失敗指針直到某節(jié)點的next[i]與該節(jié)點相同，??
18. ????????????????????//則把該節(jié)點的失敗指針指向該next[i]節(jié)點；???
19. ????????????????????//若回溯到?root?都沒有找到，則該節(jié)點的失敗指針指向?root??
20. ????????????????????p=temp->fail;//將該結(jié)點的父結(jié)點的失敗指針給p???
21. ????????????????????while(p!=NULL)??
22. ????????????????????{??
23. ????????????????????????if(p->next[i]!=NULL)??
24. ????????????????????????{??
25. ????????????????????????????temp->next[i]->fail=p->next[i];??
26. ????????????????????????????break;??
27. ????????????????????????}??
28. ????????????????????????p=p->fail;??
29. ????????????????????}??
30. ????????????????????//讓該結(jié)點的失敗指針也指向root???
31. ????????????????????if(p==NULL)??
32. ????????????????????????temp->next[i]->fail=root;??
33. ????????????????}??
34. ????????????????queue[head++]=temp->next[i];//每處理一個結(jié)點，都讓該結(jié)點的所有孩子依次入隊???
35. ????????????}??
36. ????????}??
37. ????}??
38. }??

• 為什么上述那個方法是可行的，是可以保證從root到所跳轉(zhuǎn)的位置的那一段字符串長度小于當前匹配到的字符串長度且與當前匹配到的字符串的某一個后綴完全相同且長度最大呢？

1. • 顯然我們在構(gòu)建失敗指針的時候都是從當前節(jié)點的父節(jié)點的失敗指針出發(fā)，由于Trie樹將所有單詞中相同前綴壓縮在了一起，所以所有失敗指針都不可能平級跳轉(zhuǎn)（到達另一個與自己深度相同的節(jié)點），因為如果平級跳轉(zhuǎn)，很顯然跳轉(zhuǎn)所到達的那個節(jié)點肯定不是當前匹配到的字符串的后綴的一部分，否則那兩個節(jié)點會合為一個，所以跳轉(zhuǎn)只能到達比當前深度小的節(jié)點，又因為是由當前節(jié)點父節(jié)點開始的跳轉(zhuǎn)，所以這樣就可以保證從root到所跳轉(zhuǎn)到位置的那一段字符串長度小于當前匹配到的字符串長度。另一方面，我們可以類比KMP求NEXT數(shù)組時求最大匹配數(shù)量的思想，那種思想在AC自動機中的體現(xiàn)就是當構(gòu)建失敗指針時不斷地回到之前的跳轉(zhuǎn)位置，然后判斷跳轉(zhuǎn)位置的下一個字符是否包含當前字符，如果是就將失敗指針與那個跳轉(zhuǎn)位置連接，如果跳轉(zhuǎn)位置指向NULL就說明當前匹配的字符在當前深度之前沒有出現(xiàn)過，無法與任何跳轉(zhuǎn)位置匹配，而若是找到了第一個跳轉(zhuǎn)位置的下一個字符包含當前字符的的跳轉(zhuǎn)位置，則必然取到了最大的長度，這是因為其余的當前正在匹配的字符必然在第一個跳轉(zhuǎn)位置的下一個字符包含當前字符的的跳轉(zhuǎn)位置深度之上，而那樣的跳轉(zhuǎn)位置就算可以，也不會是最大的（最后一個字符的深度比當前找到的第一個可行的跳轉(zhuǎn)位置的最后一個字符的深度小，串必然更短一些）。
   • 第三步：匹配 這樣就證明了這種方法構(gòu)建失敗指針的可行性。

第三步：匹配

1. 最后，我們便可以在AC自動機上查找模式串中出現(xiàn)過哪些單詞了。匹配過程分兩種情況：(1)當前字符匹配，表示從當前節(jié)點沿著樹邊有一條路徑可以到達目標字符，此時只需沿該路徑走向下一個節(jié)點繼續(xù)匹配即可，目標字符串指針移向下個字符繼續(xù)匹配；(2)當前字符不匹配，則去當前節(jié)點失敗指針所指向的字符繼續(xù)匹配，匹配過程隨著指針指向root結(jié)束。重復這2個過程中的任意一個，直到模式串走到結(jié)尾為止。
2. 對例子來說：其中模式串為yasherhs。對于i=0,1。Trie中沒有對應(yīng)的路徑，故不做任何操作；i=2,3,4時，指針p走到左下節(jié)點e。因為節(jié)點e的count信息為1，所以cnt+1，并且講節(jié)點e的count值設(shè)置為-1，表示改單詞已經(jīng)出現(xiàn)過了，防止重復計數(shù)，最后temp指向e節(jié)點的失敗指針所指向的節(jié)點繼續(xù)查找，以此類推，最后temp指向root，退出while循環(huán)，這個過程中count增加了2。表示找到了2個單詞she和he。當i=5時，程序進入第5行，p指向其失敗指針的節(jié)點，也就是右邊那個e節(jié)點，隨后在第6行指向r節(jié)點，r節(jié)點的count值為1，從而count+1，循環(huán)直到temp指向root為止。最后i=6,7時，找不到任何匹配，匹配過程結(jié)束。
3. AC自動機時間復雜性為：O(L(T)+max(L(Pi))+m)其中m是模式串的數(shù)量
   

匹配代碼：
[plain]?view plaincopy

1. int?query(Node?*root)??
2. {?//i為主串指針，p為模式串指針???
3. ????int?i,v,count=0;??
4. ????Node?*p=root;??
5. ????int?len=strlen(s);??
6. ????for(i=0;i<len;i++)??
7. ????{??
8. ????????v=s[i]-'a';??
9. ????????//由失敗指針回溯查找，判斷s[i]是否存在于Trie樹中???
10. ????????while(p->next[v]==NULL?&&?p!=root)??
11. ????????????p=p->fail;??
12. ????????p=p->next[v];//找到后p指針指向該結(jié)點???
13. ????????if(p==NULL)//若指針返回為空，則沒有找到與之匹配的字符???
14. ????????????p=root;??
15. ????????Node?*temp=p;//匹配該結(jié)點后，沿其失敗指針回溯，判斷其它結(jié)點是否匹配???
16. ????????while(temp!=root)//匹配結(jié)束控制???
17. ????????{??
18. ????????????if(temp->cnt>=0)//判斷該結(jié)點是否被訪問???
19. ????????????{??
20. ????????????????count+=temp->cnt;//由于cnt初始化為?0，所以只有cnt>0時才統(tǒng)計了單詞的個數(shù)???
21. ????????????????temp->cnt=-1;//標記已訪問過???
22. ????????????}??
23. ????????????else//結(jié)點已訪問，退出循環(huán)???
24. ????????????????break;??
25. ????????????temp=temp->fail;//回溯?失敗指針?繼續(xù)尋找下一個滿足條件的結(jié)點???
26. ????????}??
27. ????}??
28. ????return?count;??
29. }??

本例題的完整模板代碼請點擊查看博文：http://blog.csdn.net/liu940204/article/details/51345954
暫時的AC自動機的講解就這么愉快地結(jié)束了，未完待續(xù)......

總結(jié)

以上是生活随笔為你收集整理的AC自动机算法及模板的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。