DFA,全称为Deterministic Finite Automaton,即确定有穷自动机、确定有限状态自动机或确定有限自动机
对于一个给定的属于该自动机的状态和一个属于该自动机字母表Σ的字符,它都能根据事先给定的转移函数转移到下一个状态(这个状态可以是先前那个状态)。
确定:状态以及引起状态转换的事件都是可确定的,不存在“意外”。
有穷:状态以及事件的数量都是可穷举的。
简单来说就是存储字符串每个字符,并判断到该字符为止是否属于敏感词
存储:一次性的把所有的敏感词存储到了多个map中,就是下图表示这种结构
敏感词:冰毒、大麻、大坏蛋
检索的过程
执行上面的过程,就能匹配到内容中的敏感词了
public static Map<String, Object> dictionaryMap = new HashMap<>();
/**
* 生成关键词字典库
* @param words
* @return
*/
public static void initMap(Collection<String> words) {
if (words == null) {
System.out.println("敏感词列表不能为空");
return ;
}
// map初始长度words.size(),整个字典库的入口字数(小于words.size(),因为不同的词可能会有相同的首字)
Map<String, Object> map = new HashMap<>(words.size());
// 遍历过程中当前层次的数据
Map<String, Object> curMap = null;
Iterator<String> iterator = words.iterator();
while (iterator.hasNext()) {
String word = iterator.next();
curMap = map;
int len = word.length();
for (int i =0; i < len; i++) {
// 遍历每个词的字
String key = String.valueOf(word.charAt(i));
// 当前字在当前层是否存在, 不存在则新建, 当前层数据指向下一个节点, 继续判断是否存在数据
Map<String, Object> wordMap = (Map<String, Object>) curMap.get(key);
if (wordMap == null) {
// 每个节点存在两个数据: 下一个节点和isEnd(是否结束标志)
wordMap = new HashMap<>(2);
wordMap.put("isEnd", "0");
curMap.put(key, wordMap);
}
curMap = wordMap;
// 如果当前字是词的最后一个字,则将isEnd标志置1
if (i == len -1) {
curMap.put("isEnd", "1");
}
}
}
dictionaryMap = map;
}
/**
* 搜索文本中某个文字是否匹配关键词
* @param text
* @param beginIndex
* @return
*/
private static int checkWord(String text, int beginIndex) {
if (dictionaryMap == null) {
throw new RuntimeException("字典不能为空");
}
boolean isEnd = false;
int wordLength = 0;
Map<String, Object> curMap = dictionaryMap;
int len = text.length();
// 从文本的第beginIndex开始匹配
for (int i = beginIndex; i < len; i++) {
String key = String.valueOf(text.charAt(i));
// 获取当前key的下一个节点
curMap = (Map<String, Object>) curMap.get(key);
if (curMap == null) {
break;
} else {
wordLength ++;
if ("1".equals(curMap.get("isEnd"))) {
isEnd = true;
}
}
}
if (!isEnd) {
wordLength = 0;
}
return wordLength;
}
/**
* 获取匹配的关键词和命中次数
* @param text
* @return
*/
public static Map<String, Integer> matchWords(String text) {
Map<String, Integer> wordMap = new HashMap<>();
int len = text.length();
for (int i = 0; i < len; i++) {
int wordLength = checkWord(text, i);
if (wordLength > 0) {
String word = text.substring(i, i + wordLength);
// 添加关键词匹配次数
if (wordMap.containsKey(word)) {
wordMap.put(word, wordMap.get(word) + 1);
} else {
wordMap.put(word, 1);
}
i += wordLength - 1;
}
}
return wordMap;
}
public static void main(String[] args) {
List<String> list = new ArrayList<>();
list.add("坏蛋");
list.add("混蛋");
list.add("笨蛋");
initMap(list);
String content="我是一个坏人,但是不是坏蛋,也不是笨蛋";
Map<String, Integer> map = matchWords(content);
System.out.println(map);
}
可以看到匹配结果是正确的(上面的代码可以直接封装成工具类使用)
// 封装后直接调用
// 初始化敏感词库
SensitiveWordUtil.initMap(sensitiveList);
// 查看内容中是否包含敏感词
Map<String, Integer> map = SensitiveWordUtil.matchWords(content);
if (map.size() > 0) {
System.out.println("内容中存在敏感词");
}
这个算法和之前遇到的字典树(Trie)算法很像,然后我就去搜索了一下两者的联系,发现DFA算法的核心就是构建一颗以敏感词为基础的多叉树,也就是字典树。字典树的每个节点代表一个状态,每条边代表一个字符,从一个状态到另一个状态的转移。当遍历完一个词后,将该词的最后一个字符的状态标记为结束(isEnd = true)
这样,我们可以通过这个DFA字典树,一个字符一个字符的检测输入的字符串,如果检测的字符在我们的敏感词树中,就进入命中的树,看下一个字符在不在树中,如果持续命中到最后一个字符,即idEnd = true,那么就是完全命中了,即存在敏感词