P58 项目场景面试：敏感词过滤怎么设计

面试题：用户发言/昵称/内容的敏感词过滤怎么实现？用什么数据结构？

1. 核心数据结构：Trie（前缀树）/ DFA 算法

敏感词过滤的主流实现是DFA（确定有限自动机），底层用 Trie 树：

敏感词：["赌博", "博彩", "菠菜"]

             根
            /  \
           赌    博
           |     |
           博    彩

扫描文本时沿树匹配，命中即替换/拦截。时间复杂度 O(n)（n 为文本长度），不随敏感词数量增长。

2. 完整流程

文本进来 → 预处理（大小写、简繁、全半角、拼音变形处理）
  → DFA/Trie 匹配
  → 命中：打码（**）或拦截
  → 命中记录上报（词、次数），用于优化词库

3. 工程化要点

① 词库管理

• 敏感词分级（政治/色情/广告/暴力），不同业务不同强度；
• 词库热更新：配置中心推送，内存中的 Trie 重建/增量更新，不重启；
• 命中规则支持通配（如"赌＊博"中间插字符）。

② 变体对抗

现实中会绕过：博 彩、博彩!、bócai、谐音。处理：

• 文本归一化（去空格/标点、大小写统一、繁简转换）；
• 拼音/谐音库；
• 图片、谐音词靠人工/模型兜底。

③ 性能

• Trie 匹配 O(n)，单次过滤毫秒级，可放在网关/评论服务前置；
• 高并发用本地内存 Trie（不查远程），词库更新异步同步；
• 文本过长截断/分块处理。

④ 多级方案

• 实时拦截：Trie/DFA（快、准、覆盖率靠词库）；
• 异步审核：AI 模型 + 人工（处理模糊、图片、上下文）；
• 黑名单/举报闭环。

4. 加分点

• 说出"为什么不用 HashMap 遍历敏感词"：词量大时 O(m×n) 太慢，Trie 一次扫描搞定；
• 提到**双数组 Trie（Double-Array Trie）**进一步省内存；
• 追问"删除敏感词"：Trie 动态删除即可，注意引用计数/子节点处理；
• 提到开源实现：ToolGood.Words、ho3e 等 DFA 敏感词库。

一句话总结

敏感词过滤用 Trie/DFA 自动机实现 O(n) 一次扫描匹配，词库分级 + 热更新，文本做归一化防变体；性能关键在本地内存匹配，再配合异步 AI/人工审核兜底。