评论、昵称、弹幕系统上线后，敏感词过滤很快会撞上两堵墙：词库涨到几万后逐词扫描拖垮接口，用户用同音字和符号穿插轻松绕过匹配。前者靠 DFA/AC 自动机解决，后者靠归一化与词库运营对抗。

核心问题：多模式字符串匹配

敏感词过滤的技术本质是多模式匹配——在一段文本里同时查找几万个关键词。暴力做法是每个词扫一遍文本，复杂度 O(词数 × 文本长度 × 词长)，万级词库下延迟直接到秒级，不可用。优化方向只有一个：让所有词共享一次扫描。

DFA：Trie 树驱动的确定有限自动机

DFA（Deterministic Finite Automaton，确定有限自动机）是工业界敏感词过滤最常见的实现，底层是一棵 Trie 树（字典树）：

  • 每个节点代表一个状态，每条边代表一个字符转移；
  • 从根到某节点的路径拼起来就是一个前缀，路径终点的标记表示”到这里构成一个完整敏感词”；
  • 词库中所有词的公共前缀只存一份——“东京热”和”东京冷”共享”东京”两个节点。

匹配过程是确定性的状态机运转：指针从文本每个位置出发，沿 Trie 逐字符向下走，走不动就停止，途中踩到终止节点就记一次命中。状态只由当前节点和输入字符决定，没有分支犹豫，所以叫”确定”有限自动机。它的复杂度约为 O(文本长度 × 最长词长)，与词库规模基本无关——这就是它比暴力匹配快几个数量级的原因。

词库：东京热 / 东京冷 / 高清

根 ──东──京──热(终)
        └──冷(终)
  └──高──清(终)

DFA 与 AC 自动机的差异

DFA（Trie）有一个短板：匹配失败后要从文本下一个位置重新从根出发。在文本 "ushers" 中找 "she" 和 "he"：从位置 1 出发命中 she 后，还得回到位置 2 再走一遍才找到 he，最坏情况退化成 O(L × m)。

AC 自动机（Aho-Corasick）在 Trie 之上为每个节点加了一条 fail 指针，指向”当前已匹配串的最长后缀”所在的节点——思路和 KMP 的 next 数组一脉相承。失配时不回文本起点，而是沿 fail 链跳到下一个有希望的状态继续，整段文本只扫一遍，复杂度 O(L + 命中数)。代价是构建阶段要用 BFS 预处理 fail 指针，实现复杂度更高。

工程选型上：中小词库（万级以下）用 DFA 足够，Hutool 的 WordTree 开箱即用；大词库、高吞吐场景选 AC 自动机，配合双数组 Trie（Double-Array Trie）可把内存压到普通实现的两三成。

变体绕过与归一化对抗

算法再快，匹配的都是”字面”。真实的对抗发生在字符层面：

绕过手段 例子 对抗方式
符号插入 赌*博、赌-博 归一化时剔除标点与空白
谐音/拼音 “赌博”→”读博”、”dubo” 拼音转换 + 谐音词库
繁简混用 “台灣”→”台湾” 统一繁转简
全半角 abc→ａｂｃ NFKC 归一化
拆字/变形 “弓虽”、”氵去” 形近字库、人工运营
零宽字符 词间插不可见 Unicode 过滤 FORMAT 类字符

核心手法是归一化：匹配前对文本副本（不动原文）做大小写折叠、全半角统一、繁转简、去除格式控制字符，再在干净文本上跑 DFA。两个坑要留心：一是清洗改变了字符位置，若要在原文里高亮命中词，需维护清洗前后位置映射；二是归一化越激进误伤越多——删符号可能把两个正常词拼成敏感词，要用真实语料持续评估误报率。

对抗是长期的：词库要分级（直接拦截/替换脱敏/转人工）、要留命中日志供漏检分析，高风险场景最终还得靠模型识别与人工审核兜底，纯字符匹配解决不了一切。

开源实现与工程要点

常见选型：

  • Hutool DFA（Java）：轻量、API 简单，支持贪婪/密度匹配，中小规模词库首选。
  • ToolGood.Words（多语言）：内置繁简、全半角、拼音转换，Java 版可直接用。
  • AhoCorasickDoubleArrayTrie（hankcs）：AC 自动机 + 双数组 Trie，大词库高性能场景。

工程落地要点：

  1. 热更新：词库在线变更不能停服。用 AtomicReference 持有过滤器实例，后台构建好新 Trie 后原子切换，旧实例等 GC 回收。
  2. 不可变结构：构建完成的 Trie 不再修改，读线程免锁。
  3. 分段并行：超长文本切块并行匹配时，块间要保留”最长词长 - 1”的重叠区，否则跨边界的词会漏。
  4. 监控指标：关注匹配耗时 p99、命中率、词库更新失败率；加载失败要保留旧词库并告警，空词库不能静默放行。
  5. 超时策略：高风险内容匹配超时应拒绝或转人工，不能默认 fail-open。

小结

  • DFA 基于 Trie 树做确定性状态转移，复杂度与词库规模基本无关，是敏感词过滤的主流实现。
  • AC 自动机用 fail 指针消除文本回溯，单遍扫描匹配所有词，适合大词库高吞吐场景。
  • 字面匹配挡不住变体，归一化（繁简、全半角、去符号、拼音）是对抗核心，同时要用位置映射和误报评估控制副作用。
  • 工程上重点是原子热更新、不可变结构、分段重叠和监控告警。