这段时间在一套内容审核系统里搞多模式匹配，几百条规则词要在用户发布的每一条内容里同步检索。最开始图省事，把规则词一条条拿出来循环查，规则一多直接卡到不忍直视。后来把算法换成AC自动机（Aho-Corasick automaton），同一批规则词的检索从“遍历文本N次”变成了“一次扫描出全部结果”，响应时间降了两个数量级还要多。AC自动机本质上是一个建立在模式串集合之上的状态机，它把Trie树和类似KMP的失配转移思想结合起来，读一遍文本就能把所有模式串是否出现、出现在哪里全部找出来。这篇文章会用图解的方式把Trie构建、fail指针、匹配过程这些核心环节拆开讲清楚，并附上可直接运行的代码和我在生产环境里的实践细节，适合正在做文本匹配、关键词过滤、敏感词识别这类功能，想搞清楚AC自动机到底怎么落地的人阅读。
1. 一次能查一堆词的需求，怎么把多模式匹配做快
具体场景是这样的：用户在平台上发一条内容，我们需要同时判断这条内容是否命中黑名单里的几百个词，命中的话记录位置，方便运营同事人工复核。规则词的共同点是短、多、组合关系复杂，有的词是另一个词的前缀，有的词互相重叠，但业务上都要抓出来。
如果按最简单的方式实现，伪代码大概是：
for keyword in keywords: for i in range(len(text)): if text.startswith(keyword, i): report(keyword, i)这是最朴素的做法，复杂度是O(N * M)，N是所有关键词的总长度，M是文本长度。规则少的时候无所谓，但规则词一旦上了三位数，每条内容平均几百到几千字，这个开销就非常可观了。我在早期版本里就吃过这个亏，规则词加到两百多条之后，单条内容的审核耗时从几毫秒暴涨到几十毫秒，流量一起来CPU直接被打满。
解决这个问题的核心思路，是把“文本回退”这件事彻底去掉。单模式匹配里KMP已经能做到匹配失败时文本指针不回退，代价是维护一个next数组；多模式下能不能也做一个类似的全局转移表，让所有关键词共享同一套匹配状态？这就是AC自动机的出发点。
几种常见方案的对比：
| 方案 | 匹配一个词的成本 | 匹配所有词的成本 | 适合场景 |
|---|---|---|---|
| 顺序逐个查找 | O(M) | O(N * M) | 关键词极少（个位数） |
| 正则表达式合并 | 取决于写法 | 可能退化成灾难性回溯 | 规则有结构、数量少 |
| 单用Trie树 | O(M)点 | 每个文本位置都要从根出发 | 快速判断“是否存在”还行 |
| AC自动机 | O(M)次整体扫描 | O(M + N + 命中数) | 关键词数量大、命中频繁 |
AC自动机最大的价值，是把“几百个词”合并成一个状态机，文本只需要从头到尾读一遍，每个字符走一次状态转移，全部词的命中情况就都出来了。代价是构建阶段要花一些时间和内存做预处理，但对内容审核这种“规则固定、文本海量”的场景来说，这个代价摊到每一次匹配里几乎可以忽略不计。
2. Trie树：把模式串集合压缩成一颗前缀树
AC自动机的底座是Trie树，也叫字典树、前缀树。它把所有模式串按照字符拆开，公共前缀用同一个节点路径表示，这样“hers”和“he”共享了“h-e”这一段，“she”虽然从不同起点出发，但也和“hers”的“h-e-r-s”形成交叉关系。
为了讲清楚后面所有概念，我用一个经典的例子：模式串集合为he, she, his, hers。先手工把这四个词插进Trie树：
root ┌──────┴──────┐ h s / \ | e i h / \ | | r * s e | (his) | s *(she) * (hers) (注：she的e)其中打星号的节点表示“走到这里时，某个模式串结束”。he在h-e处结束，他的结束标记放在e节点上；hers在h-e-r-s结束，结束标记放在最后的s节点；his在h-i-s结束；she在s-h-e结束。
Trie树的插入逻辑很容易理解：从根节点出发，依次看字符是否存在对应子节点，不存在就新建，存在就继续走，最后在终点节点打上“这是一个词的结尾”的标记。
这里有一个非常需要注意的设计点：一个节点上可能同时是多个词的结尾。比如模式串“他”和“他们”同时存在时，节点“他”既是“他”的终点，也是通往“他们”的中间节点。所以每个节点不仅是一个布尔标记，最好还维护一个列表，记录“以当前节点为结尾的所有模式串的编号”。
我把节点数据结构设计成下面这样：
class Node: def __init__(self): self.next = {} # 子节点映射，字符 -> 节点编号 self.fail = 0 # fail指针，后续章节会讲 self.out = [] # 以当前节点结尾的模式串编号列表如果是工程实现，节点一般不用类，而是用三个并行的数组：next_table存二维转移表，fail存每个节点的失配位置，output存每个节点上挂的规则编号。用数组替代对象的好处是内存连续、访问快、序列化也方便，在大量构建时GC压力小很多。
回到Trie本身。构建Trie树后，我们能做什么？能在一个文本位置，沿着树从根开始往下走，判断“以当前位置为起点，是否存在某个关键词”。但这不够，因为文本扫描时一个位置失败后，最朴素的做法是回到文本下一个位置重新从根出发，这样本质上每条关键词还是被当成了独立的一次匹配。AC自动机的关键改进，就是在这个Trie树基础上增加一套“失败时的跳跃规则”，让扫描能跨位置、跨前缀继续走下去。
3. fail指针：AC自动机里最容易被绕晕的设计
先想一个朴素问题：我在Trie树上匹配文本“shers”，从前两个字符开始，s -> h走到了节点sh，第三个字符是e，sh -> she，意外地匹配上了模式串“she”。这时文本继续往后读，第四个字符是r，问题是she这个节点下面没有指向r的子节点，按照普通Trie的规则，我应该回到文本的第二个字符位置，从根节点开始重新尝试。
但这样做浪费了一个重要信息：虽然从she这里走不下去了，可我已经读过的“she”这个字符串，它的后缀“he”恰好是另一个模式串“hers”的前缀。也就是说，我不需要回到文本起点重新来，只需要站在原地，把当前状态从“she”切换成“he”，然后用这个新状态去接着读字符r，就能继续匹配出“hers”。
这个“切换后的状态”就是失配时的去处，也就是fail指针指向的地方。形式化的定义是：fail指针指向当前节点对应字符串的最长真后缀，并且这个后缀必须能作为Trie树某个路径的前缀存在。如果找不到这样的后缀，fail就指向根节点。
用表格把上例中每个节点的fail指向列出来：
| 节点 | 对应字符串 | 最长可作为前缀的真后缀 | fail指向 |
|---|---|---|---|
| root | 空 | 无 | 无 |
| h | h | 无 | root |
| s | s | 无 | root |
| he | he | e（无法从根匹配） | root |
| hi | hi | i（无法从根匹配） | root |
| sh | sh | h（从根可匹配） | h |
| she | she | he（从根可匹配） | he |
| his | his | s（从根可匹配） | s |
| her | her | 无 | root |
| hers | hers | 无 | root |
看到这里你应该能感觉到，fail指针就像是KMP算法中next数组在Trie树上的推广。KMP里失配后利用“已匹配部分的最长相同前后缀”，AC自动机里失配后利用“已匹配字符串的在Trie中存在的前缀后缀”，本质都是不丢弃已经读过的文本信息。
接下来是构建fail指针的步骤。这一步必须用广度优先搜索（BFS），不能随手用递归，原因在于计算某个节点的fail时，依赖的是深度比它浅的节点，BFS天然保证了从根开始逐层推进的顺序。流程如下：
- 根节点的所有直接子节点，fail全部指向根节点，先入队。
- 从队列中取出节点cur，遍历cur的所有子节点。
- 假设cur对应的字符路径是“...abc”，cur的某个子节点nxt对应“...abcd”。要计算nxt的fail，先从cur.fail开始，看它有没有标签为d的子节点。如果有，nxt.fail就指向那个节点；如果没有，就继续顺着cur.fail的fail向上跳，直到找到为止；始终找不到就指向根。
- 找到的nxt.fail节点如果恰好是某个词的结尾，这个输出信息要合并到nxt上，否则匹配时会漏掉跨指针词。
这个“向上跳着找”的过程，与匹配阶段的字符转移完全一致。正因如此，很多优化实现会在构建时直接把每个节点的失配转移一步到位，生成一张完整的状态转移表，让匹配时无需while循环跳fail，这也是生产级代码会做的事情。
4. 匹配阶段：用“shers”一步步走一遍失配转移
现在把完整的状态机跑一遍。假设模式串还是he, she, his, hers，文本是shers。手工模拟一下每读一个字符时的状态变化和命中情况：
| 已读文本 | 当前节点 | 动作说明 | 命中 |
|---|---|---|---|
| s | s | 从根沿s走到节点s | 无 |
| sh | sh | 沿s->h走到sh | 无 |
| she | she | 沿sh->e走到she | she |
| sher | her | she没有r子节点，跳到fail指向的he，he有r子节点，走到her | 无 |
| shers | hers | her有s子节点，走到hers | hers |
这个例子把AC自动机的精髓全部展示出来了：
第一，文本索引从头到尾只增不减，这是“一次扫描”的本质。我并没有在字符r处失败后回到文本第二个字符重新开始，而是原地切换状态继续读。第二，“she”和“hers”在文本“shers”里是重叠的（she占据0-2，hers占据2-4），普通单模式匹配逐个查很容易漏掉这类重叠命中，而AC自动机在匹配时输出全部结果，重叠的部分也一并给你。第三，失配转移不是只发生一次，while循环可能连续跳多个fail指针，但每个文本字符平均分摊下来的代价是常数。
匹配阶段的逻辑可以统一描述为：每读一个字符c时，如果当前节点有c子节点，就走过去；没有，就顺着fail链向上找第一个有c子节点的节点，然后走过去；如果最终都没有，就回到根。到达一个新节点后，这个节点以及它沿fail链向上的所有节点，如果带有词尾标记，全部要输出。
为什么这些“沿fail链向上”的节点都要检查？因为当前节点对应的字符串，它的后缀可能本身就是另一个违禁词。举个例子，如果规则里同时有“他”和“他们”，当匹配到“他们”的“他”时，当前路径是“他”，那么“他”这个词已经命中了。如果只检查最终节点，就会漏掉“他”这个短词。解决方法是构建时把fail链上的输出合并到每个节点上，匹配时只查当前节点挂的out列表，就能避免反复向上跳链。
匹配复杂度方面，设模式串总长度为n，文本长度为m，命中次数为z，整体复杂度O(n + m + z)。这里的n是构建阶段的花费，m是扫描文本的必读代价，z是输出结果的代价。注意z这一项是无法避免的——只要你确实需要知道所有命中位置，每个命中位置总得占用一次操作。
5. 拿着就能用的最小实现：Python版本构建与匹配
纸上谈兵这么多，直接给一个能跑的版本。我用Python写了一个足够清楚的最小实现，所有模式串用编号管理，能返回每个模式串在文本中所有出现的位置。
from collections import deque class AhoCorasick: def __init__(self): self.next = [dict()] # 子节点表，每个节点一个dict self.fail = [0] # fail指针 self.out = [[]] # 每个节点挂载的模式串编号列表 def add(self, word, index): """插入模式串，index是这个模式串的唯一编号""" cur = 0 for ch in word: if ch not in self.next[cur]: self.next[cur][ch] = len(self.next) self.next.append(dict()) self.fail.append(0) self.out.append([]) cur = self.next[cur][ch] self.out[cur].append(index) def build(self): """构建fail指针，同时将fail链上的输出合并到当前节点""" q = deque() # 根节点的直接子节点 fail 指向根节点 for nxt in self.next[0].values(): q.append(nxt) while q: cur = q.popleft() for ch, nxt in self.next[cur].items(): f = self.fail[cur] # 向上跳fail，直到找到包含ch子节点的祖先 while f and ch not in self.next[f]: f = self.fail[f] # f可能是根节点，也可能是某个祖先节点 if ch in self.next[f]: self.fail[nxt] = self.next[f][ch] else: self.fail[nxt] = 0 # 合并输出链，匹配时只查当前节点即可 self.out[nxt].extend(self.out[self.fail[nxt]]) q.append(nxt) def match(self, text, patterns): """扫描文本，返回每个模式串命中的所有起始位置""" result = [[] for _ in patterns] cur = 0 for i, ch in enumerate(text): # 失配则沿着fail链找可用转移 while cur and ch not in self.next[cur]: cur = self.fail[cur] if ch in self.next[cur]: cur = self.next[cur][ch] # 当前节点挂载的所有模式串都命中 for idx in self.out[cur]: result[idx].append(i - len(patterns[idx]) + 1) return result if __name__ == "__main__": patterns = ["he", "she", "his", "hers"] ac = AhoCorasick() for i, word in enumerate(patterns): ac.add(word, i) ac.build() text = "shers" res = ac.match(text, patterns) for word, pos in zip(patterns, res): print(f"{word}: {pos}")这段代码跑出来结果应该是：
he: [] she: [0] his: [] hers: [2]构建阶段我多做了一步优化：把fail节点的out列表直接合并到当前节点的out列表。这样一来，匹配阶段不需要沿fail链向上遍历找输出，每走到一个节点直接看当前节点的out就行，把“遍历fail链输出”的复杂度彻底压平。这种做法在很多资料里被称为“输出链接”，是工程实现的标配。
如果追求极致性能，可以把dict()换成数组哈希表，甚至直接用二维转移表go[cur][c]预处理出每个状态在任意字符下的下一跳，这样匹配时连while跳fail都不用，一次数组取址就到下一个状态。代价是内存变大，但对纯字母场景完全可行。我在生产环境里用的是C++版本，节点和转移全部用数组存储，好处是构建后可以整体序列化成二进制快照，服务重启时直接加载，不用重新插关键词。
6. 上线前必须想清楚的坑：选型、编码、重叠与性能
很多文章讲完原理就结束，但真正的坑都在落地时冒出来。我在这套系统上踩过几回，挑几个典型问题说。
第一，不是所有场景都适合上AC自动机。如果规则词只有四五个、文本也不长，直接顺序find比什么算法都简单，构建AC自动机的开销反而拖慢节奏。我的建议是规则词超过20个，或者这块文本会被反复扫描（比如一个规则集服务于所有用户内容），才值得用AC自动机。规则词经常动态增删的团队也要慎重，静态构建的AC自动机对热更新不友好，删词尤其麻烦，常见做法是维护版本号定期全量重建，或者做成两层结构：新词走增量小表，旧词走大表，查询时两边同时查再合并结果。
第二，编码归一化必须在进AC自动机之前完成。内容审核里最痛苦的不是算法本身，而是中文的变体。全角和半角、简体与繁体、大写和小写、甚至“违-禁”中间插入连字符，如果不做预处理，AC自动机再快也认不出来。我的做法是文本进入匹配前置一个归一化管线：统一大小写、全角转半角、移除规则中约定的干扰字符，再送到自动机。注意关键词表也要经过同一套归一化流程，并且要和线上规则保持完全一致，否则构建出来的状态机和线上行为会脱节。
第三，重叠命中会制造业务难题。比如关键词“北京”和“北京市”同时存在，一条包含“北京市”的文本会把两个词都命中。算法层面给的是全部结果，这没有错，但业务层往往要求“最短命中”“最长命中”或者“按权重选一个”。我建议在AC自动机之后加一个结果裁决层：把所有命中按位置排序，做区间合并，再根据词权重决定最终输出。绝对不要试图在匹配过程中做长短取舍，会把自动机的逻辑搅得一团糟。
第四，输出量本身也要设防。我有一个极端案例：规则集里有两万多个词，某条文本几乎每个字符都命中好几个。如果不限制结果数量，一次匹配能产生几十万个命中对象，内存瞬间涨上去。后来在匹配层加了参数：每个模式串只保留前N个位置、或者全部命中只保留前N个总数，超出部分只计数不分发，才把压力降下来。做内容审核时“有没有命中”往往比“命中了几次”更重要，这个设计帮我省了大量的下游开销。
第五，内存和构建时间需要提前评估。纯英文字母用二维数组转移表很舒服，每个状态256个int，模式串总量在几万级别时内存还能接受。但中文关键词直接用数组会爆炸，中文字符空间太大，只能退回到哈希表或者双数组Trie的路线。双数组Trie配合AC状态转移是文本过滤领域的黄金组合，构建稍复杂，但内存压缩非常明显，读一份几百MB的词表也没问题。构建时间上，几千词的规则集在Python里也就几十毫秒到一两百毫秒，C++会快一个量级，除非词表到百万规模，否则完全不用优化构建阶段。
第六，别把AC自动机当成语义理解的工具。它能做的是快速找出“文本里是否有这些字符串”，但“这句话是不是在骂人”“这句话有没有合规风险”这种问题，仅靠字符串匹配远远不够。字符串命中只能作为触发信号，更准确的判断还需要结合上下文、语义模型、运营规则一起做。我见过不少团队把AC自动机的命中数直接当成风险分，这会在低俗词误命中率极高的场景下制造大量无效工单。
最后分享一点我的个人体会。第一次在项目里把AC自动机跑通时，看着几百个关键词在一条长文本上毫秒级出结果，确实有“豁然开朗”的感觉。但后来用久了就明白，AC自动机是个很成熟的工具，价值高低取决于你怎么用它——输入侧的归一化做得好不好、输出侧的裁决规则清晰不清晰，这些周边工程往往才是决定效果的关键。算法本身不会替你思考业务规则，它只负责高效地把所有可能性摆到你面前。先把自动机跑起来，再花时间打磨数据、规则和结果处理，方向一定不会错。
