Aho-Corasick automaton
- 2020 年 4 月 8 日
- 筆記
在談 AC 自動機之前，我們需要學習一些預備知識，請你先詳細閱讀本博客的前兩部分。
KMP 算法
BF 算法
BF算法，即暴風(Brute Force)算法，是普通的模式匹配算法，不是要匹配字符嗎？那我一個一個直接匹配不就好啦。BF算法的思想就是將目標串 S 的第一個字符與模式串 T 的第一個字符進行匹配，若相等，則繼續比較 S 的第二個字符和 T 的第二個字符；若不相等，則比較S的第二個字符和T的第一個字符，依次比較下去，直到得出最後的匹配結果。
代碼實現：
#include <string.h> int BF(const char* str, const char* sub, int pos)//O(n*m) { int i = pos; int j = 0; while (i < strlen(str) && j < strlen(sub)) { if (str[i] == sub[j]) //同時移動 i 和 j { i++; j++; } else { i = i - j + 1; //i 退回到當前匹配失敗的字符串第一個字符的下一個 j = 0; //j 回退到 0，即回溯 } } if (j >= strlen(sub)) //匹配 return i - j; else //失配 return -1; } KMP 算法
避免重複遍歷
假設我們的目標串是 「abcdefgab……」，模式串是 「abcde&」，那麼使用 BF 算法匹配流程如下所示。
但是在模式串中，第一個字符 「a」 與後面的字符 「bcde&」 都不一樣，也就是說對於第一步，前 5 位字符都匹配成功了，那麼 「a」 與目標串中的第 2~5 個字符一定不能匹配，那麼流程就可以縮減成這樣：
再看個例子，假設我們的目標串是 「abcababca……」，模式串是 「abcab&」，那麼使用 BF 算法匹配流程如下所示。
因為模式串中的第一位和第四位的字符都是 「a」，第二位和第五位字符都是 「b」，而第四位和第五位在第一步的時候已經匹配成功了，因此匹配的過程可以簡化為：
那麼這種思想就是 KMP 算法，這種算法的思想是為了讓不必要的回溯不發生。
算法思想
KMP 算法是一種改進的字符串匹配算法，由 D.E.Knuth，J.H.Morris 和 V.R.Pratt 提出的，因此人們稱它為克努特—莫里斯—普拉特操作（簡稱 KMP 算法）。KMP算法的核心是利用匹配失敗後的信息，盡量減少模式串與主串的匹配次數以達到快速匹配的目的。具體實現就是通過一個 next() 函數實現，函數本身包含了模式串的局部匹配信息。KMP 算法的時間複雜度 O(m+n)。
代碼實現
匹配函數
int KMP(string str, string t, int pos) { int i = pos; //從字符串的 pos 下標開始匹配 int j = 0; //用於描述模式串 t 的下標 int next[t.size()]; getNext(t, next); while (i <= str.size() && i <= t.size()) { if (j == -1 || str[i] == t[j]) //兩字符相等，繼續判斷 { i++; j++; } else //不相等，回溯 { j = next[j]; } } if (j > t.size()) return i - t.size; else return -1; } 求 next 數組
void getNext(string t,int next[]) { int i = 0,j = -1; next[0] = -1; while(i < t.size()) { if(j == -1 || t[i] == t[j]) //匹配前綴和後綴 { i++; j++; next[i] = j; } else j = next[j]; //字符不相同，回溯 } } 如果你不是很懂 KMP 算法具體是怎麼實現的也沒關係，先理解算法的思想即可。
字典樹
左轉我的另一篇博客字典樹 (Trie)
多模匹配
AC 自動機(Aho-Corasick automaton)算法在 1975 年產生於貝爾實驗室，是著名的多模匹配算法，時間複雜度為 O(n)，n 為文本串長度。那麼啥是多模匹配算法嘞？相信你已經理解了 KMP 算法的思想，KMP 算法是一種單模匹配算法，即一段模式串匹配一段字符串。所謂多模匹配算法就是多段模式串匹配一段字符串，例如給出 n 個單詞，再給出一段包含 m 個字符的英文文章，讓你利用算法找出有多少個單詞在文章里出現過，這就是一個多模匹配的過程。
那麼問題來了，我們可以連續使用 KMP 算法 n 次，每次匹配一個模式串，這樣也可以實現多模匹配，但是這麼做時間複雜度無疑是很大的，特別是當模式串很多，英文文章很長的情況下，那匹配的次數就太多次啦。作為一個懶人，我們總是很喜歡搞點手法，讓我們能夠在儘可能少的次數中完成多模式匹配啦，最理想的情況是一次匹配就完成任務。
那麼問題來了，想要一次匹配成功，也就是說需要一次匹配所有模式串，難道我們需要一個字符分別拿每個模式串上去匹配嗎？要不直接開個多線程好了(笑)，這顯然不是很好的想法。我們的目標是，用一種結構將所有模式串組織起來，然後匹配時就拿組織好的這一個結構進去匹配嘍！盲猜一下，我們用什麼結構去組織，對於單模匹配，我們使用的是順序表，字符之間是一對一的關係，既然要組織多個模式串，應該是要用一對多的結構去組織吧(還不需要把圖結構祭出來啊)。
構造字典樹
你說巧不巧，我們剛學習了字典樹，字典樹就是一種用於組織多個字符串的樹結構啊。例如有 "a","apple","appeal","appear","bee","beef","cat" 7 個模式串，就能夠組織成如圖所示字典樹，就把一個所有模式串都組織到一個結構中啦。
字典樹的結構體定義
typedef struct Node { Node* next[26]; //結點的後繼，最多有 26 個 Node* fail; //失配指針 bool flag; //判斷單詞結尾的 flag }Node, * Trie; 構造算法
其實就是字典樹的插入算法啦，不過我們還有個還沒介紹的失配指針需要初始化，所以要稍微改裝一下。這裡和我的另一篇博客的不同在於，這裡使用了鏈式存儲，不過思想是一樣的。
偽代碼
代碼實現
void buildTrie(Trie root, string a_word) //建 Trie { Trie pre = root; Trie ptr; int order; for (int i = 0; i < a_word.size(); i++) { order = a_word[i] - 'a'; //獲取字母在字母表中的順序 if (pre->next[order] == NULL) //字母序對應的後繼不存在 { ptr = new Node; //初始化新結點 for (int j = 0; j < 26; j++) ptr->next[j] = NULL; ptr->fail = NULL; ptr->flag = false; pre->next[order] = ptr; //插入新結點 } pre = pre->next[order]; //以新節點作為下一次循環的根結點 } pre->flag = true; //修改 flag 表示為單詞結尾 } 接下來就是解決如何匹配的問題了，還記得我們是怎麼在單模匹配中減少不必要的匹配的嗎？使用** KMP 算法**，通過 KMP 算法的 next 數組，使得每次失配之後可以直接回溯到不重複的位置繼續匹配，就不需要移動被匹配的字符串了。在這種思想的引導下，我們需要解決的是，找到一種算法，能夠幫助我們在一個樹結構中準確地找到適當的回溯位置，即可避免不必要的匹配了。
失配指針
功能解析
我們的目的是，希望在匹配多個模式串時不發生不必要的回溯，實現類似於 KMP 算法的機制，在匹配一個模式串時發生失配，能夠從該字符自動跳轉到另一段模式串，目標模式串時從根結點開始具有與失配的模式串的某個後綴字符串完全相同的前綴字符串。這種機制在 AC 自動機中被稱為失配指針，失配指針是 AC 自動機算法的核心。
失配指針的原理是，如果文本與某一個模式串失配失配，則說明文本自上一個單詞到此為止，中間不存在任何單詞。此時若模式串中的任何後綴字符串都不為其他模式串的前綴字符串，則失配結點處的失配指針指向 root，表示下一輪匹配回溯至根結點。若當前模式串具有與某一模式串的前綴字符串相同的後綴字符串，就通過失配指針進行模式串的跳躍，使得匹配不需要回溯。我們通過一個例子來理解一下：
如圖是用 5 個模式串：**"she","he","say","shr","her" **所建的字典樹，通過分析可知，"she" 具有後綴字符串 "he"，"her" 具有前綴字符串，因此當 "she" 模式串發生失配的時候，就可以通過失配指針繼續匹配 "her" 模式串，那麼就需要將 "she" 中的 "h" 結點的失配指針指向 "her" 的 "h" 結點，將 "she" 中的 "e" 結點的失配指針指向 "her" 的 "e" 結點。至於其他的結點，由於不存在共有的前綴字符串和後綴字符串，因此它們的失配指針指向根結點。因此對於如圖字典樹，失配指針的關係如圖所示：
構造方法
通過分析可以得知，進行跳轉的另一個模式串的結點深度一定小於跳轉之前的結點的深度，這是因為若跳轉後的結點深度小於原結點的深度，就無法保證跳轉後模式串的前綴字符串與進行跳轉的模式串的後綴字符串相匹配，這樣結點數量完全不夠。
例如上文的例子中，通過失配指針聯繫的 "she" 中的 "h" 結點和 "her" 的 "h" 結點(藍色標出)中前者的層數大於後者， "she" 中的 "e" 結點和 "her" 的 "e" 結點(紫色標出)中前者的層數也大於後者：
根據這個特點，我們可以通過訪問當前結點的雙親結點的方式進行試探，對於某一個字母結點(原字母)，通過對其雙親的失配指針的訪問，尋找到其他的結點，這個結點滿足其孩子結點中存在與原字母相同的結點，此時就把原字母結點的失配指針指向尋找到的結點中與原字母相同的孩子結點。若訪問到了根結點，沒有發現符合要求的結點，則失配指針指向根結點。
為什麼這麼做可行？因為我們組織模式串使用了字典樹，如果失配指針指向的是同一層的結點，顯然指向的結點肯定不是當前模式串的後綴字符串的一部分，也就是說如果是同層的話，這兩個結點會重合，即為同一個結點，這也就是字典樹構造時會將所有單詞中相同前綴的前綴字符串用相同的結點來描述的特點。因此所有失配指針指向的結點不可能是另一個與自己深度相同的節點，通過失配指針訪問時只能訪問比當前深度小的結點。通過結點的雙親來探測失配指針的指向，就可以保證通過失配指針訪問的位置的模式串長度小於當前被匹配的模式串。
例如對於 "she" 中的 "h" 結點，其雙親是 "s" 結點，"s" 結點的失配指針指向根結點，而根節點具有與 "h" 結點相同的孩子結點，因此就可以利用失配指針構成聯繫：
那麼我們使用什麼樣的算法來實現這個過程？因為我們需要訪問某個結點的雙親的失配指針，因此就需要保證雙親的失配指針有意義，而對於第一層結點而言，其雙親是根結點無需操作。因此對於失配指針的設置具體要保證層數在上層的結點先構造失配指針，下層的結點後構造失配指針。你有什麼想法？你有沒有感覺這個過程和我們做隊列實現迷宮尋路和二叉樹的層序遍歷一模一樣啊！都是從內層到外層一層一層探測，因此我們就明白了，我們需要使用廣度優先搜索的思想來進行構造，因此就需要一個隊列，先把根結點加入隊列，並設置其的失配指針指向自己或者 NULL，之後每構造一個結點的失配指針，就連帶將其子結點入隊列。
偽代碼
代碼實現
void disposeFail(Trie root) //配置失配指針 { queue<Trie> que; Trie ptr; Trie pre; que.push(root); //根結點入隊列 while (!que.empty()) { pre = que.front(); que.pop(); //隊列頭出隊列 ptr = NULL; for (int i = 0; i < 26; i++) { if (pre->next[i] != NULL) //挖掘存在的後繼 { if (pre == root) //pre 和 root 處在同一層，失配指針為 root { pre->next[i]->fail = root; } else { ptr = pre->fail; //ptr 為其的雙親的失配指針 while (ptr != NULL) { if (ptr->next[i] != NULL) //將該結點的失配指針指向該 next[i] 結點 { pre->next[i]->fail = ptr->next[i]; break; } ptr = ptr->fail; //回溯該結點的雙親的失配指針，直到該結點的 next[i] 與之相同 } if (ptr == NULL) //若回溯到 root，則失配指針指向 root pre->next[i]->fail = root; } que.push(pre->next[i]); //該結點的所有子結點入隊列 } } } } 匹配算法
功能解析
其實我們會發現，AC 自動機算法只要你理解了失配指針的構建，接下的匹配過程就比較好理解了。對於文本的一個字符，匹配過程中只會有 2 種情況：
- 當前字符匹配，此時將文本移動到下個字符，字典樹繼續向下挖掘結點繼續匹配；
- 當前字符不匹配，則訪問當前結點的失配指針所指向的模式串，若失配指針指向根結點表示到此為止沒有可匹配的字符，文本移動到下一個字符開始下一輪匹配。
偽代碼
代碼實現
int matchMultiPattern(Trie root, string str) { int order; int count = 0; Trie pre = root; Trie ptr; for (int i = 0; i < str.size(); i++) { order = str[i] - 'a'; while (pre->next[order] == NULL && pre != root) { //若根結點沒有該字母的後繼，通過失配指針挖掘，判斷 str[i] 是否需要與模式串匹配 pre = pre->fail; } pre = pre->next[order]; //找到對應的模式串頭，用 pre 指向 if (pre == NULL) //沒有找到與之匹配的字符 { pre = root; //pre 回到根結點 continue; //開啟下一輪判斷 } ptr = pre; //匹配該結點後，沿其失敗指針回溯，判斷其它結點是否匹配 while (ptr != root) //ptr 回到根結點，則匹配結束 { if (ptr->flag == true) //判斷當前單詞是否匹配過了 { count++; //沒匹配過，統計 ptr->flag = false; //修改 flag 為 false，表示該單詞被匹配過了 } else //結點已訪問，退出循環 { break; } ptr = ptr->fail; //回溯失配指針，挖掘下一個需要匹配的結點 } } return count; } 算法小結
算法實現步驟
- 根據模式串構造字典樹；
- 根據字典樹構造每個結點的失配指針；
- 根據失配指針進行文本匹配。
應用情景
情景需要實現的是輸入匹配的次數，然後輸入被匹配的單詞數 n，然後依次讀入 n 個單詞，接着輸入文本，編程實現對文本中出現過的被匹配單詞的數量統計。
代碼實現
將上述的代碼封裝好，然後寫一個主函數來組織 AC 自動機的運行即可，這裡簡化一下操作，只進行一次匹配。
調試效果
參考資料
BF算法
史上最簡(詳細)KMP算法講解，看不懂算我輸！
AC自動機
ac自動機最詳細的講解，讓你一次學會ac自動機
AC自動機講解超詳細
AC自動機 算法詳解(圖解)及模板
AC自動機算法詳解(轉載)
AC自動機算法及模板
hdu 2222 AC自動機(可做模板)
AC自動機詳解
