关于 AC 自动机

大家好，欢迎来到IT知识分享网。

什么是 AC 自动机

AC 自动机，全称 Aho-Corasick 自动机，是一种用于字符串搜索的算法，由 Alfred V. Aho 和 Margaret J. Corasick 在 1975 年提出。这个算法是为了解决在一个主文本字符串中查找多个模式字符串（或称为“关键词”）的问题，它可以在线性时间内完成搜索，非常高效。

下文是 wiki 百科中的原文内容

在计算机科学中，Aho-Corasick 算法是 Alfred V. Aho 和 Margaret J. Corasick 于 1975 年发明的一种字符串搜索算法。 [1]它是一种字典匹配算法，用于在输入文本中定位有限字符串集（“字典”）的元素。它同时匹配所有字符串。算法的复杂度与字符串的长度加上搜索文本的长度加上输出匹配的数量呈线性关系。请注意，由于找到了所有匹配项，因此如果每个子字符串都匹配，则匹配项的数量可能是二次方（例如，dictionary = a、aa、aaa、aaaa 和 input 字符串是aaaa）。

通俗地说，该算法构建了一个类似于特里树的有限状态机，在各个内部节点之间具有附加链接。这些额外的内部链接允许在失败的字符串匹配之间快速转换（例如，在不包含 cart 的 trie 中搜索 cart，但包含 art，因此会在以 car 为前缀的节点处失败）到共享的 trie 的其他分支通用后缀（例如，在前面的情况下，属性分支可能是最好的横向转换）。这允许自动机在字符串匹配之间转换，而不需要回溯。

当预先知道字符串字典（例如计算机病毒数据库）时，可以离线执行自动机的构造，并将编译后的自动机存储起来供以后使用。在这种情况下，其运行时间与输入长度加上匹配条目的数量成线性关系。Aho-Corasick 字符串匹配算法构成了原始 Unix 命令 fgrep 的基础。

如何被想出来的呢？

Aho 和 Corasick 设计这个算法的初衷是为了提高字符串匹配的效率，特别是在需要同时查找多个模式字符串时。当时的背景是计算机科学正在迅速发展，人们需要更高效的算法来处理大量的文本数据。AC 自动机的设计灵感部分来自于有限状态机（Finite State Machine, FSM）和 Trie（字典树）的概念，通过将多个模式字符串构建成一个具有状态转移功能的 Trie 树，并在此基础上添加失败指针（fail pointer），使得在匹配失败时能够高效地转移到下一个可能的状态，从而避免了重复的匹配工作。

适用的场景

AC 自动机的主要应用场景包括：

• 文本过滤和内容审查： AC 自动机可以用来在文本中查找敏感词或特定的词组，因此在内容审查和敏感信息过滤的系统中非常实用。
• 生物信息学： 在基因序列分析中，可能需要在 DNA 序列中查找多个短序列，AC 自动机因其高效性而被广泛应用。
• 网络安全： 在网络入侵检测系统（IDS）中，AC 自动机可用于匹配多种入侵签名或恶意代码片段。
• 文本挖掘和自然语言处理： 在大规模文本数据中查找多个关键词或短语时，AC 自动机可以提供高效的解决方案。
• 编译原理： 在词法分析阶段，AC 自动机可用于高效识别多个关键字和模式字符串。

原理之前的扩展

何为 Trie 树

Trie树（发音为”try”），又称为前缀树或字典树，是一种树形结构，它是一种用于快速检索字符串数据集中特定字符串的高效数据结构。

Trie树的基本概念和特点：

节点结构：Trie树的每个节点通常包含多个子节点，每个子节点代表一个字符。从根节点到某一节点的路径，代表一串字符。

• 前缀共享：在Trie树中，具有共同前缀的字符串会共享前缀的路径。例如，字符串”tree”和”trie”会在前两个字符”tr”后分叉成两条路径。
• 结束标记：为了标识一个字符串完整地出现在Trie树中，会在字符串的最后一个字符对应的节点上做一个特殊标记，如设置一个布尔标记或存储一个指向数据的引用。
• 快速查找：使用Trie树可以在O(m)时间内查找一个长度为m的字符串，这是因为它几乎不涉及字符串比较操作。

Trie树的构建过程：

初始化： 从一个根节点开始，根节点通常不包含字符。
插入字符串： 将每个字符串的字符逐个插入到Trie树中。如果某个字符对应的节点不存在，则创建它。
重复字符： 如果插入的字符在Trie树中已有对应的节点，则沿着该节点继续插入下一个字符。
结束标记： 每个字符串的末尾字符对应的节点被标记为结束节点，表明一个字符串已经插入完成。

Trie树的应用场景：

Trie树由于其高效的查找性能，特别适合于处理字符串匹配相关的问题。

何为自动机

“自动机”（Automaton）在计算机科学中通常指的是一种抽象的机器，它能够根据输入自动执行一系列操作，而不需要外部的干预。自动机通常根据一组规则或算法自动处理输入序列，并根据这些输入改变其内部状态，可能还会生成输出。它们在形式语言理论、编译器设计、文本处理等领域中有着广泛的应用。

Aho-Corasick自动机是一种特定类型的自动机，它根据一组预定义的字符串（模式）进行构建，当文本输入流被送入自动机进行处理时，AC自动机会自动地匹配这些预定义的模式。它之所以被称为自动机，是因为它能自动完成以下操作：

状态转换： AC自动机有一系列内部状态，这些状态对应于Trie树中的节点。每读取输入文本中的一个字符，自动机就根据当前状态和输入字符转移到下一个状态。

