基于DFA算法实现敏感词过滤

何为DFA

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标志置1if (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;}

验证DFA算法

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，那么就是完全命中了，即存在敏感词