敏感词过滤方案总结

敏感词过滤方案总结

敏感词过滤是许多系统中必不可少的安全功能，用于过滤色情、政治、暴力等相关词汇。本文总结了常用的敏感词过滤算法，包括Trie树、AC自动机和DFA算法，并提供了具体的实现代码和开源项目推荐。

算法实现

Trie 树

Trie 树（字典树）是一种用于字符串匹配的数据结构，常用于解决在一组字符串集合中快速查找某个字符串的问题。例如，浏览器搜索的关键词提示就可以基于 Trie 树来实现。

假设我们的敏感词库中有以下敏感词：

• 高清视频
• 高清 CV
• 东京冷
• 东京热

构造出来的敏感词 Trie 树如下图所示：

当要查找字符串“东京热”时，会将其切割成单个字符“东”、“京”、“热”，然后从 Trie 树的根节点开始匹配。可以看出，Trie 树的核心原理是通过公共前缀来提高字符串匹配效率。

Apache Commons Collections库中提供了Trie树的实现：

Trie<String, String> trie = new PatriciaTrie<>();
trie.put("Abigail", "student");
trie.put("Abi", "doctor");
trie.put("Annabel", "teacher");
trie.put("Christina", "student");
trie.put("Chris", "doctor");
Assertions.assertTrue(trie.containsKey("Abigail"));
assertEquals("{Abi=doctor, Abigail=student}", trie.prefixMap("Abi").toString());
assertEquals("{Chris=doctor, Christina=student}", trie.prefixMap("Chr").toString());

Trie 树是一种利用空间换时间的数据结构，占用的内存较大。实际工程项目中通常使用改进版的 Trie 树，例如双数组 Trie 树（DAT）。DAT 的内存占用极低，可以达到 Trie 树内存的 1%左右，在中文分词、自然语言处理等领域有广泛应用。

AC 自动机

Aho-Corasick（AC）自动机是一种基于 Trie 树的改进算法，由贝尔实验室的 Alfred V. Aho 和 Margaret J.Corasick 发明。AC 自动机使用 Trie 树来存放模式串的前缀，并通过失败匹配指针来处理匹配失败的跳转。

如果使用 DAT 来表示 AC 自动机，可以兼顾两者的优点，得到一种高效的多模式匹配算法。GitHub 上有开源的 Java 实现版本：AhoCorasickDoubleArrayTrie。

DFA

DFA（确定有穷自动机）是一种用于模式匹配的数据结构，与之对应的是 NFA（不确定有穷自动机）。Hutool 提供了 DFA 算法的实现：

WordTree wordTree = new WordTree();
wordTree.addWord("大");
wordTree.addWord("大憨憨");
wordTree.addWord("憨憨");
String text = "那人真是个大憨憨！";
// 获得第一个匹配的关键字
String matchStr = wordTree.match(text);
System.out.println(matchStr);
// 标准匹配，匹配到最短关键词，并跳过已经匹配的关键词
List<String> matchStrList = wordTree.matchAll(text, -1, false, false);
System.out.println(matchStrList);
//匹配到最长关键词，跳过已经匹配的关键词
List<String> matchStrList2 = wordTree.matchAll(text, -1, false, true);
System.out.println(matchStrList2);

输出结果：

大
[大, 憨憨]
[大, 大憨憨]

开源项目推荐

• ToolGood.Words：一款高性能敏感词检测过滤组件，支持繁体简体互换、全角半角互换、汉字转拼音、模糊搜索等功能。
• sensitive-words-filter：提供 TTMP、DFA、DAT、hash bucket、Tire 算法支持的敏感词过滤项目，支持文本的高亮、过滤、判词、替换等功能。