模式识别： 当输入文本中的某个部分与某个预定义的模式匹配时，AC自动机会识别出这个匹配，并可以执行相关的动作（例如，返回匹配位置、记录匹配等）。

失败转移： 如果当前状态没有一个直接的转移对应于当前的输入字符，自动机会使用失败指针（fail pointer）来找到下一个可能的状态，而不是从头开始匹配。

输出结果： 每当AC自动机到达某个状态，它会检查该状态是否对应于某个（或某些）预定义模式的结束。如果是，自动机将输出与当前状态相对应的模式的匹配信息。这些信息可能包括模式的起始索引、结束索引或是已匹配的文本部分。

因此，”自动机”这个名词强调了AC自动机在不需要人工干预的情况下对模式进行高效匹配的能力。自动机在遇到失败匹配时不需要回溯输入文本，而是能够利用内部的失败指针自动地跳转到其他可能的匹配状态，这是它与简单的模式匹配算法相比的一个显著优势。这种自动的状态转移和匹配检测过程是它得名”自动机”的原因。

Trie 树与 AC 自动机的联系

Trie 树，又称前缀树或字典树，是一种用于快速检索字符串数据集中的键的有序树结构。这种数据结构允许共享前缀，可以非常高效地存储和检索字符串集合中的关键字。Trie 树的每个节点代表一个字符串（或者字符串的一部分），每条边代表一个字符。从根节点到某一节点的路径对应于字典中的一个单词或者单词的前缀。

对于 Aho-Corasick 自动机，它确实是基于 Trie 树的，并在其上添加了失败指针来实现快速的模式匹配。如果你需要向 AC 自动机中添加新的元素，确实可能需要对树进行一定的更新或重建，尤其是更新失败指针。在实际应用中，如果频繁地添加新元素，这种重建可能会变得耗时。

AC 自动机本身就是一种特殊的数据结构，它结合了 Trie 树和状态机的特点。如果你要谈论这种结构并强调其用于模式匹配的特性，通常就会称之为 Aho-Corasick 自动机，简称 AC 自动机。在文献中，它没有一个不同的专用名称，通常就是直接称为 Aho-Corasick 自动机或者 AC 自动机。

在某些实现中，为了避免重建整个数据结构，可能会采用更灵活的数据结构，或者在 AC 自动机的基础上进行改进，使其支持动态插入和删除操作，但这通常会增加实现的复杂性。在需要处理动态变化的模式集合时，这些改进可能会提供更好的性能。

AC 自动机的原理

AC 自动机（Aho-Corasick 算法）是一种用于在输入文本中快速查找多个模式（即字符串）出现的算法。它由 Alfred V. Aho 和 Margaret J. Corasick 在 1975 年提出，主要用于字符串匹配问题，特别是在处理大量模式匹配时非常有效。AC 自动机的核心思想是将所有模式构建成一个有限状态机（Trie 树结构），并在这个结构中加入失败指针（fail pointer），使得在匹配失败时能快速转移到下一个可能的状态，从而避免重复检查之前已经匹配过的文本。

AC 自动机的构建过程

构建 AC 自动机的过程主要分为两个步骤：构建 Trie 树和添加失败指针。

构建 Trie 树：

• 首先，将所有模式串构建成 Trie 树。每个节点代表一个字符，从根节点到某一节点的路径代表一个模式串的前缀。
• 每个模式串的终点节点标记为输出，表示该路径对应的模式串已完全匹配。

添加失败指针：

• 对于 Trie 树的根节点的所有直接子节点，它们的失败指针都指向根节点。
• 对于其他节点，假设当前节点标记为字符 C，其父节点的失败指针指向的节点有一个直接子节点也标记为字符 C，则当前节点的失败指针指向那个子节点。如果找不到，就递归地沿着失败指针继续查找，直到到达根节点。

工作原理

在文本匹配阶段，AC 自动机从根节点开始，按照文本字符逐个进行转移，如果遇到匹配失败的情况，就通过失败指针跳转到其他分支继续匹配，这样可以避免从头开始匹配，提高效率。当到达某个节点时，如果该节点是输出节点，或者沿着失败指针可以回溯到一个输出节点，那么就找到了一个模式串的匹配。

用例举例

假设我们有一段文本 “abccab”，我们需要在这段文本中查找以下模式串：“a”, “ab”, “bc”, “bca”, “c” 和 “caa”。

构建 Trie 树： 首先基于这些模式串构建 Trie 树。
添加失败指针： 然后为 Trie 树中的每个节点添加失败指针。
文本匹配： 最后，使用 Trie 树来匹配整段文本。

在这个例子中，每个节点除了有指向子节点的指针外，还有一个失败指针（用虚线表示）。例如，节点 “b” 的失败指针指向根节点，因为当在 “ab” 后面遇到非 “c” 的字符时，下一个可能的匹配是从头开始的 “a”。

通过这种方式，AC 自动机可以在 O(n) 的时间复杂度内完成对所有模式串的匹配，其中 n 是文本的长度。这使得 AC 自动机在诸如网络内容过滤、生物信息学序列分析、文本编辑器的查找替换等场景中非常有用。

视频解释

实际用例举例

添加失败指针（蓝色”后缀”弧线）：

添加绿色”字典后缀”弧线：

文本匹配过程：

通过这种方式，AC自动机能够在文本中高效地找到所有字典中的单词，时间复杂度是线性的，即与文本的长度成正比。这使得AC自动机在诸如文本搜索、网络内容过滤和生物信息学等领域的字符串匹配问题中非常有用。

如果大家有兴趣的话不妨看看各语言 AC 自动机的视线源码，可以理解的更为透彻一点

源码实现

引用