java 实现敏感词过滤DFA算法

1. 前言

敏感词文字过滤是一个网站必不可少的功能，如何设计一个好的、高效的过滤算法是非常有必要的。作为一般开发人员来说首先考虑的肯定是简单的匹配，这样是可以实现功能，但效率比较慢，在高级一点的就是正则表达式，比前一个好一点，但终究还是一丘之貉，非常遗憾，两种方法都不可取。当然，在我意识里没有我也没有认知到那个算法可以解决问题，但是百度知道，以下就是学习的DFA算法简单介绍和功能实现。

2. DFA算法来历

DFA全称为：Deterministic Finite Automaton,即确定有穷自动机。 其特征为：有一个有限状态集合和一些从一个状态通向另一个状态的边，每条边上标记有一个符号，其中一个状态是初态，某些状态是终态。 但不同于不确定的有限自动机，DFA中不会有从同一状态出发的两条边标志有相同的符号。

具体功能：

将敏感词汇保存在map中。对敏感词汇进行过滤，将敏感词变为“*”。对无意义符号进行忽略处理。 敏感词数据结构： { 王：{ isEnd: false 八：{ isEnd：false 蛋：{ isEnd：true } } } } 无意义符号数据结构： { "@":Null (空结构体) }

3. 上代码

封装工具类：

