屏蔽词库有哪些（用 DFA 实现敏感词屏蔽）
背景
最近广告平台接入了外部的 dsp，这就需要我们对外部 dsp 投放的广告进行竞品广告屏蔽，目前的做法是设置一个屏蔽词库，如果广告标题包含屏蔽词，就过滤掉该广告
DFA 介绍
一般敏感词屏蔽都用 DFA 实现，网上有些关于 DFA 的文章有点深奥，这里结合我的理解尽量简单的介绍下
词库
我们的词库如下
"小米手机","小米手环","华为手机","华为荣耀","荣耀手机","华为手表","小米","小米加步枪"
使用该词库构建一个 DFA 树，如下
从敏感词库构建 DFA 树
这个 DFA 树和一般树结构的不同之处：
上级节点到叶子节点用 Map 来映射而不是 List，Map 的 key 是敏感词的下一个字符
树的根节点是虚拟的一个节点，其取值没有意义，我用的是 * 号
每个节点有个标记表示该节点是否某个敏感词的最后一个字符，图上字符后有个句点的，就表示该节点是某个敏感词的最后一个字符
敏感词匹配
构建好 DFA 树后，就可以进行敏感词匹配了，基本思路就是逐个字符的遍历广告标题，每个字符在 DFA 树里查询是否存在叶子节点，这里需要有一个 DFA 节点的变量 node
如果 node 为空，则从树的根节点查询叶子节点，否则从 node 查询
查询到叶子节点后，将该叶子节点存储到 node，表示下一个字符从该叶子节点继续匹配；查询不到叶子节点，将 node 置为空
一旦叶子节点不为空，且当前节点的结束标记为 true，就表示敏感词匹配到了
这里有个关键，就是当前字符是否在匹配中：即已经命中了某个敏感词的前几个字符，但还没有走到结束字符，如果这个时候下个字符未命中，需要将该字符再从根节点做一次匹配，举例说明
广告标题为"华为小米"，词库不变
当遍历到"小"字时，此时是在匹配中状态，即已经在匹配"华为"但还未遇到结束符，此时"小"字已经取不到叶子节点了，那么必须从根节点再获取一次"小"字的叶子节点
代码
代码保存在 gitee 仓库，地址如下
https://gitee.com/refusea/dfa
可运行单元测试验证
后记
写出 DFA 过滤敏感词的代码并不难，反而是将 DFA 树以树状图的形式 "画" 出来有点费劲
相关文章：
相关推荐：