DFA简介
在实现文字过滤的算法中，DFA是唯一比较好的实现算法。DFA即Deterministic Finite Automaton，也就是确定有穷自动机，它是是通过event和当前的state得到下一个state，即event+state=nextstate。下图展示了其状态的转换
在这幅图中大写字母（S、U、V、Q）都是状态，小写字母a、b为动作。通过上图我们可以看到如下关系
a b b
S -----> U S -----> V U -----> V
在实现敏感词过滤的算法中，我们必须要减少运算，而DFA在DFA算法中几乎没有什么计算，有的只是状态的转换。
Java思路
实现敏感词过滤的关键就是DFA算法的实现。首先我们对上图进行剖析。在这过程中我们认为下面这种结构会更加清晰明了。
同时这里没有状态转换，没有动作，有的只是Query（查找）。我们可以认为，通过S query U、V，通过U query V、P，通过V query U P。通过这样的转变我们可以将状态的转换转变为使用Java集合的查找。
流程:
DFA算法典型运用:敏感词
敏感词:[中国, 法X轮X功, 中国人民] 备注:博客园也做了敏感词检测为了保存,实际情况为去掉中间的X的结果
结构:(感觉就是树的遍历 isEnd是节点属性:判断是否关键字结束)
{中={isEnd=0, 国={人={民={isEnd=1}, isEnd=0}, isEnd=1}}, 法={isEnd=0, 轮={isEnd=0, 功={isEnd=1}}}}
{
中={
isEnd=0,
国={
人={
民={
isEnd=1
},
isEnd=0
},
isEnd=1
}
},
法={
isEnd=0,
轮={
isEnd=0,
功={
isEnd=1
}
}
}
}
例子
工具类:
package com.wfz; import java.io.*; import java.util.*; /** * Created by Liang on 5/5/2017. */ public class SensitiveWordUtils { public static int minMatchTYpe = 1; //最小匹配规则 public static int maxMatchType = 2; //最大匹配规则 private String ENCODE_GBK = "GBK";//编码模式 /** * 文件读取敏感词汇 * * @param file * @return 敏感词的set数组 * @throws IOException */ public Set readSensitiveWordFile(File file) throws IOException { Set<String> keyWordSet = null; BufferedReader reader = null; try { //读取文件 reader = new BufferedReader(new InputStreamReader(new FileInputStream(file), ENCODE_GBK)); //文件存在性 if (file.isFile() && file.exists()) { keyWordSet = new HashSet<String>(); String keyword = null; ////读取文件，将文件内容放入到set中 while ((keyword = reader.readLine()) != null) { keyWordSet.add(keyword); } } else { throw new Exception("敏感词库文件不存在"); } } catch (Exception e) { e.printStackTrace(); } finally { reader.close(); } return keyWordSet; } /** * 从Set中读取敏感字的hashmap，将敏感词加入到HashMap中，构建DFA算法模型 * * @param keyWordSet */ public HashMap getSensitiveWordHashMap(Set<String> keyWordSet) { HashMap result = new HashMap(keyWordSet.size()); Map keymap = null; Map<String, String> endmap = null; for (String key : keyWordSet) {//得到关键字 keymap = result; int len = key.length(); for (int i = 0; i < len; i++) { char keychar = key.charAt(i); Object val = keymap.get(keychar); if (val != null) {//存在直接引用 定位keymap要定位的位置在哪个value下 keymap = (Map) val; } else {//不存在就赋值并添加 endmap = new HashMap<String, String>(); endmap.put("isEnd", "0"); keymap.put(keychar, endmap); keymap = endmap;//一直保证尾部value添加map } if (i == len - 1) {//最后一个 keymap.put("isEnd", "1"); } } } return result; } /** * 得到敏感词 * * @param map 敏感词hashmap * @param txt 待匹配文字 * @param matchType 匹配类型 * @return */ public Set<String> getSensitiveWord(Map map, String txt, int matchType) { Set<String> set = new HashSet<String>(); for (int i = 0; i < txt.length(); i++) { int length = CheckSensitiveWord(map, txt, i, matchType); //判断是否包含敏感字符 if (length > 0) { //存在,加入list中 set.add(txt.substring(i, i + length)); i = i + length - 1; //减1的原因，是因为for会自增 } } return set; } /** * 检查是否存在敏感词 * * @param map 敏感词hashmap * @param txt 待匹配文字 * @param beginIndex 文字索引 * @param matchType 匹配类型 * @return */ private int CheckSensitiveWord(Map map, String txt, int beginIndex, int matchType) { boolean endflag = false;//isEnd标志位 int lenflag = 0;//是否为词标志位 长度》1 char word; int len = txt.length(); for (int i = beginIndex; i < len; i++) { word = txt.charAt(i); map = (Map) map.get(word); if (map != null) {//字母匹配就循环内 再匹配 直到isEnd=1 长度和isEnd两个标志位判断是否匹配 lenflag++; if ("1".equals(map.get("isEnd"))) { endflag = true; if (minMatchTYpe == matchType) {//最小规则，直接返回,最大规则还需继续查找 break; } } } else {//不存在 直接返回 break; } } if (lenflag < 2 || !endflag) { lenflag = 0; } return lenflag; } /** * 是否包含敏感词 * * @param map 敏感词hashmap * @param txt 待匹配文字 * @param matchType 匹配类型 * @return */ public boolean containSensitiveWord(Map map, String txt, int matchType) { boolean flag = false; for (int i = 0; i < txt.length(); i++) { int length = CheckSensitiveWord(map, txt, i, matchType); //判断是否包含敏感字符 if (length > 0) { //存在,加入list中 flag = true; } } return flag; } /** * 替换敏感词 * * @param map 敏感词hashmap * @param txt 待匹配文字 * @param matchType 匹配类型 * @param replaceChar 替换字符 * @return */ public String replaceSensitiveWord(Map map, String txt, int matchType, String replaceChar) { String ret = txt; Set<String> set = getSensitiveWord(map, txt, matchType); for (String word : set) { String replaceword = getReplaceChars(replaceChar, word.length()); ret = ret.replaceAll(word, replaceword); } return ret; } /** * 得到替换的字符串 * * @param replaceChar 替换字符 * @param length 长度 * @return */ private String getReplaceChars(String replaceChar, int length) { String ret = replaceChar; for (int i = 1; i < length; i++) { ret += replaceChar; } return ret; } }
测试类:
SensitiveWordUtils ins = new SensitiveWordUtils(); File file = new File("D:\SensitiveWord.txt"); Set set = ins.readSensitiveWordFile(file); System.out.println(set); HashMap map = ins.getSensitiveWordHashMap(set); System.out.println(map); String string = "爱看三.级.片的日本人民在中国旅游"; System.out.println("待检测语句字数：" + string.length()); long beginTime = System.currentTimeMillis(); Set<String> ret = ins.getSensitiveWord(map, string, 1); long endTime = System.currentTimeMillis(); System.out.println("语句中包含敏感词的个数为：" + ret.size() + "。包含：" + ret); boolean b = ins.containSensitiveWord(map, string, 1); System.out.println(b); String newstring = ins.replaceSensitiveWord(map, string, 1, "*"); System.out.println(newstring); System.out.println("总共消耗时间为：" + (endTime - beginTime));
结果:
[中国, 中国人民]
{中={isEnd=0, 国={人={民={isEnd=1}, isEnd=0}, isEnd=1}}}
待检测语句字数：17
语句中包含敏感词的个数为：1。包含：[中国]
true
爱看三.级.片的日本人民在**旅游
总共消耗时间为：0
参考原文:hxxp://blog.csdn.net/chenssy/article/details/26961957