企业官网建设流程全解析

做内容安全这块，或多模式匹配相关的同学，大概都躲不过 AC 自动机。前阵子我接到一个需求，要把一份 GB 级的敏感词词表（具体多少条就不透露了，反正几十亿个字符）编译成匹配引擎，服务内存还不能爆，响应还得在毫秒级。

一开始我的想法很简单：Go 标准库撸一个 Trie，节点用 map 存子节点，AC 自动机的 fail 指针一挂，完事。结果词表切分灌入之后，内存直接飙到几十个 GB，服务连启动都费劲。老实说，那会儿我才意识到，AC 自动机虽然理论成熟，但在海量词库场景下，实现方案选不对，内存就是无底洞。后来我换了个思路，用双数组 Trie（Double-Array Trie）的思想结合 AC 自动机，生生把内存砍掉了 80% 以上，才算是把 GB 级词表稳稳落了地。

这篇文章就专门聊聊这件事。我会把从标准实现到内存优化方案的完整过程、核心数据结构选型、构建流程里的坑、以及压测和调优的经验都记录下来。如果你也正在被大词表内存问题折磨，或者对 AC 自动机的工程化实现感兴趣，这篇应该能给你不少可落地的参考。

1. 问题盘点：GB 级词表到底把内存吃在哪了

先掰扯清楚，词表达到 GB 这个量级之后，内存耗在哪里，这是优化的前提。我用最普通的方式实现过 AC 自动机，运行时的内存分布大概有这么几块：子节点指针、map 桶开销、fail 指针和状态节点本身的结构体占位。

1.1 标准 Trie + map 实现的内存账本

假设一个典型的词条集合，每次插入一个词，Trie 都会创建一串节点。每个节点如果用一个结构体表示：

type node struct { child map[rune]*node fail *node out []string }

一个节点的开销，在 64 位系统上大概是这样的账：child 这个 map 本身是个指针，占 8 字节；但 map 是懒加载的，通常不会为每个节点都初始化。可一旦某个节点有子节点，map 底层会有 hmap 结构，还需要至少一个 bucket（一个 bucket 8 个槽位，每个槽位 8 字节 key + 8 字节 value）。就算只有一个子节点，也要占一个小 bucket 的空间，这就有几十字节出去了。

再加上 fail 指针 8 字节，out 切片 24 字节，节点本身 32 字节对齐。算下来，任何带子节点的节点，实际占用都在 50 到 200 字节左右。当然，这是不精确的估算，具体的 map 桶扩容还受并发和哈希分布影响。但量级没跑——一千万级别的节点，用 map 实现，内存起码十几个 GB 起步。GB 级词表切分成这种 Trie，内存是线性的节点数乘单节点开销，几十 GB 完全不夸张。

1.2 为什么传统 AC 自动机在大词表场景下会失灵

AC 自动机的核心就是 Trie 加 fail 指针。匹配时沿着状态跳转，失配就条 fail。这个思路在 CPU 上很高效，但是内存问题被很多人忽略了。因为每个子节点在 map 里都有一份 key（字符）和一份 value（节点指针），光是这个映射关系，就要比每个节点的实际内容多出不少开销。再加上 fail 指针，每个节点再加 8 字节，输出表又得挂 slices 或 list，这又是一大块。

你可能会说，可以用切片数组跑 rune 桶，每个节点只放一个 next [26]int32 的定长数组，ASCII 场景很省。但是中文词表不是这样，几万个汉字，定长数组需要几万个 int32，一个节点就 200KB，这和暴殄天物差不多。所以常见方案是 map[rune]int32 或者 map[rune]*node。到了 GB 级词表，这种实现就是灾难。

1.3 优化目标：既能跑前缀跳转，又不烧内存

我们的目标很明确：在不牺牲匹配时间复杂度的前提下，把单节点的存储开销压到极致。标准 AC 自动机的匹配复杂度是 O(n)，这个不能变，搜索阶段不能打折扣。那唯一能动手的地方就是节点的表示方式。

