做内容安全这块或多模式匹配相关的同学大概都躲不过 AC 自动机。前阵子我接到一个需求要把一份 GB 级的敏感词词表具体多少条就不透露了反正几十亿个字符编译成匹配引擎服务内存还不能爆响应还得在毫秒级。一开始我的想法很简单Go 标准库撸一个 Trie节点用 map 存子节点AC 自动机的 fail 指针一挂完事。结果词表切分灌入之后内存直接飙到几十个 GB服务连启动都费劲。老实说那会儿我才意识到AC 自动机虽然理论成熟但在海量词库场景下实现方案选不对内存就是无底洞。后来我换了个思路用双数组 TrieDouble-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 对应的位置 basec如果 check[basec] 不为 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(t1, 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 指针这是很多开源库的做法。第二个版本就是本文说的双数组版。结果如下方案内存占用构建时间匹配速度约 10MB 文本标准 map 版 AC31.2GBOOM 边缘约 3 分钟约 200ms双数组 ACint325.4GB约 85 秒约 180ms双数组 ACint32 输出索引优化4.8GB约 78 秒约 190ms从数据可以看出双数组版本的内存只有原版的 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 数组压缩成 uint32base 用 int32这可以再省一部分。但要注意 base 值的范围可能得确保 base 不超过 21 亿。把 output 和 fail 合并成一个结构体用位运算打包。状态编号和输出编号都可以压进 64 位里这样每个状态又少 4 字节。对高频中文词做编码压缩比如把常用 3000 汉字映射到 uint16缩小字符偏移量。但这些都会增加代码复杂度。我的经验是如果内存已经压到 5GB 且服务能稳定运行没必要为了省那几百 MB 把可维护性搭进去。先上线等数据量真的大了再考虑更极致的压缩。6. 常见问题速查与匹配测试为了让这篇文章更有实操参考价值我把从零构建到上线的过程中最常被问到的几个问题整理成一个速查表覆盖了选型、构建、匹配、调优这几个阶段。常见问题可能原因排查方法构建期内存峰值过高临时 Trie 的 map 节点太多改用迭代构建分批导入临时节点用完后手动置 nil匹配结果漏词fail 构建逻辑有误输出收集只查了 output[s] 没沿 fail 回溯打印每个状态转移和 fail 链用极小词表验证匹配变慢每次转移都沿 fail 回溯太多输出收集里大量 append把 fail 回溯改成“转移失败时再回溯”输出收集用预分配 slice错误地把 rune 当成 byte 处理base 偏移量算错或下标越界用 range text 遍历 rune不要用 text[i]构建时间太长findBase 选择劣化冲突检测次数过多改用子节点排序用动态 base 起始值必要时用启发式分配GC 停顿影响服务构建后未及时释放临时大对象构建完成后调用 runtime.GC()必要时关闭 GC这表里的前三个问题是最多人会遇到的。特别是漏词问题我见过很多 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 自动机的数据结构选型吃透说不定问题直接就解决了。