Algorithm: Aho–Corasick algorithm (AC自動機)

我不久前曾遇到一個需求：在文章中尋找是否出現特定的多種句子。

當時我將所有要抓的句子建成一個Trie，不斷的移動文章並放到Trie中搜尋。後來朋友提到了AC自動機，才有這一篇。

KMP Algorithm

回顧 Algorithm: KMP 中的例子，假設pattern為abacab，則對應的最長prefix為001012，而prefix的數字，也代表比不到時的跳躍位置。

假設我們把pattern的每個字元視為一棵單通的樹，從根開始依序放上abacab，則陣列上的跳躍，就變成了node之間的跳躍。

思考一下，為何橘a知道要跳到白a？橘b知道要跳到白b？

Ans：因為橘a的前一個點，白c比不到東西指向root，輪到橘a時從root開始比。而橘b的前一個點，橘a已經指向白a，繼續往下比剛好也是b，因此橘b指向白b。

• 藍線：該點沒有prefix
• 綠線：比到的第一組prefix
• 橘線：比到的第二組prefix

PATTERN_2: baca

pattern1 = abacab
pattern2 = baca

從現在起，我叫彩色的線為失敗指標，意思是當某個點比失敗了，要跳躍後繼續比的點。

本例中，假設雙色a已經指向紫a，繼續比深黃b時，發現紫a的下面比不到東西，因此紫a沿著失敗指標跳到白a，又白a下面有淺黃b，因此深黃b最終指向淺黃b。

為了指向從根出發最長的prefix，因此AC自動機的失敗結點並不一定指向自己過去的node。

建構AC自動機的流程

1. 將patterns變成一棵Trie。
2. 接上失敗指標，過程是整棵樹的BFS Traversal。
3. 匹配 (完全跟KMP一樣)：

• 當前匹配成功則接著比
• 匹配失敗，跳到失敗結點(等同KMP跳到prefix)繼續比
• 注意路過的結點，都必須沿著失敗指標走到底。
  以本例來說，假設text=abacad，前五個字沿著垂直線往下走，比到第六個字失敗。雖然baca也存在text中，但匹配過程不會跳到斜的baca，要匹配過的點自己延著失敗指標移動，才會發現其實有匹配到baca。

程式

• upgrade_fail() 和 search_patterns()是不是覺得跟KMP中的gen_partial及search很像呢？
• 但AC自動機是多個pattern，因此每個路過的node都要遍歷一次fail node，也就是跑 traversal_fail()

問題

• 很容易注意到，node一樣的話， traversal_fail(node)的結果也會一樣，既然如此，要如何優化這一步？
  Ans: 如果某些pattern的重複率高且node很深時，我會建議採用dfs+mem，這個方法適合兩個時機，1.建fail_node時、2.第一次traversal_fail()時。

# Initialize all nodes: node.result = None
def traversal_fail(node):
    if node.result is not None:
        return node.result
    ...do something
    node.result = res
    return res

• 今天有一個文章，假設任務是在文章中尋找特定的多個句子，該怎麼做？
• 承上，如果要跳過文章中的標點符號、大小寫視為相同，又要將比對結果mapping回文章的對應位置上，該怎麼做？

相關題目

• Leetcode 1032: Stream of Characters