敏感词过滤DFA算法
- 用处
- DFA 算法原理
- 算法实现demo
用处
政府相关网站项目的新闻一般会有一些敏感词不能出现, 这个时候就需要做一个AOP进行拦截,对所有提交的新闻字段进行过滤
常见的过滤方法
- 直接将敏感词组织成 String 后, 利用 indexOf 方法来查询
- 传统的敏感词入库后SQL查询
- 利用 Lucene 建立分词索引查询
- 利用 DFA 算法
在敏感词和扫描字段不多的情况下, 1 和 2 可以满足需求, 在高性能下不足以满足需求, 效率太低
3 方法分词后可能会有的敏感词语不会变为敏感词, 方法复杂, 效率也低
目前大多数过滤系统采用的都是 DFA 算法
DFA 算法原理
DFA 即 Deterministic Finite Automaton 也就是确定有穷自动机, 他是通过 event 和当前的 state 得到下一个 state, 即 event + state = nextState. 下图展示了其状态的转换
<图片来源见水印>
构建规则原理
以 日本人, 日本鬼子 为例
- 在 hashMap 中查询 “日” 看其是否在 hashMap 中, 如果不存在, 则证明以 “日” 开头的敏感词还不存在, 则我们直接构建这样的一颗树. 跳至 3.
- 如果hashMap中查找到了, 表明存在以"日"开头的敏感词, 设置hashMap = hashMap.get(“日”), 跳至 1, 依次匹配 “本”, “人”
- 判断该字是否为该词中的最后一个字, 若是敏感词结束,则设置标志位 isEnd = 1, 否则设置标志位 isEnd = 0.
<图片来源见水印>
最终敏感词形成的 hashMap 树结构为
{日=
{本=
{人={isEnd=1},
鬼=
{子={isEnd=1},
isEnd=0},
isEnd=0},
isEnd=0},
大=
{汉=
{民={isEnd=0,
族={isEnd=1}
},
isEnd=0},
isEnd=0,
中={isEnd=0,
华={isEnd=1,
帝={isEnd=0,
国={isEnd=1}}}}}}
初始化中可以结合正则排除字典中的特殊字符
检索扫描原理
假如我们匹配 “中国人民万岁”
- 第一个字"中", 我们在hashMap中可以找到, 得到一个新的map= hashMap.get(“中”)
- 如果 map == null, 则表示不是敏感词, 否则跳至 3
- 获取map中的isEnd, 通过isEnd == 1 来判定该词是否为最后一个, 如果 isEnd == 1 则表示该词为敏感词, 否则跳至 1
通过这个步骤我们可以判定 “中国人民” 为敏感词, 但是如果我们输入"中国女人" 则不是敏感词了
扫描过程也需要结合正则排除跳过特殊字符
算法实现demo
import java.util.HashMap;
import java.util.HashSet;
import java.util.Set;
import java.util.regex.Matcher;
import java.util.regex.Pattern;
/**
* @Author Yzx
* @Date 2020/4/23 0023 15:34
* @Version 1.0
*/
public class DFAUtil {
HashMap<String, Object> dfaMap;
public static final int minMatchType = 1;
public static final int maxMatchType = 2;
/**
* 忽略特殊字符的正则表达式
*/
private final String IGNORE_SPECIAL_CHAR_REGEX = "[`~!@#$%^&*()+=|{}':;',\\\\[\\\\].<>/?~！@#￥%……&*（）——+|{}【】‘；：”“’。，、？]|\\s*";
/**
* 忽略特殊字符的正则表达式MATCHER
*/
private final Matcher IGNORE_MATCHER = Pattern.compile(IGNORE_SPECIAL_CHAR_REGEX).matcher("");
/*{日=
* {本=
* {人={isEnd=1},
* 鬼=
* {子={isEnd=1},
* isEnd=0},
* isEnd=0},
* isEnd=0},
*
* 大=
* {汉=
* {民={isEnd=0,
* 族={isEnd=1}},
* isEnd=0},
* isEnd=0,
* 中={isEnd=0,
* 华={isEnd=1,
* 帝={isEnd=0,
* 国={isEnd=1}}}}}}*/
/**
* set作为敏感词，创建出对应的dfa的Map，以供检验敏感词
*
* @param set
*/
public void createDFAHashMap(Set<String> set) {
HashMap<String, Object> nowMap;
//根据set的大小，创建map的大小
dfaMap = new HashMap<>(set.size());
//对set里的字符串进行循环
for (String key : set) {
//对每个字符串最初，nowMap就是dfaMap
nowMap = dfaMap;
for (int i = 0; i < key.length(); i++) {
if (isIgnore(key.charAt(i))){
continue;
}
//一个个字符循环
String nowChar = String.valueOf(key.charAt(i));
//根据nowChar得到nowMap里面对应的value
HashMap<String, Object> map = (HashMap<String, Object>) nowMap.get(nowChar);
//如果map为空，则说明nowMap里面没有以nowChar开头的东西，则创建一个新的hashmap，
//以nowChar为key，新的map为value，放入nowMap
if (map == null) {
map = new HashMap<String, Object>();
nowMap.put(nowChar, map);
}
//nowMap=map，就是nowChar对应的对象
nowMap = map;
//最后在nowMap里设置isEnd
//如果nowMap里面已经有isEnd，并且为1，说明以前已经有关键字了，就不再设置isEnd
//因为如果没有这一步，大中华和大中华帝国，先设置大中华
//在大中华帝国设置的时候，华对应的map有isEnd=1，如果这时对它覆盖，就会isEnd=0，导致大中华这个关键字失效
if (nowMap.containsKey("isEnd") && nowMap.get("isEnd").equals("1")) {
continue;
}
if (i != key.length() - 1) {
nowMap.put("isEnd", "0");
} else {
nowMap.put("isEnd", "1");
}
}
}
System.out.println(dfaMap);
}
/**
* 用创建的dfaMap，根据matchType检验字符串string是否包含敏感词，返回包含所有对于敏感词的set
*
* @param string 要检查是否有敏感词在内的字符串
* @param matchType 检查类型，如大中华帝国牛逼对应大中华和大中华帝国两个关键字，1为最小检查，会检查出大中华，2位最大，会检查出大中华帝国
* @return
*/
public Set<String> getSensitiveWordByDFAMap(String string, int matchType) {
Set<String> set = new HashSet<>();
for (int i = 0; i < string.length(); i++) {
//matchType是针对同一个begin的后面，在同一个begin匹配最长的还是最短的敏感词
int length = getSensitiveLengthByDFAMap(string, i, matchType);
if (length > 0) {
set.add(string.substring(i, i + length));
//这个对应的是一个敏感词内部的关键字（不包括首部），如果加上，大中华帝国，对应大中华和中华两个敏感词，只会对应大中华而不是两个
//i=i+length-1;//减1的原因，是因为for会自增
}
}
return set;
}
/**
* 如果存在，则返回敏感词字符的长度，不存在返回0
*
* @param string
* @param beginIndex
* @param matchType 1：最小匹配规则，2：最大匹配规则
* @return
*/
public int getSensitiveLengthByDFAMap(String string, int beginIndex, int matchType) {
//当前匹配的长度
int nowLength = 0;
//最终匹配敏感词的长度，因为匹配规则2，如果大中华帝，对应大中华，大中华帝国，在华的时候，nowLength=3，因为是最后一个字，将nowLenth赋给resultLength
//然后在帝的时候，now=4，result=3，然后不匹配，resultLength就是上一次最大匹配的敏感词的长度
int resultLength = 0;
HashMap<String, Object> nowMap = dfaMap;
for (int i = beginIndex; i < string.length(); i++) {
if (isIgnore(string.charAt(i))){
nowLength++;
continue;
}
String nowChar = String.valueOf(string.charAt(i));
//根据nowChar得到对应的map，并赋值给nowMap
nowMap = (HashMap<String, Object>) nowMap.get(nowChar);
//nowMap里面没有这个char，说明不匹配，直接返回
if (nowMap == null) {
break;
} else {
nowLength++;
//如果现在是最后一个，更新resultLength
if ("1".equals(nowMap.get("isEnd"))) {
resultLength = nowLength;
//如果匹配模式是最小，直接匹配到，退出
//匹配模式是最大，则继续匹配，resultLength保留上一次匹配到的length
if (matchType == minMatchType) {
break;
}
}
}
}
return resultLength;
}
/**
* 判断是否是要忽略的字符(忽略所有特殊字符以及空格)
*
* @param specificChar 指定字符
* @return 特殊字符或空格true否则false
*/
private boolean isIgnore(char specificChar) {
return IGNORE_MATCHER.reset(String.valueOf(specificChar)).matches();
}
public static void main(String[] args) {
Set set = new HashSet();
set.add("傻逼");
set.add("操你妈");
set.add("垃圾");
set.add("憨逼");
set.add("傻屌");
set.add("吃屎");
set.add("三.级片");
set.add("傻屌说");
set.add("傻叼");
DFAUtil dfaUtil = new DFAUtil();
dfaUtil.createDFAHashMap(set);
String str = "私房钱无法猜你妹操你妈我放弃我过去傻屌说废弃物垃圾太多的伤感情怀也许只局限于饲养基地 荧幕中的情节，主人公尝试着去用某种方式渐渐的很潇洒地释自杀指南怀那些自己经历的伤感。\"\n" +
" + \"然后法.轮.功 我们的扮演的角色就是跟随着主人公的喜红客联盟 怒哀乐而过于牵强的把自己的情感也附加于银幕情节中，然后感动就流泪，\"\n" +
" + \"难过就躺在某一个人的怀傻叼尽情的阐述心扉或者手机卡复制器一个人一杯红酒一部电影在夜三.级.片 深人静的晚上，关上电话静静的发呆着。";
long beginTime = System.currentTimeMillis();
Set<String> dfaMap = dfaUtil.getSensitiveWordByDFAMap(str, 1);
long endTime = System.currentTimeMillis();
System.out.println(dfaMap.toString());
System.out.println("总共消耗时间为：" + (endTime - beginTime));
}
}
耗时毫秒