DFA，全称 Deterministic Finite Automaton 即确定有穷自动机：从一个状态通过一系列的事件转换到另一个状态，即 state -> event -> state。

　　确定：状态以及引起状态转换的事件都是可确定的，不存在“意外”。
　　有穷：状态以及事件的数量都是可穷举的
详细的算法大家可以自行鸟姐下哈。今天咱们主要讲下DFA算法进行敏感词统计

比如说有以下这些敏感词

【二傻子，不太行，二傻子吧？】

咱们先分析下。如果不用DFA算法。咱们就得用正则表达式匹配。看下是否包含这两个词。

但是这样的话效率太低了。会随着被匹配内容的增加进行指数型增加（也就是O(2ⁿ)）

接下咱们可以想着优化下

可以发现如果这个文本都不包含`二`就更不会包含 二傻子

以此类推 包含 `二` 但是后边不是 `傻` 那也不包含敏感词  再以此类推

转成Java思维 

{二={End=0, 傻={子={End=1}, End=0,吧={？={End=1}}}  必须把链路走完才是敏感词。也就是有1

上边这个json就可以用Java当中的Map来实现。上代码

  1 import java.io.BufferedReader;
  2 import java.io.File;
  3 import java.io.FileInputStream;
  4 import java.io.InputStreamReader;
  5 import java.util.*;
  6 
  7 /**
  8  * 敏感词对象
  9  */
 10 @Service
 11 public class SensitiveWord {
 12 
 13     //分布式锁
 14     private static IDistributedLock distributedLock;
 15 
 16     @Autowired
 17     public void setIDistributedLock(IDistributedLock distributedLock) {
 18         SensitiveWord.distributedLock = distributedLock;
 19     }
 20 
 21 
 22     /**
 23      * 铭感词状态 false 未初始化 ture已初始化
 24      */
 25     public static boolean status;
 26     public static HashMap sensitiveWordMap;
 27 
 28     public SensitiveWord() {
 29         super();
 30     }
 31 
 32     /**
 33      *
 34      */
 35     @SuppressWarnings("rawtypes")
 36     public static Map initKeyWord() {
 37         String distributedLockKey = "information:applyCredit:admin:wscs";
 38         try {
 39 
 40             if (!distributedLock.tryLock(distributedLockKey, 3, -1)) {
 41                 throw BusinessException.of(CommonCodeMsg.TOO_FREQUENT);
 42             }
 43             status = false;
 44             //读取敏感词库
 45             Set<String> keyWordSet = readSensitiveWordFile();
 46             //将敏感词库加入到HashMap中
 47             addSensitiveWordToHashMap(keyWordSet);
 48 
 49         } catch (Exception e) {
 50             e.printStackTrace();
 51         } finally {
 52             status = true;
 53             // 待事务提交后再释放锁
 54             SpringUtils.afterCompletion(() -> distributedLock.release(distributedLockKey));
 55         }
 56         return sensitiveWordMap;
 57     }
 58 
 59 
 60     /**
 61      * 读取敏感词库，将敏感词放入HashSet中，构建一个DFA算法模型：<br>
 62      * 中 = {
 63      * isEnd = 0
 64      * 国 = {<br>
 65      * isEnd = 1
 66      * 人 = {isEnd = 0
 67      * 民 = {isEnd = 1}
 68      * }
 69      * 男  = {
 70      * isEnd = 0
 71      * 人 = {
 72      * isEnd = 1
 73      * }
 74      * }
 75      * }
 76      * }
 77      * 五 = {
 78      * isEnd = 0
 79      * 星 = {
 80      * isEnd = 0
 81      * 红 = {
 82      * isEnd = 0
 83      * 旗 = {
 84      * isEnd = 1
 85      * }
 86      * }
 87      * }
 88      * }
 89      *
 90      * @param keyWordSet 敏感词库
 91      * @version 1.0
 92      */
 93     @SuppressWarnings({"rawtypes", "unchecked"})
 94     public static void addSensitiveWordToHashMap(Set<String> keyWordSet) {
 95         sensitiveWordMap = new HashMap(keyWordSet.size());     //初始化敏感词容器，减少扩容操作
 96         String key = null;
 97         Map nowMap = null;
 98         Map<String, String> newWorMap = null;
 99         //迭代keyWordSet
100         Iterator<String> iterator = keyWordSet.iterator();
101         while (iterator.hasNext()) {
102             key = iterator.next();    //关键字
103             nowMap = sensitiveWordMap;
104             for (int i = 0; i < key.length(); i++) {
105                 char keyChar = key.charAt(i);       //转换成char型
106                 Object wordMap = nowMap.get(keyChar);       //获取
107 
108                 if (wordMap != null) {        //如果存在该key，直接赋值
109                     nowMap = (Map) wordMap;
110                 } else {     //不存在则，则构建一个map，同时将isEnd设置为0，因为他不是最后一个
111                     newWorMap = new HashMap<String, String>();
112                     newWorMap.put("isEnd", "0");     //不是最后一个
113                     nowMap.put(keyChar, newWorMap);
114                     nowMap = newWorMap;
115                 }
116 
117                 if (i == key.length() - 1) {
118                     nowMap.put("isEnd", "1");    //最后一个
119                 }
120             }
121         }
122     }
123 
124     /**
125      * 读取敏感词库中的内容，将内容添加到set集合中
126      *
127      * @return
128      * @throws Exception
129      */
130     @SuppressWarnings("resource")
131     public static Set<String> readSensitiveWordFile() throws Exception {
132         Set<String> set = null;
133 
134         File file = new File("D:\\SensitiveWord.txt");    //读取文件
135         InputStreamReader read = new InputStreamReader(new FileInputStream(file), "UTF-8");
136         try {
137             if (file.isFile() && file.exists()) {      //文件流是否存在
138                 set = new HashSet<String>();
139                 BufferedReader bufferedReader = new BufferedReader(read);
140                 String txt = null;
141                 while ((txt = bufferedReader.readLine()) != null) {    //读取文件，将文件内容放入到set中
142                     set.add(txt);
143                 }
144             } else {         //不存在抛出异常信息
145                 throw new Exception("敏感词库文件不存在");
146             }
147         } catch (Exception e) {
148             throw e;
149         } finally {
150             read.close();     //关闭文件流
151         }
152         return set;
153     }
154 
155 }

 酱紫就会把所有的敏感词都先缓存。然后再进行敏感词过滤

 1 /**
 2      * 敏感词过滤
 3      */
 4     public void sensitiveWordFilter() {
 5 
 6         String text = "这是一段需要检测的文字。知道了吗？二傻子？";
 7         for (int i = 0; i < text.length(); i++) {
 8             boolean isExist = this.checkSensitiveWord(text, i);
 9             //判断是否包含敏感字符
10             if (isExist) {
11                 System.out.println("你惨了，你说话都是星星");
12                 return;
13             }
14 
15         }
16 
17     }
18 
19 
20     /**
21      * 检查文字中是否包含敏感字符，检查规则如下：<br>
22      *
23      * @param txt        需要检测的文字
24      * @param beginIndex 开始检测的位置
25      */
26     @SuppressWarnings({"rawtypes"})
27     public boolean checkSensitiveWord(String txt, int beginIndex) {
28         Map nowMap = SensitiveWord.sensitiveWordMap;
29         for (int i = beginIndex; i < txt.length(); i++) {
30             char word = txt.charAt(i);
31             nowMap = (Map) nowMap.get(word);     //获取指定key
32             if (nowMap != null) {     //存在，则判断是否为最后一个
33                 if ("1".equals(nowMap.get("isEnd"))) {
34                     return true;       //结束标志位为true
35                 }
36             } else {
37                 //不存在，直接返回
38                 break;
39             }
40         }
41         return false;
42     }

可以看到这样做，时间复杂度就会降到O(n2)。可以说是非常的不错啦

课后作业

1.统计敏感词字数

2.把敏感词替换成***