[转*摘要*总结]敏感词过滤的算法原理之DFA算法

article/2025/9/23 17:57:13

问题背景

敏感词、文字过滤是一个网站必不可少的功能，过滤的关键是用户输入内容与敏感字库的匹配。
对于字符串匹配，一般的方法是字符串子串包含判断、正则表达式判断，但对于用户输入的大量内容，它们的效率是非常低的。Google和百度搜索文字过滤算法时我找到了一个比较好的算法DFA算法。

实际项目中，对于整句的匹配我们采用的仍是正则表达式，因为整句词库比较少；对于单词屏蔽，我们采用的是DFA算法来处理，因为单词字库是万级以上的，DFA算法简单高效。

DFA算法简介

DFA即Deterministic Finite Automaton，也就是确定有穷自动机，它是是通过event和当前的state得到下一个state，即event+state=nextstate，因为只有状态的变化，没有过多的运算，所以DFA很高效。

DFA算法处理敏感词过滤的核心就是：将关键词转换成一个个类似下图的敏感字树用于搜索匹配。

敏感词：日本人、日本鬼子、日本男人
对应敏感词树结构：
在这里插入图片描述

搜索时：由于我们将敏感词库构建成了一个类似上图的一颗一颗的树，这样我们判断一个词是否为敏感词时就大大减少了检索的匹配范围。比如我们要判断日本人，根据第一个字我们就可以确认需要检索的是那棵树，然后再在这棵树中进行检索。

java实现DFA算法（HashMap版）

Step1. 构建敏感词搜索树

    @SuppressWarnings({ "rawtypes", "unchecked" })private void addSensitiveWordToHashMap(Set<String> keyWordSet) {sensitiveWordMap = new HashMap(keyWordSet.size());     //初始化敏感词容器，减少扩容操作String key = null;  Map nowMap = null;Map<String, String> newWorMap = null;//迭代keyWordSetIterator<String> iterator = keyWordSet.iterator();while(iterator.hasNext()){key = iterator.next();    //关键字nowMap = sensitiveWordMap;for(int i = 0 ; i < key.length() ; i++){char keyChar = key.charAt(i);       //转换成char型Object wordMap = nowMap.get(keyChar);       //获取if(wordMap != null){        //如果存在该key，直接赋值nowMap = (Map) wordMap;}else{     //不存在则，则构建一个map，同时将isEnd设置为0，因为他不是最后一个newWorMap = new HashMap<String,String>();newWorMap.put("isEnd", "0");     //不是最后一个nowMap.put(keyChar, newWorMap);nowMap = newWorMap;}if(i == key.length() - 1){nowMap.put("isEnd", "1");    //最后一个}}}}

运行得到的hashMap结构如下：

{"五": {"星": {"红": {"isEnd": 0,"旗": {"isEnd": 1}},"isEnd": 0},"isEnd": 0},"中": {"isEnd": 0,"国": {"isEnd": 0,"人": {"isEnd": 1},"男": {"isEnd": 0,"人": {"isEnd": 1}}}}
}

Step2. 检查文本中的敏感词

    @SuppressWarnings({ "rawtypes"})public int CheckSensitiveWord(String txt,int beginIndex,int matchType){boolean  flag = false;    //敏感词结束标识位：用于敏感词只有1位的情况int matchFlag = 0;     //匹配标识数默认为0char word = 0;Map nowMap = sensitiveWordMap;for(int i = beginIndex; i < txt.length() ; i++){word = txt.charAt(i);nowMap = (Map) nowMap.get(word);     //获取指定keyif(nowMap != null){     //存在，则判断是否为最后一个matchFlag++;     //找到相应key，匹配标识+1 if("1".equals(nowMap.get("isEnd"))){       //如果为最后一个匹配规则,结束循环，返回匹配标识数flag = true;       //结束标志位为true   if(SensitivewordFilter.minMatchTYpe == matchType){    //最小规则，直接返回,最大规则还需继续查找break;}}}else{     //不存在，直接返回break;}}if(matchFlag < 2 && !flag){     matchFlag = 0;}return matchFlag;}

补充：中文汉字的繁简体转换工具包opencc4j

opencc4j是一个我们实际用过值得推荐的一个繁简体转换工具包，之前我们在也有用过一些通过繁简体组成的字典Map来进行转换的方案，但都出现了漏词、转换失败的问题，原因是字典不全等原因。

opencc4j使用很简单：
step1：maven 引入

<dependency><groupId>com.github.houbb</groupId><artifactId>opencc4j</artifactId><version>1.0.2</version>
</dependency>

step2：直接使用ZhConverterUtil静态方法

// 简体转繁体：
String original = "为中华之崛起而读书";
String result = ZhConverterUtil.convertToTraditional(original);
// result：為中華之崛起而讀書// 繁体转简体：
String original = "為中華之崛起而讀書";
String result = ZhConverterUtil.convertToSimple(original);
// result：为中华之崛起而读书