DFA算法实现敏感词过滤

需求：检测一段文本中是否含有敏感词。

比如检测一段文本中是否含有：“滚蛋”，“滚蛋吧你”，“有病”，

可使用的方法有：

遍历敏感词，判断文本中是否含有这个敏感词。

for (keyword in [“滚蛋”、“滚蛋吧你”、“有病”]) {
    if (text.indexOf(keyword) != -1) {
        return true;
    }
}
return false;

使用正则表达式

Pattern pattern = Pattern.compile("滚蛋|滚蛋吧你|有病"); // 编写正则表达式
Matcher matcher = pattern.matcher(text); // 编写正则表达式
return matcher.matches();

以上两个方法，随着敏感词的增加，效率会越来越低。

而我们使用DFA算法只需遍历一遍文本，就可以找出文本中所有敏感词。

DFA算法

我先大致讲讲DFA算法是怎么做到敏感词过滤的。

DFA查找过程

DFA算法会维护一个map结构的敏感词库

map结构就是一个个key、value。在一个key，value中，【key里装的是敏感词的首个字符】，【value又是一个map结构】，这个value里一般存储两对key，value：一对key，value的key是isEnd变量，value为0表示这个字符不是这个敏感词的最后一个字符；value为1表示这个字符是这个敏感词的最后一个字符。另一对key，value的key里装的则是下一个字符，value则又是一个map结构……；

也就是说对于每个敏感词的一个字符中，都记录着这个字符是否为最后一个，如果不是最后一个的话还记录下一个字符的信息。

画成树的结构就是这样：
遍历文本中的每个字符，【此时的map的key都是敏感词的第一个字符】。
如果map.get(这个字符)不为空，表示这个字符可能是敏感词的第一个字符
获取这个敏感词字符的下一个字符信息，和isEnd信息。【此时的map的key是下一个字符】。判断isEnd是否为1，为1表示匹配到敏感词，结束。
不为1，继续遍历文本的下一个字符，判断map.get(这个字符)是否为空。
如果不为空，获取这个敏感词字符的下一个字符信息，和isEnd信息。【此时的map的key是下一个字符】。判断isEnd是否为1，为1表示匹配到敏感词，结束。
不为1，……
直到isEnd为1

上面的步骤归纳起来，一个循环主要做的就是

map.get(这个字符)
是否为空，不为空，获取这个敏感词字符的下一个字符信息和isEnd信息。如果isEnd为1，结束
继续循环遍历。

经过上述步骤，就可以匹配到一个敏感词，如果文本中有多个敏感词炸糕？将文本中的每个字符作为初始字符，都经过上面步骤的匹配，最终都可以找到文本中包含的所有敏感词。

敏感词库初始化

知道了大致匹配的过程后，就是要构建一个敏感词库，也就是给你一堆敏感词，构建一个map结构。如下图：

在这里插入图片描述

与匹配差不多思路：

遍历敏感词的每一个字符
curMap一开始就是表示敏感词一个字符的map结构
Map<String, Object> wordMap = (Map<String, Object>) curMap.get(key);
如果wordMap 为空，则建一个wordMap ，这个wordMap 涵盖两个信息：下一个字符、isEnd
不管wordMap 为不为空，curMap被赋值为wordMap ，表示下一个字符的map结构。
……循环

/**
 * 生成敏感词库
 * @param words
 * @return
 */
private Map<String, Object> handleToMap(Collection<String> words) {
    if (words == null) {
        return null;
    }

    // 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");
            }
        }
    }

    return map;
}

/**
 * 文本中是否含有敏感词
 * @param text
 * @param beginIndex
 * @return
 */
private 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 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;
}
put(word, wordMap.get(word) + 1);
            } else {
                wordMap.put(word, 1);
            }

            i += wordLength - 1;
        }
    }
    return wordMap;
}