从布隆过滤器到 AC 自动机：一个敏感词过滤工具的重写笔记
从布隆过滤器到 AC 自动机：一个敏感词过滤工具的重写笔记 前段时间在做 AI 流式输出的内容审核，需要一套敏感词检测方案。本来想找个现成的库直接用，但后来还是决定自己写一遍——主要是想把里边的原理摸透。这篇文章算是把整个思考过程、踩过的坑和最终的实现串起来，做个记录。 一开始的想法：布隆过滤器 + 词库匹配 第一反应是搞个布隆过滤器。这东西内存占用小，判断“肯定不存在”极快，拿来当第一道筛子很合适。 我很快写了个简单的布隆过滤器，用 MD5 做哈希，加上几个不同的盐值，凑出 k 个哈希函数。然后把敏感词库全塞进去。对于一段文本，如果布隆说过滤器认为“肯定不包含敏感词”，那就直接放行；如果说“可能存在”，再交给后端的精确匹配（比如一个 HashMap 词库）去验证。 测试下来，安全文本的过滤效率确实很高。但我很快就发现了一个致命问题——流式输出。 流式场景下的尴尬 AI 生成内容是逐字往外吐的。假设敏感词是 ab，第一个片段只来了 "a"，第二个片段来了 "b"。如果对每个片段单独过布隆过滤器，"a" 不在词库里，放行；"b" 也不在，放行。结果 "ab" 就这么漏过去了。 这个问题不是布隆过滤器独有的。任何无状态的、逐片段独立检测的方案都绕不开。要解决它，必须让检测器记住“刚才已经看到了一个 a，再等等看后面有没有 b”。 也就是说，我需要一个有状态的匹配器。 AC 自动机的救场 后来想起来大学时学过的一个算法——AC 自动机。这东西本来就是为了解决“一次扫描，匹配多个模式串”的问题。而且它天生可以维护状态：匹配完一个片段后，记住当前走到了 Trie 树的哪个节点，下一个片段来了接着往下走。 AC 自动机的结构其实不复杂： 先把所有敏感词建一棵 Trie 树。 然后用 BFS 给每个节点补一条失败指针（fail）。失败指针的作用是，当在当前节点匹配不上下一个字符时，应该跳到哪个节点继续匹配——有点像 KMP 的 next 数组，但搬到了树上。 匹配时，拿着文本的每个字符沿着树往下走，走不通就顺着 fail 跳，走到有输出的节点就记下来。 这个过程是严格 O(n) 的，跟敏感词数量无关。流式场景下，只需要在每次处理完一个片段后把当前节点存下来，下一个片段来了接着用。 我写了一个普通的 AC 自动机实现，用 HashMap 存子节点，结构清晰，调试也方便。对于十万级别的词库，内存占用几十 MB，完全能接受。 分片测试 用之前的例子：敏感词 ["ab", "bc"]，分三次喂入 "a"、"b"、"c"。 第一次 "a"：状态从根走到节点 a，没有输出。 第二次 "b"：从节点 a 走到 ab，输出 "ab"。同时因为 ab 的 fail 指向第一层的 b 节点，而 b 节点本身没有输出，所以只输出一个词。 第三次 "c"：当前节点是 ab，没有 c 子节点，于是顺着 fail 跳到 b，发现 b 有子节点 c，走过去到达 bc，输出 "bc"。 完美。跨片段的 "ab" 和 "bc" 都抓到了。 ...