下图是一个完整的文本审核流程,包括名单匹配、敏感词匹配、AI 机器审核、人工审 核四个环节。待审核文本需要顺次通过名单匹配、敏感词匹配、AI 机器审核三个流程, 若结果为嫌疑则需要人工审核,否则将直接给出确定的结果。
敏感词匹配功能可以迅速地匹配文本中的敏感词汇,算法平均耗时为 50ms,因其简单、 快速、直接、灵活的特点,成为了审核人员对抗垃圾文本的利器。然而身处信息爆炸时 代的网民们非常“优秀”,他们源源不断的发明各种新词、谐音词来绕过敏感词检测。
例如某些用户会使用“啋票”、“采漂”等词汇来规避敏感词“彩票”,其中“啋票” 不仅是谐音词,还包含多音字,常规的模式匹配算法很难保证完全命中。这不仅给运营 规则带来挑战,也对匹配算法的精准度、漏杀率提出了要求。
1.算法选型
敏感词匹配功能依托于模式匹配算法。模式匹配的定义是,给定一个子串,在某个字符 串中找出与该子串相同的所有子串。其中给定的子串被称为模式串,被匹配的字符串被 称为目标串。基于多个模式串进行匹配的算法被称为多模式匹配算法,目前成熟的多模 式匹配算法有 AC 自动机和 WM
业务需求:
1)词库量大,需要维护和加载百万级别的词库(模式串)
2)敏感词与业务特性、国家政策相关性强,无法统一约定长度、前缀等特征
WM 算法对模式串的长度和前缀存在一定的要求,可能会影响业务的使用。虽然 AC 自 动机加载耗时长,内存占用大,但敏感词加载并不频繁,且服务器内存资源充足,所以 我们最终选用 AC 自动机作为底层算法
2.实现步骤
构建 Trie 树:将所有敏感词插入到 Trie 树中,形成字典树的结构。
构建失败指针:使用广度优先搜索(BFS)为 Trie 树中的每个节点设置失败指针,确保可以在文本中快速找到下一个匹配点。
文本过滤:使用 AC 自动机在文本中快速匹配敏感词,并将敏感词替换为指定字符(如 *)。
2.1.构建构建 Trie树
// AC算法节点类 class ACNode { Map<Character, ACNode> children; // 子节点集合 ACNode fail; // 失败指针 boolean isEnding; // 是否为模式串结尾 int length; // 敏感词的长度 public ACNode() { this.children = new HashMap<>(); this.fail = null; this.isEnding = false; this.length = 0; // 默认为0 } } |
2.2 AC自动机类
//AC算法类 public class AhoCorasick { private ACNode root; // 根节点 public AhoCorasick() { this.root = new ACNode(); } // 添加敏感词到AC自动机中 public void addWord(String word) { ACNode current = root; for (char c : word.toCharArray()) { if (!current.children.containsKey(c)) { current.children.put(c, new ACNode()); } current = current.children.get(c); } current.isEnding = true; current.length = word.length(); // 记录敏感词的长度 } // 构建AC自动机的失败指针 public void buildFailurePointer() { Queue<ACNode> queue = new LinkedList<>(); root.fail = null; queue.offer(root); while (!queue.isEmpty()) { ACNode current = queue.poll(); for (char c : current.children.keySet()) { ACNode child = current.children.get(c); if (current == root) { child.fail = root; } else { ACNode failTo = current.fail; while (failTo != null) { if (failTo.children.containsKey(c)) { child.fail = failTo.children.get(c); break; } failTo = failTo.fail; } if (failTo == null) { child.fail = root; } } queue.offer(child); } } } // 敏感词过滤 public List<String> filter(String text) { List<String> sensitiveWords = new ArrayList<>(); ACNode current = root; for (int i = 0; i < text.length(); ++i) { char c = text.charAt(i); while (!current.children.containsKey(c) && current != root) { current = current.fail; } if (current.children.containsKey(c)) { current = current.children.get(c); } else { current = root; } if (current.isEnding) { // 发现敏感词,记录匹配到的敏感词 sensitiveWords.add(text.substring(i - current.length + 1, i + 1)); } } return sensitiveWords; } |
2.3.测试
public static void main(String[] args) { AhoCorasick ac = new AhoCorasick(); // 添加敏感词 ac.addWord("敏感词1"); ac.addWord("敏感词"); ac.addWord("敏感词3"); // 构建失败指针 ac.buildFailurePointer(); // 测试过滤文本 String text = "这是一个测试,包含敏感词1和敏感词3,但是敏感词2不在里面。"; List<String> sensitiveWords = ac.filter(text); System.out.println("敏感词列表:" + sensitiveWords); } } |
执行结果:
敏感词列表:[敏感词, 敏感词1, 敏感词, 敏感词3, 敏感词] |