public class SensitiveWordUtil { /** * 敏感词匹配规则 */ private static final int MinMatchTYpe = 1; //最小匹配规则，如：敏感词库["我是人","我是人么"]，语句："你猜我是人么"，匹配结果：我是[我是人]么 public static final int MaxMatchType = 2; //最大匹配规则，如：敏感词库["我是人","我是人么"]，语句："你猜我是人么"，匹配结果：我是[我是人么] /** * 敏感词集合 */ private static HashMap sensitiveWordMap; /** * 初始化敏感词库，构建DFA算法模型 * * @param sensitiveWordSet set */ private static synchronized void init(Set<String> sensitiveWordSet) { sensitiveWordMap = new HashMap(sensitiveWordSet.size()); //初始化敏感词容器，减少扩容操作 String key; Map nowMap; Map<String, String> newWorMap; for (String s : sensitiveWordSet) { //迭代sensitiveWordSet key = s; //关键字 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 { newWorMap = new HashMap<>(); //不存在则，则构建一个map，同时将isEnd设置为0，因为他不是最后一个 newWorMap.put("isEnd", "0"); //不是最后一个 nowMap.put(keyChar, newWorMap); nowMap = newWorMap; } if (i == key.length() - 1) { nowMap.put("isEnd", "1"); //最后一个 } } } } /** * 判断文字是否包含敏感字符 * @param txt 要过滤的文章 * @param matchType 过滤规则 * @param list 脏词库 * @return */ public static boolean contains(String txt, int matchType, List<String> list) { if (sensitiveWordMap.size() <= 0){ System.out.println("开始初始化平台脏数据"); if (list.size() > 0){ Set<String> sensitiveWordSet = new HashSet<>(list); System.out.println("set: " + sensitiveWordSet); SensitiveWordUtil.init(sensitiveWordSet); System.out.println("初始化平台脏数据完成"); } System.out.println("初始化数据源未能获取到"); } boolean flag = false; for (int i = 0; i < txt.length(); i++) { int matchFlag = checkSensitiveWord(txt, i, matchType); //判断是否包含敏感字符 if (matchFlag > 0) { //大于0存在，返回true flag = true; } } return flag; } /** * 获取文字中的敏感词 * * @param txt 文字 * @return 敏感词 */ private static Set<String> getSensitiveWord(String txt, int matchType) { Set<String> sensitiveWordList = new HashSet<>(); for (int i = 0; i < txt.length(); i++) { int length = checkSensitiveWord(txt, i, matchType); //判断是否包含敏感字符 if (length > 0) { //存在,加入list中 sensitiveWordList.add(txt.substring(i, i + length)); i = i + length - 1; //减1的原因，是因为for会自增 } } return sensitiveWordList; } /** * 替换敏感字字符 * * @param txt 文本 * @param replaceStr 替换的字符串，匹配的敏感词以字符逐个替换，如 语句：你猜我是人么 敏感词：是人么，替换字符串：**，替换结果：你猜我*** * @return 敏感字字符结果 */ private static String replaceSensitiveWord(String txt, String replaceStr, int matchType) { String resultTxt = txt; Set<String> set = getSensitiveWord(txt, matchType); //获取所有的敏感词 Iterator<String> iterator = set.iterator(); String word; while (iterator.hasNext()) { word = iterator.next(); for (int i = 0; i < word.length() - 1; i++) { replaceStr += replaceStr; } resultTxt = resultTxt.replaceAll(word, replaceStr); } return resultTxt; } /** * 检查文字中是否包含敏感字符 * * @return 如果存在，则返回敏感词字符的长度，不存在返回0 */ private static int checkSensitiveWord(String txt, int beginIndex, int matchType) { boolean flag = false; //敏感词结束标识位：用于敏感词只有1位的情况 int matchFlag = 0; //匹配标识数默认为0 char word; Map nowMap = sensitiveWordMap; for (int i = beginIndex; i < txt.length(); i++) { word = txt.charAt(i); nowMap = (Map) nowMap.get(word); //获取指定key if (nowMap != null) { //存在，则判断是否为最后一个 matchFlag++; //找到相应key，匹配标识+1 if ("1".equals(nowMap.get("isEnd"))) { //如果为最后一个匹配规则,结束循环，返回匹配标识数 flag = true; //结束标志位为true if (SensitiveWordUtil.MinMatchTYpe == matchType) break; //最小规则，直接返回,最大规则还需继续查找 } } else break; //不存在，直接返回 } if (matchFlag < 2 || !flag) { //长度必须大于等于1，为词 matchFlag = 0; } return matchFlag; } /*public static void main(String[] args) { Set<String> sensitiveWordSet = new HashSet<>(); sensitiveWordSet.add("你妈"); sensitiveWordSet.add("有病"); //初始化敏感词库 SensitiveWordUtil.init(sensitiveWordSet); System.out.println("敏感词库的数量：" + SensitiveWordUtil.sensitiveWordMap.size()); String string = "我说你这孩子是不是有病，你妈的。"; System.out.println("准备检查的语句：" + string.length() + "个字"); //是否含有关键字 boolean result = SensitiveWordUtil.contains(string, SensitiveWordUtil.MaxMatchType); System.out.println("检查出了敏感词？" + result); //获取语句中的敏感词 Set<String> set = SensitiveWordUtil.getSensitiveWord(string, SensitiveWordUtil.MaxMatchType); System.out.println("语句中包含敏感词的个数为：" + set.size() + ",包含：" + set); //替换语句中的敏感词 String s = "*"; String filterStr = SensitiveWordUtil.replaceSensitiveWord(string, s, SensitiveWordUtil.MaxMatchType); System.out.println("001号已为你重新组织了你的语言：" + filterStr); }*/ }

调用方如下：

private boolean verification(String title) { List<String> list = JSON.parseArray((String) redisTemplate.opsForValue().get("curse:list"), String.class); /* * 参数一：是我们要检验的字符串 * * 参数二：是我们过滤的规则 * * 参数三：是我们的脏词库（这里我直接从redis取出了） */ return SensitiveWordUtil.contains(title, SensitiveWordUtil.MaxMatchType, list); }

4. 总结

我这里脏词库是调用方传入过来的，也就没有去做统一的库直接初始化操作等。。 代码工具整体就这样子，简单的几种过滤方法。 有看那些不懂欢迎评论去留言。

作者：Teddy (公众号：鸡仓故事汇) ok！到这里就大功告成，小编（Teddy）在这里先感谢大家的到来。 虽然不是太详细，小编已经很努力，给小编来个一键三连(点赞，关注，收藏)，小编会越来越努力。。。