利用 DFA 算法实现文字过滤
一、DEA 算法简介
在实现文字过滤的算法中，DFA是唯一比较好的实现算法。
DFA 全称为：Deterministic Finite Automaton，即确定有穷自动机。其特征为：有一个有限状态集合和一些从一个状态通向另一个状态的边，每条边上标记有一个符号，其中一个状态是初态，某些状态是终态。但不同于不确定的有限自动机，DFA 中不会有从同一状态出发的两条边标志有相同的符号。
简单点说就是，它是是通过 event 和当前的 state 得到下一个 state，即 event + state= nextstate。理解为系统中有多个节点，通过传递进入的 event，来确定走哪个路由至另一个节点，而节点是有限的。
二、DEA 算法实践敏感词过滤
1. 敏感词库构造
以王八蛋和王八羔子两个敏感词来进行描述，首先构建敏感词库，该词库名称为SensitiveMap，这两个词的二叉树构造为：
用 hash 表构造为：
{
"王":{
"isEnd":"0",
"八":{
"羔":{
"子":{
"isEnd":"1"
},
"isEnd":"0"
},
"isEnd":"0",
"蛋":{
"isEnd":"1"
}
}
}
}怎么用代码实现这种数据结构呢？
/**
* 读取敏感词库，将敏感词放入HashSet中，构建一个DFA算法模型
*
* @param keyWordSet 敏感词库
*/
public Map<String, Object> addSensitiveWordToHashMap(Set<String> keyWordSet) {
//初始化敏感词容器，减少扩容操作
Map<String, Object> map = new HashMap(Math.max((int) (keyWordSet.size() / .75f) + 1, 16));
//迭代keyWordSet
for (String aKeyWordSet : keyWordSet) {
Map nowMap = map;
for (int i = 0; i < aKeyWordSet.length(); i++) {
//转换成char型
char keyChar = aKeyWordSet.charAt(i);
//获取
Object wordMap = nowMap.get(keyChar);
//如果存在该key，直接赋值
if (wordMap != null) {
nowMap = (Map) wordMap;
} else { //不存在则，则构建一个map，同时将isEnd设置为0
Map<String, String> newWorMap = new HashMap<>(3);
newWorMap.put("isEnd", "0");
nowMap.put(keyChar, newWorMap);
nowMap = newWorMap;
}
//判断最后一个
if (i == aKeyWordSet.length() - 1) {
nowMap.put("isEnd", "1");
}
}
}
return map;
}2. 敏感词过滤
以上面例子构造出来的 SensitiveMap 为敏感词库进行示意，假设这里输入的关键字为：王八不好，流程图如下：
怎么用代码实现这个流程图逻辑呢？
/**
* 查找字符串中是否包含敏感字符
*
* @param txt 输入的字符串
* @return 如果存在，则返回敏感字符串；不存在，则返回空字符串
*/
public static String findSensitiveWord(String txt) {
SensitiveWordInit sensitiveWordInit = SpringContextHolder.getBean(SensitiveWordInit.class);
Map<String, Object> sensitiveWordMap = sensitiveWordInit.getSensitiveWordMap();
StringBuilder sensitiveWord = new StringBuilder();
// 敏感词结束标志位，表示匹配到了最后一位
boolean flag = false;
for (int i = 0; i < txt.length(); i++) {
char word = txt.charAt(i);
// 获取指定 key
sensitiveWordMap = (Map) sensitiveWordMap.get(word);
// 不存在，直接返回没有敏感词
if (sensitiveWordMap == null) {
break;
}
//存在，存储该敏感词，并判断是否为最后一个
sensitiveWord.append(word);
//如果为最后一个匹配规则，结束循环
if ("1".equals(sensitiveWordMap.get("isEnd"))) {
flag = true;
break;
}
}
// 表示匹配到了完整敏感词
if (flag == true) {
return sensitiveWord.toString();
}
return "";
}三、优化思路
对于“王*八&&蛋”这样的词，中间填充了无意义的字符来混淆，在我们做敏感词搜索时，同样应该做一个无意义词的过滤，当循环到这类无意义的字符时进行跳过，避免干扰。
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2019-11-27 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读