功能简介
DFA算法模型是解决针对一段文本,过滤出其他文本。比如我们定义了三段文本a、b和c为“张三”、“程序员”、“开发”,而在文本d“我的名字叫张三,我是一名刚工作一年的程序员”的内容中,可以发现文本d是包含a和b文本的,这个过程就是DFA算法模型实现的功能。DFA算法的核心是构建出一个模型。
抛出疑问
- java中有contain方法进行判断a文本是否包含b文本,为什么不直接用contain进行比较呢?
- DFA算法用Java如何构建?
- DFA算法性能如何?
算法思想
举个例子,假如我们认为以下是敏感词。
1. 我是张三
2. 我是李四
3. 大王八
4. 大王来了
然后我们根据上面的敏感词构建出一个模型,该模型实际上是一颗树,或者说是森林。在java代码中实际上是多个map,为了方便观察,我转换成了json。(不完整版本)
{
"我": {
"是": {
"张": {
"三": {}
},
"李": {
"四": {}
}
}
},
"大": {
"王": {
"来": {
"了": {}
},
"八": {}
}
}
}
我们通过上面构建的模型对目标文本“我是张三,我是大王”进行敏感词过滤,大致过程如下:
1. 遍历目标文本,获取到第一个字符‘我’,在我们构建的模型的第一层比较,发现第一层的字符串是‘我’和‘大’。
2. 字符‘我’能够在模型中匹配到,继续获取目标文本的下一个字符‘是’,发现第二层也是‘是’,也是匹配上了,依次是‘张’、‘三’。
3. 通过步骤2我们可以断定目标文本中“我是张三”是敏感词,记录下来。
4. 继续获取下一个字符,这里节省时间直接跳到‘大’的字符,发现可以和第一层的‘大’匹配上,然后获取目标文本中的下一个字符‘王’,也能够在模型中匹配上。
5. 这样整个匹配过程完成了,大家可能有疑问,那到底“大王”算不算敏感词呢?如果算,但是我们在定义敏感词的时候并没有“大王”;如果不算,但确实是匹配上了。
为了解决这个问题,我们在构建好的模型中加一个字段就可以解决这种摸棱两可的问题。
{
"我": {
"isEnd": false,
"是": {
"张": {
"三": {
"isEnd": true
},
"isEnd": false
},
"isEnd": false,
"李": {
"四": {
"isEnd": true
},
"isEnd": false
}
}
},
"大": {
"王": {
"来": {
"了": {
"isEnd": true
},
"isEnd": false
},
"八": {
"isEnd": true
},
"isEnd": false
},
"isEnd": false
}
}
可以看到加了一个isEnd字段进行记录构建的模型,每段敏感词的结尾是true,如果不是结尾则是false,比如“我”“我是”“我是张”都为false,而“我是张三”为true。通过这个字段每次来判断敏感词校验是否到了敏感词的结尾。
回到上面的问题:“大王”到底算不算敏感词呢?
根据上面的分析,只有完整匹配上模型中的敏感词才能算敏感词,所以在比较‘王’的时候发现isEnd是false,说明“大王”只是“大王八”或者“大王来了”的一部分,并不能算敏感词。所以目标文本“我是张三,我是大王”中“我是张三”是敏感词,“大王”不是敏感词。
构建DFA模型
下面用java代码构建一个DFA模型
/**
* @param keyWordSet 敏感词库
*/
private Map addSensitiveWordToHashMap(Set<String> keyWordSet) {
// 初始化敏感词容器,减少扩容操作
Map sensitiveWordMap = new HashMap(keyWordSet.size());
String key;
Map nowMap;
Map<String, String> newWordMap;
// 遍历keyWordSet
for (String aKeyWordSet : keyWordSet) {
// 关键字
key = aKeyWordSet;
nowMap = sensitiveWordMap;
for (int i = 0; i < key.length(); i++) {
// 转换成char型
char keyChar = key.charAt(i);
// 65279是一个空格,遇到空格直接跳过即可
if ((int) keyChar == 65279) {
continue;
}
// 获取
Object wordMap = nowMap.get(keyChar);
if (wordMap != null) {
// 如果存在该key,直接赋值
nowMap = (Map) wordMap;
} else {
// 不存在则,则构建一个map,同时将isEnd设置为0,因为他不是最后一个
newWordMap = new HashMap<>();
// 不是最后一个
newWordMap.put("isEnd", "0");
nowMap.put(keyChar, newWordMap);
nowMap = newWordMap;
}
if (i == key.length() - 1) {
// 最后一个
nowMap.put("isEnd", "1");
}
}
}
return sensitiveWordMap;
}
构建好模型之后,通过下面方法进行判断是否存在敏感词。
/**
* 过滤出敏感词
*
* @param txt 目标文本
* @param matchType 匹配模式 1、最小匹配模式 2、最大匹配模式
*/
public Set<String> getSensitiveWordSets(String txt, int matchType) {
Set<String> sensitiveWordSets = new HashSet<>();
for (int n = 0; n < txt.length(); n++) {
// 判断是否包含敏感字符
int length = judgeSensitiveWithIndex(txt, n, matchType);
if (length > 0) {
// 存在,加入list中
sensitiveWordSets.add(txt.substring(n, n + length));
// 减1的原因,是因为for会自增
n = n + length - 1;
}
}
return sensitiveWordSets;
}
/**
* 根据指定位置是否是敏感词的开始
*
* @param txt 文本
* @param beginIndex 开始位置
* @param matchType 匹配模式 1、最小匹配模式 2、最大匹配模式
* @return int
*/
private int judgeSensitiveWithIndex(String txt, int beginIndex, int matchType) {
// 匹配标识数默认为0
int matchFlag = 0;
char word;
boolean isEnd = false;
Map nowMap = sensitiveWordMap;
for (int i = beginIndex; i < txt.length(); i++) {
word = txt.charAt(i);
// 获取指定key
nowMap = (Map) nowMap.get(word);
// 存在,则判断是否为最后一个
if (nowMap != null) {
// 找到相应key,匹配标识+1
matchFlag++;
if ((boolean) nowMap.get("isEnd")) {
// 如果为最后一个匹配规则,结束循环,返回匹配标识数
isEnd = true;
break;
}
} else {
// 不存在,直接返回
break;
}
}
if (1 == matchType) {
// 最小匹配模式
return matchFlag;
}
// 最大匹配模式
if (isEnd) {
return matchFlag;
}
return 0;
}
解答疑问
1. java中有contain方法进行判断a文本是否包含b文本,为什么不直接用contain进行比较呢?
可以从两方面考虑:
①功能方面,contain只能进行最大匹配模式进行匹配,比如目标文本“我是张三,我是大王”,针对敏感词“大王八”,目标文本中的“大王”正常来说是不算敏感词的,但是要是有这么个需求就认为“大王”是敏感词,那么contain就不能满足这个需求了。而DFA可以设置最小匹配模式,可以过滤出“大王”是敏感词。
②性能方面,contain是针对每次比对一个敏感词,尽管有containAny,但底层还是对每个敏感词进行比对,也就意味着,有一万个敏感词,就要比对一万次,性能相对很低;而DFA算法不管有多少敏感词,只需要对目标文本遍历一次,便可以获取目标文本涉及到的所有敏感词。
2. DFA算法用Java如何构建?
用java实现实际上就是一层层map的嵌套,核心思想就是通过遍历文本的每个字符,然后去map中找到对应的key一层层进行比对,具体实现如上。
3. DFA算法性能如何?
DFA算法的性能取决于目标文本的长度,遍历一次目标文本即可获取所有涉及到的敏感词,尤其适合针对于实时聊天软件的敏感词过滤;假设目标文本的长度为n,它的时间复杂度为O(n)。
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
文章由极客之音整理,本文链接:https://www.bmabk.com/index.php/post/192063.html