Aho-Corasick Algorithm
Aho-Corasick Algorithm
Aho-Corasick Introduction
This post describes the construction of an Aho-Corasick automaton for the simultaneous matching of substrings within a sequence. I’m fond of this algorithm because it constructs an automaton from an existing tree data structure in a rather pleasant way.
Aho-Corasick 简介 本文介绍了如何构建 Aho-Corasick 自动机，用于在序列中同时匹配多个子串。我非常喜欢这个算法，因为它能以一种非常优雅的方式从现有的树形数据结构中构建出自动机。
Tries
A trie (or “prefix tree”) is an $n$-ary tree that stores a set of strings. Each edge in the trie is labelled with a character and each node conceptually represents the concatenation of all the edge characters required to reach it (starting from the root). Tries are designed to reduce redundancy by ensuring entries with common prefixes share these prefixes within the tree data structure. See the trie below that stores the strings ${\lbrace \text{suit}, \text{suited}, \text{suitable} \rbrace}$: You can see that the common prefix of suit is shared by all entries. Also note that nodes representing complete entries in the trie are explicitly marked.
字典树 (Tries)
字典树（或称“前缀树”）是一种存储字符串集合的 $n$ 叉树。树中的每条边都标有一个字符，每个节点在概念上代表了从根节点到达该节点所需经过的所有边字符的拼接。字典树旨在通过确保具有公共前缀的条目在树结构中共享这些前缀来减少冗余。请看下方存储了字符串 ${\lbrace \text{suit}, \text{suited}, \text{suitable} \rbrace}$ 的字典树：你可以看到 suit 的公共前缀被所有条目共享。同时请注意，代表完整条目的节点已被明确标记。
Suffix Links
Aho-Corasick automatons recover from transition failure by following so-called suffix links. These links preserve the longest suffix of the string represented by each node that happens to exist as a prefix of a pattern in the trie. This allows the machine to transition to a state that permits further matching of patterns that happen to have the failing node’s longest suffix as a prefix. Consider the suffix links applied (in red) to the trie constructed for the strings $\lbrace \text{item}, \text{suits} \rbrace$ below: The majority of nodes have the root node as their suffix link. However, if we look at node $8$, representing the state reached by following suit, we see that its suffix link (node $3$) points to the node one would reach if, starting from the root, we had followed its suffix, it. This permits the potential for matching the patterns prefixed with it; in this case, only $\lbrace \text{item} \rbrace$. For example, if we were scanning the input suitems, we would reach node $8$, see that there is no outgoing edge labelled e, we would transition via the suffix link and continue scanning from the failing character, eventually matching su[item]s.
后缀链接 (Suffix Links)
Aho-Corasick 自动机通过跟随所谓的“后缀链接”从转换失败中恢复。这些链接保留了每个节点所代表字符串的最长后缀，且该后缀恰好也是字典树中某个模式串的前缀。这使得自动机能够跳转到一个状态，从而继续匹配那些以失败节点的最长后缀为前缀的模式串。考虑下方为字符串 $\lbrace \text{item}, \text{suits} \rbrace$ 构建的字典树及其后缀链接（红色）：大多数节点的后缀链接都指向根节点。然而，如果我们观察节点 $8$（代表跟随 suit 后到达的状态），会发现它的后缀链接（节点 $3$）指向了从根节点出发跟随其后缀 it 所到达的节点。这使得匹配以 it 为前缀的模式串成为可能；在本例中，即 $\lbrace \text{item} \rbrace$。例如，如果我们扫描输入 suitems，到达节点 $8$ 后发现没有标记为 e 的出边，我们就会通过后缀链接跳转，并从失败的字符处继续扫描，最终匹配到 su[item]s。
Construction
The construction of suffix links is rather pleasant, they’re computed in a breadth-first traversal of the trie. The cases for each node are computed as follows: The root and its children have root as their suffix link. To compute the suffix link for each other node, you start by looking at the node’s parent’s suffix link. For a pattern of characters $( c_1, c_2, c_3, \ldots, c_n)$, to compute a suffix link for a node $c_k$ ($k \geq 3$), you examine the suffix link of $c_{k-1}$. That suffix link preserves the longest suffix of $(c_1, \ldots, c_{k-1})$ that represents a prefix of a pattern in the trie. If the node at that suffix link has an outgoing edge labelled $c_k$, then the target of that edge is $c_k$’s suffix link. Otherwise, you continue to chase up the trie by following successive suffix links. If you reach the root, you stop (to avoid iterating indefinitely by following its suffix link to itself).
构建过程 后缀链接的构建非常巧妙，它们是在字典树的广度优先遍历中计算出来的。每个节点的计算情况如下：根节点及其子节点的后缀链接指向根节点。对于其他节点，计算其后缀链接时，首先查看其父节点的后缀链接。对于字符序列 $( c_1, c_2, c_3, \ldots, c_n)$，要计算节点 $c_k$ ($k \geq 3$) 的后缀链接，需检查 $c_{k-1}$ 的后缀链接。该后缀链接保留了 $(c_1, \ldots, c_{k-1})$ 的最长后缀，且该后缀是字典树中某个模式串的前缀。如果该后缀链接指向的节点拥有标记为 $c_k$ 的出边，那么该出边指向的目标节点就是 $c_k$ 的后缀链接。否则，继续沿着后缀链接向上追溯。如果到达根节点，则停止（以避免因跟随指向自身的后缀链接而陷入无限循环）。
Output Links
When a pattern is introduced into the trie, the last node traversed during insertion is annotated as being an “output” node (usually storing the inserted pattern). If a node has an output pattern associated with it, this identifies a match that should be output when entering the state represented by that node. However, it may be the case that a node with an output’s pattern has a suffix that also happens to be a pattern in the trie - and, so, must also be output at the same time. In order to capture this information, Aho-Corasick employs output links. As with suffix links, it will always be the case that output links point to nodes representing shorter strings (visited first in the breadth-first algorithm).
输出链接 (Output Links) 当一个模式串被插入字典树时，插入过程中遍历的最后一个节点会被标记为“输出”节点（通常存储该模式串）。如果一个节点关联了一个输出模式，这意味着进入该节点所代表的状态时应输出一个匹配项。然而，有时带有输出模式的节点其后缀也恰好是字典树中的另一个模式串，因此必须同时输出。为了捕获这些信息，Aho-Corasick 使用了输出链接。与后缀链接一样，输出链接总是指向代表较短字符串的节点（在广度优先算法中先被访问）。