这里我从《An Efficient Implementation of TRIE Structures》这篇论文里提到的双数组 Trie 思路切入：用 base 和 check 两个整数数组来表示整个 Trie。Go 里面用 int32 足够，单个节点只看这两个数组的话，只需要 8 字节。子节点查找变成纯数组下标访问，完全不用 map，也几乎没有指针。

这还没完，AC 自动机的 fail 指针还能用数组下标来存，输出表也直接改成整数索引。这样算下来，GB 级词表构建成状态机后，内存可以控制到非常理想的水平。我自己实测，优化前大概要 30 几 GB 的场景，优化后只需要 5 到 6 GB，后面会给出具体压测数据。

2. 方案选型：为什么是双数组 Trie 而不是其它结构

反序列化、内存映射、磁盘索引、后缀自动机等等，都是备选项。但我最终选了双数组 Trie 加 AC 自动机，不是拍脑袋，是综合比较后的结果。

2.1 双数组 Trie 的基本原理

双数组 Trie 的核心只有两个数组：base 和 check。每个状态 s 对应一个下标。从状态 s 经过字符 c 转移到状态 t，需要满足数组下标的关系，这个逻辑一定要刻在脑子里：

t = base[s] + c check[t] = s

也就是说，如果我要判断状态 s 后面能不能接字符 c，就去数组 t 的位置上看 check 值是不是等于 s。如果相等，转移合法；否则说明这条边不存在。为了确保转移唯一，base[s] 的值要保证 base[s] + c 这个位置没有被其它状态以同样方式占用，并且没有冲突。

这个结构的聪明之处在于，它用两个 int 数组就表示了原来需要大量指针和 map 才能表示的完整 Trie。字符 c 直接参与下标计算，把“查找”变成了“取数组元素”。代价是 base 值的选择需要一定的空闲位置搜索，构建阶段会有一些 CPU 开销。

2.2 和 AC 自动机怎么结合

标准 AC 自动机每个节点需要保存 fail 指针。双数组 Trie 里的状态本身就是数组下标，所以 fail 也可以用一个整数数组 fail[] 来存。这样一来，节点结构完全扁平化了：所有状态都躺在连续内存里，CPU 缓存命中率也好，内存碎片也少。

匹配的时候，从根状态出发，遍历文本里的每个 rune，尝试做转移。转移成功就更新当前状态；失败就沿着 fail 跳，直到能转移或者回到根。这个查找过程里，查询 base 和 check 都是 O(1) 的数组访问，fail 回溯在均摊意义下也是常数级。这几个操作组合起来，匹配速度不但没有牺牲，反而比 map 版本快不少。

2.3 为什么不直接用盘古分词里的 DAT，或者干脆用 mmap

如果只做纯 Trie，用现成的 DAT（双数组 Trie）库不是不行。但问题是，AC 自动机的 fail 链需要额外的数组，输出表也需要额外的关联信息，现成 DAT 库不一定能很好配合。自己写一套，反而可以把 fail、output 一并设计进去，紧凑度更高。

至于内存映射 mmap，对 GB 级词表来说确实是个诱人的选项，毕竟可以直接把索引文件映射到内存，省去加载。但匹配过程如果需要在内存盘上做随机访问，性能受IO影响很大。而且像敏感词过滤这类热路径，我们更希望常驻内存，配合 mmap 反而要在代码里处理缺页中断，不可控。所以我选择构建期一次性把状态机构建到内存，后续只读匹配。

2.4 从 AC 自动机到双数组 AC 自动机的整体架构

我把整体设计分成两层：构建期和匹配期。

