Aho-Corasick 算法

# Colin James - Aho-Corasick算法 原文链接：https://compiler.club/aho-corasick/ ### 简介 本文描述了用于在序列中同时匹配多个子串的Aho-Corasick自动机的构建过程。我特别喜欢这个算法，因为它以相当优雅的方式从现有的树数据结构中构造出自动机。 ### 前缀树 前缀树是一种多叉树，用于存储一组字符串。前缀树中的每条边都标记一个字符，每个节点从概念上表示从根节点到达该节点所需的所有边字符的连接。 前缀树通过确保具有公共前缀的条目在树数据结构中共享这些前缀来减少冗余。 参见下面存储字符串集合 $\{\text{suit}, \text{suited}, \text{suitable}\}$ 的前缀树示例： 前缀树示例 你可以看到公共前缀 `suit` 被所有条目共享。另外请注意，表示完整条目的节点被明确标记出来。 ### 后缀链接 Aho-Corasick自动机通过所谓的后缀链接从转换失败中恢复。这些链接保留每个节点所代表字符串的最长后缀，而该后缀恰好是前缀树中某个模式串的前缀。这使得自动机可以转换到一个允许进一步匹配的模式串的状态，该模式串恰好以失败节点的最长后缀为前缀。 考虑应用于为字符串集合 $\{\text{item}, \text{suits}\}$ 构建的前缀树的后缀链接（以红色显示）： 带有后缀链接的前缀树示例 大多数节点的后缀链接都指向根节点。但是，如果我们查看节点 $8$（表示跟随 `suit` 到达的状态），我们会看到它的后缀链接（节点 $3$）指向一个节点，该节点是如果我们从根节点开始跟随其后缀 `it` 所能到达的节点。这允许匹配以 `it` 为前缀的模式串的可能性；在这种情况下，只有 $\{\text{item}\}$。 例如，如果我们扫描输入 `suitems`，我们会到达节点 $8$，发现没有标记为 `e` 的出边，我们将通过后缀链接进行转换，并从失败字符开始继续扫描，最终匹配到 `su[item]s`。 后缀链接的构建过程相当优雅，它们在对前缀树进行广度优先遍历的过程中计算得出。每个节点的情况计算如下： - 根节点及其直接子节点将根节点作为其后缀链接。 - 要计算每个其他节点的后缀链接，首先查看该节点父节点的后缀链接。对于一个字符序列 $(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$ 的后缀链接。否则，你通过跟随连续的后缀链接在树中继续向上查找。如果你到达根节点，你就停止（以避免通过跟随其后缀链接指向自身而无限循环）。 尽管我尽力在上面正式描述后缀链接的构建过程，但最好通过图解来说明。考虑为字符串集合 $\{\text{cadence}, \text{facade}\}$ 构建的、带有部分构建的后缀链接的前缀树： 后缀链接的增量构建示例 节点的编号是按其广度优先遍历顺序排列的。 在处理完上面计算出后缀链接的节点后，广度优先搜索队列将包含 $[(c, 5), (d, 6)]$。如果我们检查 $(c, 5)$，我们会查看其父节点的后缀链接。在这种情况下，它是前缀树的根节点。我们看到根节点有一条标记为 $c$ 的出边，因此通过该边到达的节点就是节点 $5$ 的后缀链接： 更新的后缀链接增量构建示例 在上述操作之后，队列将包含 $[(d, 6), (a, 7)]$。处理 $(d, 6)$ 很简单。和之前一样，其父节点的后缀链接是根节点。但是，没有标记为 $d$ 的出边，因此节点 $6$ 的后缀链接就是根节点（这表示树中没有其他模式串以 $\{\text{c}, \text{ca}, \text{cad}\}$ 中的任何一个为前缀）。在操作层面，如果到达节点 $6$ 且输入字符不是 $e$，则没有需要保留为另一个模式串前缀的后缀。我们舍弃已匹配的 $\text{cad}$，并从根节点重新尝试处理失败的输入字符。如果某个字符在根节点无法推进匹配，我们将停留在根节点，但继续处理字符流（因为它对任何模式串来说都是无用的开头）。 下一个有趣的情况是处理边 $(a, 7)$。节点 $7$ 的父节点的后缀链接是先前计算出的非根节点 $2$——节点 $2$ 确实有一条标记为 $a$ 的出边，因此节点 $7$ 的后缀链接是节点 $4$。这保留了 $\text{faca}$ 的后缀 $\text{ca}$ 作为另一个模式串 $\text{cadence}$ 的有效前缀。 当所有节点都已处理完毕时，后缀链接如下所示： 最终的后缀链接示例 为了清晰起见，我省略了指向根节点的后缀链接。有趣的是，你可以看到节点 $12$ 指向节点 $2$，试图为匹配 $\text{cadence}$ 保留前缀上下文，而节点 $12$ 是从假设它在匹配 $\text{cadence}$ 方面取得进展的节点到达的！ ### 输出链接 当一个模式串被引入前缀树时，在插入过程中遍历的最后一个节点会被标记为“输出”节点（通常存储被插入的模式串）。如果一个节点关联了一个输出模式串，这表示当进入该节点所代表的状态时应输出匹配项。但是，可能存在一个具有输出模式串的节点，其后缀也恰好是前缀树中的一个模式串——因此也必须同时输出。 为了捕获此信息，Aho-Corasick使用了输出链接。与后缀链接一样，输出链接总是指向表示更短字符串（在广度优先算法中先被访问）的节点。 考虑下面的前缀树（后缀链接为红色，输出链接为蓝色），它由字符串集合 $\{\text{spin}, \text{pin}, \text{in}\}$ 构建。 后缀链接和输出链接示例 蓝色链接连接具有关联输出的节点。很明显，当到达状态 $9$（表示匹配到 `spin`）时，节点 $8$ 和 $6$ 的输出也必须被输出（分别表示模式串后缀 `pin` 和 `in`）。你可以将输出链接视为一个节点链表，如果直接解释此匹配器，则需要迭代输出这些节点。 一个节点的输出链接（如果有的话）可以在其后缀链接计算完成后直接计算。这是合理的，因为后缀链接试图捕获当前节点模式串的最长后缀，而该后缀恰好是前缀树中某个模式串的前缀。因此，一个节点的输出链接是其后缀节点（如果其后缀节点关联了输出（本身是一个模式串）），否则，节点的输出链接是其后缀节点的输出链接。 ### 算法伪代码 计算后缀链接和输出链接的伪代码如下： ``` let Q be a queue of (char, node) # 根节点及其直接子节点的后缀链接指向根节点 root.suffix <- root for each (char, child) in root.arrows { child.suffix <- root # 将根节点的孙节点加入队列以进行遍历 add (char, child) to Q } while Q is not empty { let (char, node) = Q.poll() # 从父节点的后缀链接节点开始查找 let suffix = node.parent.suffix while suffix has no edge labelled char { # 跟随其后缀链接 suffix <- suffix.suffix # 如果到达根节点，则避免无限循环 if suffix == root then break } # 处理根节点有标记为 char 的出边的情况 if suffix has edge (char, actual) then node.suffix <- actual else node.suffix <- suffix # 节点的输出链接：如果其后缀链接节点是一个输出节点（是模式串本身），则指向它； # 否则，指向其后缀节点的输出链接。 if (node.suffix.pattern != null) then node.output = node.suffix else node.output = node.suffix.output } ``` ### 自动机 后缀链接和输出链接的计算是Aho-Corasick的核心，但对于构建自动机本身来说，这只是中间一步。当然，前缀树（添加了这些内部链接）可以直接解释执行。然而，由于可能需要重复地沿着后缀链接向上查找以确定在给定符号下的下一个转换状态，每个转换所需的工作量不是常数。 一旦后缀链接和输出链接就位，所有的转换和输出都可以静态地解析到一个确定性有限自动机中。为了计算这个自动机，需要执行最后一次广度优先遍历。 首先，处理根节点（基础情况）。对于每个符号 $a$，如果根节点有一条到达某个状态 $s$ 且标记为 $a$ 的边，那么这就是根节点在输入 $a$ 时的转换目标。如果不存在这样的边，则停留在原地（在根节点上自循环——有效地跳过该符号，因为它对前缀树中的所有模式串都是无用的开头）。所有从根节点可达的状态在处理过程中都会被添加到遍历队列中。 对于以广度优先方式处理的每个其他节点：对于每个符号 $a$，转换到通过标记为 $a$ 的边可达的状态。如果不存在这样的边，则转换到从该节点的后缀链接节点转换所能到达的状态。这体现了这样的思想：如果在前缀树的某条路径上无法取得进展，则状态将转换到另一个状态，该状态有望保留当前状态的最长后缀，而该后缀也是前缀树中某个模式串的前缀。很多时候，许多转换只是转到根节点（保留 $\epsilon$），因此对于许多离线的Aho-Corasick自动机，建议使用稀疏矩阵存储表示。 例如，由字符串集合 $\{\text{he}, \text{she}, \text{her}\}$ 构建的带有后缀链接和输出链接的前缀树如下： 确定化前的自动机 从上述前缀树计算出的确定性有限自动机（通过解析转换并将输出合并到集合中）将是： 从带有后缀链接和输出链接的前缀树计算出的DFA ### 演示 在下方，你可以从一组字符串构建一个Aho-Corasick前缀树： ### 延伸阅读 - 《高效字符串匹配：辅助书目搜索》(https://cr.yp.to/bib/1975/aho.pdf) - 描述整个算法的原始论文。