<script type="text/javascript" src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.1/MathJax.js?config=TeX-AMS-MML_HTMLorMML"></script> # Aho Corasick Automata - AC自動機 -------- #### 問題 在文本$$ text $$中查找$$ k $$個模式$$ pattern $$出現的所有位置（其中$$ text $$長度為$$ n $$，$$ pattern_{i} $$的長度為$$ m_{i} $$，其中最長的模式長度為$$ m_{max} $$且$$ n \gt m_{max} $$，所有模式長度之和為$$ m_{sum} = \sum_{i=1}^{k} m_{i} $$，且所有模式中的$$ pattern $$沒有重復的字符串）。 #### 簡單字符串匹配算法 將簡單字符串匹配SimpleMatch應用在本問題上，搜索所有模式需要重復$$ k $$次，每次的時間復雜度為$$ O(n \cdot m_{i}) $$。直接應用SimpleMatch算法的時間復雜度為$$ O_{1} = O(n \cdot m_{sum}) $$。  #### 前綴樹 我們能否在一次匹配$$ text $$的過程中就同時找出所有模式呢？即并行算法（算法上的并行，非多線程多進程的并行）。 首先用所有$$ pattern $$構造一個前綴樹$$ pt $$，如圖所示：  $$ (1) $$ 從$$ text $$的首個字符$$ text[i = 0] $$開始，將其與前綴樹中的節點依次向下匹配，可知$$ text[0 \dots 1] = pt[2 \dots 5]$$，但$$ text[2] \ne pt[8] $$因此匹配失敗；  $$ (2) $$ 匹配位置向右移動一位，從$$ text[i = 1] $$開始，可知$$ text[1] = pt[1]$$但$$ text[2] \ne pt[3], text[2] \ne pt[4] $$；  $$ (3) $$ 匹配位置向右移動一位，從$$ text[i = 2] $$開始匹配，可知$$ text[2 \dots 3] = pt[1 \dots 3], text[2 \dots 5] = pt[1 \dots 9] $$匹配成功； $$ \cdots $$ 構建前綴樹的時間復雜度為$$ O(m_{sum}) $$，之后對于文本上每個字符，都匹配一次前綴樹即可，該算法的時間復雜度為$$ O_{2} = O(m_{sum}) + O(n \cdot max(m_{i})) $$。當$$ n $$遠大于$$ max(m_{i}) $$時顯然構造第二種算法更優。 #### 失敗指針 下圖中，當匹配到$$ text[i = 5] $$時有$$ text[5 \dots 6] = pt[2 \dots 5] $$，但$$ text[7] \ne pt[8] $$匹配失敗。我們不希望從$$ text[i = 6] $$處從前綴樹的根節點重新開始匹配，顯然$$ text[i = 6] $$在前綴樹中已經存在。因為$$ pt[1 \dots 1] $$是$$ pt[2 \dots 5] $$的后綴字符串，這時將前綴樹的匹配位置調整到$$ pt[1] $$，那么$$ pt[1] $$和$$ text[i = 6] $$可以繼續匹配，嘗試找到一個成功的匹配。圖中紅色的連線稱為失敗鏈接/失敗指針$$ failure link $$；  設字符串$$ \alpha $$的末尾字符為$$ pt[i] $$，嘗試在前綴樹中尋找$$ \alpha $$的最長后綴字符串$$ \beta $$（設$$ pt[j] $$是$$ \beta $$的末尾字符）。若找到這樣一個合適的$$ \beta $$，建立從$$ pt[i] $$到$$ pt[j] $$的指針，否則建立從$$ pt[i] $$到$$ pt[root] $$的指針。顯然前綴樹中每個節點只有一個失敗指針。失敗指針的出發節點是前綴樹中最后一個成功匹配的字符，其實質是后綴字符串，也稱后綴鏈接/后綴指針$$ suffix link $$。 失敗指針的核心思路在于匹配文本失敗時，希望避免從前綴樹的根部重新開始匹配。失敗指針要么指向一個與當前位置上字符串相同的最長的后綴字符串（這樣的指針就是后綴指針），要么指向前綴樹的根節點。比如下圖中$$ pt[2 \dots 5] = "sh" $$的最長后綴字符串是$$ pt[1 \dots 1] = "h" $$，$$ pt[2 \dots 8] = "she" $$的最長后綴字符串是$$ pt[1 \dots 3] = "he" $$。$$ pt[1 \dots 4] = "hi" $$找不到最長后綴字符串（也可以認為最長后綴字符串為空），因此有失敗指針$$ pt[4] \rightarrow pt[root] $$。  前綴樹中的失敗指針聯系的兩個節點可能在同一個字符串上，比如下圖中有失敗指針$$ pt[11] \rightarrow pt[5] $$，$$ pt[10] \rightarrow pt[2] $$，這兩個失敗指針在前綴樹中構成了環形圖。  #### 輸出指針 下圖中，當匹配到$$ text[10] = pt[8] $$時（即使在該位置沒有$$ text[8 \dots 10] = pt[2 \dots 8] $$匹配成功也同樣適用），我們發現不管前綴樹當前位置$$ pt[8] $$匹配成功與否，一定存在成功的匹配$$ pt[1 \dots 3] $$。利用這一特性避免了從$$ text[i = 9] $$和前綴樹的根節點重新開始匹配。顯然這也是失敗指針，但并非在匹配失敗時才跳轉，這類跳轉稱為輸出指針/輸出鏈接$$ output link $$，用紅色虛線表示。  再給一個特別情況，當匹配到$$ text[0 \dots 2] = pt[2 \dots 7] $$時，有失敗指針$$ pt[7] \rightarrow pt[6] $$，輸出指針$$ pt[6] \rightarrow pt[1] $$。因此對于前綴樹中的節點$$ pt[7] $$，需要遞歸的沿著所有失敗指針，找出一次成功匹配$$ text[2 \dots 2] = pt[1 \dots 1] $$。當匹配到$$ text[0 \dots 3] = pt[2 \dots 9] $$時，有輸出指針$$ pt[9] \rightarrow pt[8], pt[8] \rightarrow pt[4] $$。如圖所示：  仔細觀察可以發現，輸出指針$$ pt[i] \rightarrow pt[j] $$有幾個特性： $$ (1) $$ 兩個節點不在同一個字符串分支上，$$ pt[i] $$是前綴樹中的任意節點； $$ (2) $$ 輸出指針是一種特殊的失敗指針，$$ pt[j] \ne pt[root] $$。顯然每個節點上只有至多一個輸出指針； $$ (3) $$ $$ pt[j] $$是前綴樹中的葉子節點； 在匹配過程中，嘗試遞歸的沿著前綴樹上當前節點的失敗指針，找出所有輸出指針，這些輸出指針都是（在其他分支的字符串上的）成功匹配。 最終得到AC自動機算法：對于文本$$ text $$上的任意字符$$ text[i] $$，從前綴樹$$ pt $$的根部開始匹配： $$ (1) $$ 沿著前綴樹完成一次成功匹配，$$ text[i] $$上的位置$$ i $$向右移動一位，從前綴樹$$ pt $$的根節點重新開始匹配； $$ (2) $$ 匹配失敗時，若前綴樹上的當前節點上有非$$ pt[root] $$（非前綴樹根節點）的失敗指針，則跳到失敗指針處繼續匹配；若沒有這樣的失敗指針，則文本$$ text $$的匹配位置向右移動一位，從前綴樹$$ pt $$的根節點重新開始匹配； $$ (3) $$ 匹配途中若遇到輸出指針，立刻找到一次輸出指針所處的成功匹配，但不影響當前字符串分支上的匹配，當前的匹配仍然繼續； AC自動機的匹配時間復雜度為$$ O(n + m_{sum} + z) $$。其中$$ z $$是所有模式$$ pattern $$在文本$$ text $$上出現的次數。 #### 構建AC自動機 構建AC自動機需要三步：構建前綴樹；構建失敗指針；構建輸出指針。 構造前綴樹的過程詳見本書的DataStructure-PrefixTree。 構造失敗指針的過程是一種類似BFS/層序遍歷樹的算法。初始時令根節點的失敗指針指向自己，首先將前綴樹的第一層節點加入空隊列$$ Queue $$中，所有的失敗指針指向根節點。然后依次從$$ Queue $$中取出頭節點$$ pt[i] $$，對于頭節點的某個孩子節點$$ pt[child] $$，尋找它的失敗指針，并將$$ pt[child] $$推入$$ Queue $$中，直到$$ Queue $$為空： $$ (1) $$ 對于前綴樹根節點$$ pt[root] $$，其失敗指針指向自己； $$ (2) $$ 對于前綴樹第一層節點，其失敗指針指向$$ pt[root] $$； $$ (3) $$ 對于前綴樹中其他的節點$$ pt[i] $$，設該節點的字符為$$ x $$，其父節點為$$ pt[father] $$，且$$ pt[fail] $$為$$ pt[father] $$的失敗指針。若$$ pt[fail] $$有字符為$$ x $$的孩子節點$$ pt[child] $$，則顯然$$ pt[child] $$所在的字符串為$$ pt[i] $$所在字符串的最長后綴字符串。因此有失敗指針$$ pt[i] \rightarrow pt[child] $$。若不存在這樣的孩子節點，則遞歸的再考慮$$ pt[j] $$的失敗指針，直到失敗指針本身是$$ pt[root] $$，則有失敗指針$$ pt[i] \rightarrow pt[root] $$，遞歸結束；如圖所示：  在構造失敗指針的同時構造輸出指針，若$$ pt[i] $$的失敗指針$$ pt[j] $$不是前綴樹根節點$$ pt[root] $$，又是前綴樹的葉子節點，則有輸出指針$$ pt[i] \rightarrow pt[j] $$。顯然$$ pt[root] $$不存在輸出指針，前綴樹第一層節點也都不存在輸出指針。 AC自動機的構造時間復雜度為$$ O(m_{sum}) $$，加上匹配的時間，AC自動機算法的時間復雜度為$$ O(n + m_{sum} + z) $$。 -------- #### Aho Corasick Automata * https://cr.yp.to/bib/1975/aho.pdf * https://web.stanford.edu/class/cs166/lectures/02/Small02.pdf * https://www.geeksforgeeks.org/aho-corasick-algorithm-pattern-searching/ * http://www.learn4master.com/algorithms/aho-corasick-algorithm -------- #### 源碼 [AhoCorasickAutomata.h](https://github.com/linrongbin16/Way-to-Algorithm/blob/master/src/TextMatch/AhoCorasickAutomata.h) [AhoCorasickAutomata.cpp](https://github.com/linrongbin16/Way-to-Algorithm/blob/master/src/TextMatch/AhoCorasickAutomata.cpp) #### 測試 [AhoCorasickAutomataTest.cpp](https://github.com/linrongbin16/Way-to-Algorithm/blob/master/src/TextMatch/AhoCorasickAutomataTest.cpp)