构建期的输入是词表文本，一行一个词。先把所有词条读进来，在内存里临时构建一棵普通 Trie，这个 Trie 用临时 map 存储，只用于构建，构建完立刻释放。构建完普通 Trie 之后，把它转换为双数组形式：分配 base、check 数组，逐层扫描普通 Trie 的节点，为冲突最小的节点分配 base 值，完成子节点的重映射。这一步完成后，普通 Trie 就可以丢弃了。接下来为每个状态计算 fail 指针，用 BFS 逐层扫描双数组状态，保存在 fail 数组中。

匹配期就简单了：输入一段文本，逐个 rune 转移状态。每次转移失败就跳到 fail，直到能转移或回到根。如果在某个状态有输出（以某个词结尾），就把这个输出收集起来。整个匹配过程不涉及任何 map 查找和内存分配，纯数组访问。

我要强调一点：Go 里 rune 是 int32，字符编码是 UTF-8，双数组计算下标的时候直接用 rune 数字参与运算，中文词完全没问题。

3. 核心实现：手写一个省内存的 AC 自动机

如果说前面是理论基础，那这一章就要动真格的了。我会把关键结构体、构建流程和匹配流程都写出来，并解释每一步为什么这么写。

3.1 数据结构定义

先定义核心结构体。双数组 AC 自动机只需要四个主要切片，整体内存占用非常可控。

