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 }
View Code
酱紫就会把所有的敏感词都先缓存。然后再进行敏感词过滤
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 }
View Code
可以看到这样做，时间复杂度就会降到O(n2)。可以说是非常的不错啦
课后作业
1.统计敏感词字数
2.把敏感词替换成***