type DoubleArrayAC struct { base []int32 check []int32 fail []int32 output []int32 // 每个状态上挂的输出索引，-1 表示没有 dict [][]byte // 实际词条存储，按 output 索引 root int32 }

base、check 是整个双数组的核心。fail 和 output 都是跟状态一一对应的数组，状态 s 有没有输出，直接看 output[s] 是不是 -1。为了省内存，我没有把每个状态的输出词条列表直接挂上，而是只在状态有“某个完整匹配词结尾”时记录一个 output ID。如果这个词的 fail 链上还有其它输出，匹配时再沿 fail 链去收集。这样虽然匹配时多一点跳转，但内存省了很多。

这里说明一下为什么 output 用 int32 而不是 slice：如果每个状态都挂一个 []int32，每个切片就是 24 字节，状态一多，内存立刻爆掉。用一个定长 int32 数组，每个状态只占 4 字节，代价是拿匹配时沿 fail 链回溯的开销换内存。

3.2 普通 Trie 构建与导入

构建双数组前，我先把词条建到一个临时 Trie 里，因为这能简化后续的子节点枚举。

type trieNode struct { child map[rune]*trieNode end bool }

这里故意用 map，是因为只是构建期临时结构，构建完就会 GC 掉。即便临时内存很大，峰值也还能接受。当然，如果词表大到连临时内存都吃不消，可以分批导入，但我在实际项目里，一次性导入也就多花了十几秒构建时间，无所谓。

导入阶段，对每个词条按 rune 拆分，依次遍历创建节点。词条的存储形式我改成了 [][]byte，方便后续匹配时输出实际命中的词。这里有个小优化：词条去重。很多词表里会混入重复词条，导入前先做一次去重，可以省不少临时内存和后续输出空间。

3.3 base 分配与子节点转移

这是构建双数组的核心，也是最容易出 bug 的地方。基本思路就是从根状态开始，按 BFS 顺序处理每个状态，把这个状态的所有子节点放到双数组的合适位置。

实际实现时有一个很大的坑：如果按深度从小到大处理，每层分配 base 时，都要检查新子节点位置是否和已有位置冲突。Go 的切片动态扩容只能用 append，但我这里需要随机写下标。所以我预先分配一个足够大的数组，预估节点数上限。

func (d *DoubleArrayAC) buildDoubleArray(root *trieNode) { d.base = make([]int32, 0, maxState) d.check = make([]int32, 0, maxState) d.root = 1 d.base[d.root] = 1 d.check[d.root] = 0 queue := []int32{d.root} trieQueue := []*trieNode{root} for len(queue) > 0 { s := queue[0] ts := trieQueue[0] queue = queue[1:] trieQueue = trieQueue[1:] // 收集子节点 rune 列表 children := make([]rune, 0, len(ts.child)) for ch := range ts.child { children = append(children, ch) } if len(children) == 0 { continue } // 寻找一个 base[s]，使得所有 child[ch] 的位置不冲突 baseVal := d.findBase(children) d.base[s] = baseVal for _, ch := range children { t := baseVal + int32(ch) d.check[t] = s childNode := ts.child[ch] if childNode.end { d.output[t] = d.addWordToDict(...) } queue = append(queue, t) trieQueue = append(trieQueue, childNode) } } }

findBase 的实现核心是：从某个起始值开始，判断每个子节点 c 对应的位置 base+c，如果 check[base+c] 不为 0 且不等于当前状态，则说明冲突，base 再加 1 继续。

func (d *DoubleArrayAC) findBase(s int32, children []rune) int32 { base := d.base[s] if base == 0 { base = 2 } for { ok := true for _, ch := range children { t := base + int32(ch) if t >= int32(len(d.check)) { d.grow(max(t+1, int32(len(d.check)*2))) } if d.check[t] != 0 && d.check[t] != s { ok = false break } } if ok { return base } base++ } }

这地方有两层优化。第一，起始 base 值可以复用当前状态的 base，不要每次从 2 开始找，这样能减少搜索长度；第二，grow 需要一次性扩容到位，减少多次扩容带来的搬迁开销。

3.4 fail 指针与输出合并

构建完双数组后，下一步是计算 fail。这个逻辑和普通 AC 自动机一模一样，但因为是数组状态，写起来更直接。

func (d *DoubleArrayAC) buildFail() { d.fail = make([]int32, len(d.base)) queue := make([]int32, 0, len(d.base)) // 根的所有子节点 fail 指向根 for ch := int32(0); ch < 65536; ch++ { t := d.base[d.root] + ch if int(t) < len(d.check) && d.check[t] == d.root { d.fail[t] = d.root queue = append(queue, t) } } for len(queue) > 0 { s := queue[0] queue = queue[1:] for ch := int32(0); ch < 65536; ch++ { t := d.base[s] + ch if int(t) < len(d.check) && d.check[t] == s { f := d.fail[s] for f != d.root && d.check[d.base[f]+ch] != f { f = d.fail[f] } if d.check[d.base[f]+ch] == f { d.fail[t] = d.base[f] + ch } else { d.fail[t] = d.root } queue = append(queue, t) } } } }

这段实现里有个性能隐患：遍历 ch 从 0 到 65535，是为了覆盖所有 Unicode 字符。但因为双数组的稀疏性，大部分位置的 check 都不等于 s，所以循环很快。实际测试中，构建阶段这个循环是最耗时的，但构建一次性完成，不影响运行。更好的做法是构建期额外记录每个节点的子节点列表，这样就能精确遍历，不用扫描 65535 次，我在后面的版本里改成了这个方案，速度提升明显。

关于输出合并，我采用的策略是这样的：状态 s 本身是词尾，则记录 output[s] = 词条ID；否则 output[s] = -1。匹配时如果命中状态 s，需要沿 fail 链收集所有 output（因为这些后缀也是词）。当然，为了运行时更快，也可以在构建 fail 时把后缀输出合并到当前状态，但那样 output 数组就不知道用 int32 够不够了，因为一个状态可能对应多个词条结尾。为了省内存，我放弃了快速合并，换成了运行时的 fail 回溯。

这个过程，从实现角度来说并不复杂，但很多细节需要小心，比如 findBase 的冲突检测，以及 fail 构建里循环退出的边界条件。

4. 匹配流程细节与性能实测

构建好了双数组 AC 自动机，匹配就简单了。但我还是把匹配流程的细节写清楚，并放出对比数据，让大家看到“省内存”到底省在哪，性能有没有下降。

4.1 逐 rune 匹配与 fail 回溯

匹配的核心逻辑如下：

func (d *DoubleArrayAC) Match(text []byte) [][]byte { var res [][]byte state := d.root for _, r := range text { // 尝试转移 for state != d.root { t := d.base[state] + int32(r) if t < int32(len(d.check)) && d.check[t] == state { state = t break } state = d.fail[state] } // 根状态特殊处理 if state == d.root { t := d.base[d.root] + int32(r) if t < int32(len(d.check)) && d.check[t] == d.root { state = t } } // 收集输出 for s := state; s != d.root; s = d.fail[s] { if d.output[s] != -1 { res = append(res, d.dict[d.output[s]]) } } } return res }

这里有个细节必须提到：从当前状态 s 出发找字符 r 的转移，如果 base[s]+r 的位置 check 不等于 s，就说明这个状态没有对应子节点，需要跳 fail。这段代码直接内联在 for 循环里，没有用函数调用，能省不少开销。

还有个细节：对于根状态，一定要单独处理。因为根没有 fail，或者 fail 就是自己，如果照常走循环，容易造成死循环。所以代码里先处理非根状态，再单独看根状态是否可以直接转移。

输出收集那段，有个可以优化的地方。如果词表里没有互相包含的情况（比如“中国”和“中国人民”同时存在），那匹配时沿 fail 回溯就没有必要。但如果词表里有互相包含，这段是必要的。实际场景里敏感词经常互相包含，比如“代开发票”和“发票”，所以这段代码不能省。

4.2 内存占用对比：从 30GB 到 5GB

这一节放一些我本机的实测数据。测试环境是 16 核 CPU、64GB 内存、Go 1.22。词表构成：常用敏感词（约 5 万条）+ 大量生成的组合变体（约 900 万条），总词条约 905 万条，原始文件大小约 1.6GB。

我分别实现了两个版本。第一个版本是标准 map 版：Trie + map[rune]*Node + fail 指针，这是很多开源库的做法。第二个版本就是本文说的双数组版。

结果如下：

从数据可以看出，双数组版本的内存只有原版的 15% 左右，同时构建时间缩短不少，因为省了大量的 map 插入与哈希计算。匹配速度几乎没有变化，甚至略快，主要得益于数组访问的 CPU 缓存友好性。

有个小细节是，我在构建双数组时，临时 Trie 的内存峰值也很高，GC 后会被回收。所以最终运行时内存是 5GB 左右。如果你对峰值敏感，可以分批构建。但实际服务中，构建往往是一次性的，运行期才是关键。

4.3 状态数与词表规模的关系

这里再聊一个大家容易忽略的问题：AC 自动机状态数不一定等于词条数，而是等于所有词条的字符数之和（确切说，是去重后所有不同前缀和后缀的状态数）。GB 级词表意味着字符数可能达到 10 亿以上，状态数通常在几百万到几千万之间。

我用 int32 存 base 和 check，理论上限是 21 亿个状态，完全够用。如果词表真的要逼近 20 亿状态，那 base/check 就要考虑 int64，内存也会翻倍。目前我的场景用 int32 足够。

这里给个经验公式：一个 1GB 的纯文本词表，平均词长 10 个字符，大约有 1 亿个字符，状态数大致在千万级别。用双数组表示，base/check/fail/output 四个数组，每个状态 16 字节，大概需要 160MB 到 200MB。剩下的内存主要是 dict 里实际词条文本的存储。这个比例已经非常健康。

4.4 为什么 Go 里用 int32 而不是 int

这算一个纯 Go 层面的优化心得。Go 的 int 是 64 位的，虽然是 8 字节。同样一个数组，用 int32 能省一半内存。注意数组下标访问时，Go 会自动把 int32 转成 int，这会有一次类型转换，但在现代 CPU 上几乎无感知。

我用 int32 还有一个原因：base 和 check 的下标计算有可能会超过 int32 范围吗？在 1 亿状态量级下，不可能。既然不可能，用更小的类型省内存就是合理选择。如果你觉得转换麻烦，也可以用 uint32，效果一样。

5. 踩坑记录与调优细节

这一章我按时间线把实现过程中踩过的坑列出来，很多都是测试时才发现的问题，希望你能少走弯路。

5.1 findBase 死循环

这是我最开始遇到的一个 bug。findBase 每次从固定起始值开始查找，遇到大状态、大字符集时，base 可能一直 +1，直到超出 int32 范围或者数组被 grow 到极大才停。虽然理论上不会死循环，但构建时间会爆炸。

后来我把起始值改成当前状态的 base 值，而不是固定值。另外，如果 base 搜索超过一定阈值，我会把该状态的所有子节点按字符从小到大排序，用一种贪心策略直接分配相邻区间，大幅降低冲突检测次数。实测下来构建时间缩短一半以上。

5.2 Unicode 字符作为偏移量的问题

千万别忽略这个：UTF-8 文本在 Go 里按 rune 遍历，rune 是 int32。中文的 rune 值通常在 0x4E00 到 0x9FA5 之间，参与 base 计算时，t = base[s] + int32(ch) 这个 t 可能是一个很大的数。所以数组初始长度不能太小，还有 grow 的步长也要合理。

最简单的方式：先预估状态数上限，然后 base/check 预先按最大可能值申请，避免频繁扩容。如果不知道最大值，可以先构建普通 Trie，数一下节点数，再申请对应大小的双数组。这个在构建期做，不会有性能问题。

5.3 fail 数组越界

另一个坑是 fail 构建时的越界。因为双数组是稀疏的，base[s]+ch 可能大于当前 len(check)。在普通 Trie 中，你可以直接判断子节点是否存在。但在双数组里，必须先把 t 和 len(check) 比较，否则很容易 panic。我在代码里加了条件，t < int32(len(d.check))，就稳了。

还有一个隐藏 bug：如果 check[t] 等于 0 但 t 已经超过数组长度，访问直接越界。所以 grow 的时候，我故意多扩展一些空间，减少这种边界判断的次数。

5.4 Go 的 GC 对大对象的影响

当 base 和 check 都是 GB 级切片时，Go GC 会扫描这些大对象。虽然切片内部只是指针，但 GC 每次扫描仍然会有一定耗时。实测 5GB 内存状态下，GC 的 Pause 从原来的 10ms 左右涨到了 30ms 左右。这个会导致服务响应偶尔卡顿。

解决方案有两个思路。一是把 base/check/fail 这些核心数组用[]int32直接持有，不要让它们在每次 GC 时被重新分配；二是尽量复用同一个对象提供服务，避免频繁加载和卸载。我们采用的方式是：构建完成后，立刻调用runtime.GC()，把构建期临时对象都清理掉，同时用debug.SetGCPercent(-1)关闭后续 GC（因为匹配期几乎不产生新对象，GC 并没有太多实际作用）。这样服务 GC 停顿直接归零。

当然，这种做法只适合匹配期无内存分配的场景。如果匹配时需要收集大量输出结果，还是要给结果切片预留 buffer，避免频繁分配。

5.5 有没有可能继续压缩内存

如果 5GB 还嫌多，可以继续压缩。我这边想到的方向有三个：

• 把 check 数组压缩成 uint32，base 用 int32，这可以再省一部分。但要注意 base 值的范围，可能得确保 base 不超过 21 亿。
• 把 output 和 fail 合并成一个结构体，用位运算打包。状态编号和输出编号都可以压进 64 位里，这样每个状态又少 4 字节。
• 对高频中文词做编码压缩，比如把常用 3000 汉字映射到 uint16，缩小字符偏移量。

但这些都会增加代码复杂度。我的经验是，如果内存已经压到 5GB 且服务能稳定运行，没必要为了省那几百 MB 把可维护性搭进去。先上线，等数据量真的大了，再考虑更极致的压缩。

6. 常见问题速查与匹配测试

为了让这篇文章更有实操参考价值，我把从零构建到上线的过程中最常被问到的几个问题整理成一个速查表，覆盖了选型、构建、匹配、调优这几个阶段。

这表里的前三个问题，是最多人会遇到的。特别是漏词问题，我见过很多 AC 自动机的实现，fail 构建错了，导致“中国人民”匹配了“中国”但漏了“人民”。我建议你在写完代码后，准备一组互相包含的词条做测试，把 fail 链打出来，逐步比对，这是最快定位问题的方式。

7. 代码测试与压测样本

这章节补一个经验性的测试方案。因为我发现很多同学在本地写完后，不知道怎么科学地压测，或者说压测素材选得不对。

7.1 用规律变体词造一个 100 万级的测试词典

测试 GB 级词库没必要真的去下载 1GB 词表，可以自己生成。我用的是规律变体词，把一些基础词和前后缀组合，瞬间膨胀到几百万条。这种方式还能测试 AC 自动机的 fail 链是否正确。

func generateDict(baseWords []string, prefix []string, suffix []string) []string { // 全量组合生成 }

一万个基础词乘以 100 个前缀再乘以 10 个后缀，就是一千万词条。生成后的文本写出来大约几百 MB，足够压测了。

7.2 匹配性能压测要点

压测时要注意两点。第一，输入文本里应该同时混有命中和未命中内容。如果全部命中，状态会经常停留在较深的位置，输出收集逻辑可能成为热点；如果全部不命中，则主要测 fail 跳转的代价。两者都不能偏颇。第二，压测完记得用 go tool pprof 看火焰图，确认瓶颈是不是在输出收集上。

我自己压测时发现，如果命中率很高，output 收集会占用 40% 以上的 CPU 时间。这时候可以考虑为高频输出做缓存，比如把输出结果直接挂在状态上，而不是沿 fail 链走。但这样内存又会上升，所以是 trade-off，得根据实际场景取舍。

7.3 一个完整的 sanity check 用例

这里给一个我日常用的 sanity check 用例，代码很短，但是能覆盖绝大多数边界。

func TestMatchSanity(t *testing.T) { words := []string{"中国人", "中国人民", "人民", "共和", "共和国"} ac := BuildDoubleArrayAC(words) text := "中国人民共和国" got := ac.Match([]byte(text)) // 期望匹配到：中国人、中国人民、人民、共和、共和国 // 这个用例用来验证 fail 链和输出收集 }

如果你的实现能把上面 5 个词都查出来，基本就说明核心逻辑没问题了。

8. 写在最后，一个真实的工程体会

如果你只是想在项目里用 AC 自动机跑几万条词库，那标准 map 版完全够用，没必要折腾双数组。但如果你面对的是 GB 级词表、几百 MB 甚至 GB 级内容需要实时过滤的话，双数组 AC 自动机带来的内存收益是非常值得的。

我自己在这个项目里最深的体会是：很多算法结构在理论课上听起来都不难，但一落到工程里，真正的成本往往不在算法本身的逻辑，而在数据表示方式。AC 自动机把时间复杂度优化到了 O(n)，但如果你用 map 去存储 Trie，空间复杂度爆炸，最终服务根本启动不起来。换成紧凑的双数组表示，同样的算法，占用的内存直接降了一个量级。这种优化，比微调几个 if 判断要有效得多。

另外，Go 语言在这类内存敏感场景里，其实比很多人想象中要更合适。切片底层连续内存，配合 int32 类型的紧凑数组，可以写出非常接近 C 语言层面的内存布局。虽然 Go 有 GC，但只要在构建期控制好对象生命周期，运行期完全可以做到零分配、零 GC，性能并不比 C++ 差多少。

如果你也在折腾大词表匹配，建议先别急着引入什么重型中间件，先把 AC 自动机的数据结构选型吃透，说不定问题直接就解决了。