敏感词检测——基于DFA（有穷自动机）实现

算法
字数统计: 3k   |   阅读时长≈ 13 分钟

背景

最近在做一个社交软件，其中我负责的板块是文章发布与文章品论，文章发布是需要后台进行敏感词检测的，不能出现色情、暴力、政治相关的言论。说实话在刚看到这个需求时，脑子里闪现出了用String类中的contains()，方法检测文章中是否有指定的敏感词，然后用replaceAll()方法全部替换掉。然后从百度上下载到一份敏感词词库，我打开一看，emmmmmm。我靠词库中有一万多个敏感词，这TM没法用contains()。于是乎这个方案就丢了。后来在百度的时候，看到了有穷自动机，前缀树匹配、ikAnalyze分词器等解决方案。这里基于效率，我选择了使用DFA（确定有穷自动机）。

方案选择

DFA(确定有穷自动机)

在实现文字过滤的算法中，DFA是唯一比较好的实现算法。DFA即Deterministic Finite Automaton，也就是确定有穷自动机，它是是通过event和当前的state得到下一个state，即event+state=nextstate。下图展示了其状态的转换，有根从外边来的箭头指向的状态表示初始状态，有个黑圈的状态是接受状态：

图-1

现在我们来看看有穷自动机怎么处理输入的字符串：

  1. 一开始，自动机处于初始状态
  2. 输入字符串的第一个字符，这时自动机会查询当前状态上与输入字符相匹配的边，并沿这条边转换到下一个状态。
  3. 继续输入下一个字符，重复第二步，查询当前状态上的边并进行状态转换
  4. 当字符串全部输入后，如果自动机正好处于接受状态上，就说该自动机接受了这一字符串。

敏感词检测实现思路

从上图-1中我们看出是通过某个动作进入到下一个状态的，在这里我们检测敏感词的动作是通过Query查询来到达下一个状态的。通过输入参数可以Query查询“1”、“2”、“3”。我们就转化为了通过查询动作到Java结果集中查找对应的结果。例如：我们有如下敏感词：日本人、日本鬼子。那么我们这个对应到java中怎么构建集合机构呢？

首先：query 日—>{本}、query 本—>{人、鬼子}、query人—>{null}、query鬼—>{子}。结构如下

图-2

可以对以上结构进行扩展

图-3

这样我们就将我们的敏感词库构建成了一个类似树的结构(其实这个树就是Tire树，也叫作字典树、前缀树)，这样我们来判断一个词是否为敏感词是就只需要找到词的第一个字符下面的子树，遍历这个子树看看是否有我们要检索的词，减少了搜索范围；随着词语的第二个字符、第三个字符进入检查，这个检索范围会越来越小。那么什么是否该结束检索敏感词呢，这里我们需要来一个标识符表示。

在Java中我们通过HashMap来实现以上DFA算法的搜索模型构建，构建思路如下：

  1. 在hashMap中查询“日”，看是否存在hashMap中，如果不存在，则证明在我们的词库模型结构中没有以“日”开头的词，这时我们需要直接构建一个这样的数。然后跳至第3步，设置结束标志位isEnd

    1
    2
    3
    4
    hashMap = wordMap; // 将临时map指针指向词库索引，防止直接操作词库
    HashMap newmap = new HashMap<String,Object>();
    newmap.put("isEnd",0); // 表示这个字符不是结束字符
    hashMap.put("日",newmap);  // HashMap wordMap = new HashMap<String,Object>();

  2. 如果在hashMap中找到了，表示存在以“日”开头的敏感词，则需要遍历这个“日”下的子树，跳至第1步，一次匹配“本”、“人”。

    1
    hashMap = wordMap.get("日");

  3. 判断这个字符是否是该词语中最后一个子。如果是表示敏感词结束，设置标志位为isEnd = 1，否则设置标志位isEnd = 0；

整个流程图如下：

流程图

实现代码

一下代码都是基于springboot项目的

yml配置文件：

1
2
3
4
npl:
  baseDir: classpath:/npl
  sensitiveWord:
    replacement: "*"

DFA算法抽象类

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
package com.yunya.community.miniprogram.basic.nlp;

import lombok.extern.slf4j.Slf4j;
import org.springframework.beans.factory.InitializingBean;
import org.springframework.beans.factory.annotation.Value;
import org.springframework.util.ResourceUtils;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.util.*;
import java.util.concurrent.atomic.AtomicInteger;

/**
 * @Program: community-miniprogram
 * 自然语言处理，基于有穷自动机算法实现敏感词检测，因为目前敏感词不多，多以通过这种方式可以达到空间换取时间效果，
 * 如果敏感词库日后增大的话，不在适合这种方式，可以通过ikAnalyze分词器来做
 * 确定型有穷自动机算法模型结构如下：
 * 比如当前敏感词中有
 * 中国
 * 中国人
 * 中华人民共和国
 * 结构如下:
 * "中": {
 *     isEnd: 0,
 *     "国": {
 *         isEnd: 1,
 *         "人": {
 *             isEnd: 1
 *         }
 *     },
 *     "华": {
 *         isEnd:0,
 *         "人": {
 *             isEnd:0,
 *             "民": {
 *                 isEnd:0,
 *                 "共": {
 *                     isEnd:0,
 *                     "和": {
 *                         isEnd:0,
 *                         "国":{
 *                             isEnd:1
 *                         }
 *                     }
 *                 }
 *             }
 *         }
 *     }
 * }
 * @Description: 基于DFA算法的自然语言处理
 * @Author: LHB
 * @Version: v0.0.1
 * @Time: 2021-12-06 09:23
 **/
@Slf4j
public abstract class NplAbstractHandler implements InitializingBean {

    @Value("${npl.baseDir}")
    private String baseDir = "classpath:/npl";

    private final String TEXT_FILE = "npl";

    private File[] wordTextFiles;

    protected static final String ISEND = "isend";

    protected enum IS_END {
        /**
         * 检索词结束
         */
        ZERO,
        /**
         * 检索词未结束
         */
        ONE
    }

    /**
     * 匹配模式
     */
    protected enum MATCH_TYPE {
        /**
         * 最小匹配规则，如：敏感词库["中国","中国人"]，语句："我是中国人"，匹配结果：我是[中国]人
         */
        MINIMUM_MATCH,
        /**
         * 最大匹配规则，如：敏感词库["中国","中国人"]，语句："我是中国人"，匹配结果：我是[中国人]
         */
        MAXIMUM_MATCH
    }

    public String getBaseDir() {
        return baseDir;
    }

    public void setBaseDir(String baseDir) {
        this.baseDir = baseDir;
    }

    @Override
    public void afterPropertiesSet() throws Exception {
        // 这里主要获取配置文件中的所有词库
        File[] files = ResourceUtils.getFile("classpath:").listFiles(pathname -> {
            if (TEXT_FILE.equals(pathname.getName())) {
                baseDir = pathname.getPath();
                return true;
            }
            return false;
        });
        if (files.length > 0) {
            wordTextFiles = files[0].listFiles();
        }
    }

    /**
     * 初始化DFA处理模型
     *
     * @param dfaWordMap
     * @param wordSet
     */
    protected void init(HashMap dfaWordMap, Set<String> wordSet) {
        log.info("开始初始化词库");
        long start = System.currentTimeMillis();
        HashMap currentMap;
        Iterator<String> iterator = wordSet.iterator();
        while (iterator.hasNext()) {
            currentMap = dfaWordMap;
            String currentWord = iterator.next();
            for (int i = 0; i < currentWord.length(); i++) {
                char keyWord = currentWord.charAt(i);
                Object nextMap = currentMap.get(keyWord);
                if (nextMap != null) {
                    // 将map的指针指向nextMap，以便于下次循环使用
                    currentMap = (HashMap) nextMap;
                } else {
                    HashMap<Object, Object> newWord = new HashMap<>();
                    newWord.put(ISEND, IS_END.ZERO);
                    currentMap.put(keyWord, newWord);
                    // 将map指针指向当前新创建的词节点，下次的新词要在这个新词后面添加
                    currentMap = newWord;
                }

                // 如果字符是词的结尾字符，设置结束表示isEnd=1
                // 这里减1是因为执行完本次循环，i会自增，所以这里需要先减1
                if (i == currentWord.length() - 1) {
                    currentMap.put(ISEND, IS_END.ONE);
                }
            }
        }
        log.info("词库初始化完成,一共{}个词,用时{}ms", wordSet.size(), (System.currentTimeMillis() - start));
    }

    /**
     * 判断文本中是否存在词库中指定的词，存在则返回字符串长度
     *
     * @param dfaWordMap 词库
     * @param text       文本
     * @param beginIndex 文本开始位置
     * @param matchType  匹配模式,参考 {@MATCH_TYPE}
     * @return 返回敏感词长度
     */
    protected int checkWord(HashMap dfaWordMap, String text, int beginIndex, Enum matchType) {
        // 敏感词长度
        AtomicInteger wordLength = new AtomicInteger(0);
        Map currentMap = dfaWordMap;
        boolean flag = false;
        for (int i = beginIndex; i < text.length(); i++) {
            char keyWord = text.charAt(i);
            currentMap = (Map) currentMap.get(keyWord);
            if (currentMap != null) {
                wordLength.getAndIncrement();
                if (1 == ((Integer) currentMap.get(ISEND))) {
                    flag = true;
                    if (MATCH_TYPE.MINIMUM_MATCH == matchType) {
                        break;
                    }
                }

            } else {
                break;
            }
        }
        if (wordLength.get() < 1 || !flag) {
            wordLength.set(0);
        }
        return wordLength.get();
    }

    /**
     * 是否包含词库中的敏感词
     *
     * @param dfaWordMap 词库
     * @param text       文本
     * @param matchType  匹配类型 参考{@MATCH_TYPE}
     * @return
     */
    protected boolean contains(HashMap dfaWordMap, String text, Enum matchType) {
        for (int i = 0; i < text.length(); i++) {
            int wordLength = checkWord(dfaWordMap, text, i, matchType);
            if (wordLength > 0) {
                return true;
            }
        }
        return false;
    }

    /**
     * 获取文本中的敏感词
     * @param dfaWordMap 词库
     * @param text 文本
     * @param matchType 匹配模式
     * @return 返回敏感词集合
     */
    protected Set<String> getSensitiveWordInText(HashMap dfaWordMap, String text, Enum matchType) {
        HashSet<String> sensitiveWordSet = new HashSet<>();
        for (int i = 0; i < text.length(); i++) {
            int wordLength = checkWord(dfaWordMap, text, i, matchType);
            if (wordLength > 0) {
                sensitiveWordSet.add(text.substring(i, i + wordLength));
                i = i + wordLength - 1;
            }
        }
        return sensitiveWordSet;
    }

    /**
     * 替换文本中的敏感词
     * @param dfaWordMap 词库
     * @param text 文本
     * @param replaceChar 代表敏感词的字符，替换后文本将使用这里指定的符号代表敏感词
     * @param matchType 匹配类型
     * @return 返回替换后的文本
     */
    protected String replaceSensitiveWord(HashMap dfaWordMap, String text, char replaceChar, Enum matchType) {
        Set<String> sensitiveWordSet = getSensitiveWordInText(dfaWordMap, text, matchType);
        Iterator<String> iterator = sensitiveWordSet.iterator();
        String resultText = "";
        while (iterator.hasNext()) {
            String sensitive = iterator.next();
            String replaceChars = getReplaceChars(replaceChar, sensitive.length());
            resultText = text.replaceAll(sensitive, replaceChars);
        }
        return resultText;
    }

    /**
     * 获取替换的字符
     * @param replaceChar 替换字符
     * @param length 字符长度
     * @return 返回替换字符
     */
    protected String getReplaceChars(char replaceChar,int length) {
        String replaceStr = String.valueOf(replaceChar);
        for (int i = 0; i < length; i++) {
            replaceStr += replaceStr;
        }
        return replaceStr;
    }

    /**
     * 加载敏感词本地文件
     * @return
     */
    protected Set<String> loadSensitiveWordResources() {
        if (this.wordTextFiles == null) {
            log.warn("在{}下没有找到相应的txt词库文件，敏感词检测将不能使用!!",baseDir);
            return new HashSet<>();
        }
        log.info("开始加载本地词库");
        long start = System.currentTimeMillis();
        HashSet<String> wordSet = new HashSet<>(4096);
        for (File file : wordTextFiles) {
            wordSet.addAll(loadFile(file));
        }
        log.info("本地词库加载完成，共有{}个词，耗时{}ms",wordSet.size(),(System.currentTimeMillis() - start));
        return wordSet;
    }

    /**
     * 加载文件
     * @param file 文件
     * @return
     */
    protected Set<String> loadFile(File file) {
        HashSet<String> words = new HashSet<>(256);
        BufferedReader reader = null;
        try {
            String line = null;
            reader = new BufferedReader(new FileReader(file),2048);
            while ((line = reader.readLine()) != null) {
                words.add(line.trim());
            }
        } catch (IOException e) {
            e.printStackTrace();
        } finally {
            try {
                if (reader != null) {
                    reader.close();
                }
            } catch (Exception e) {
                e.printStackTrace();
            }
        }
        return words;
    }
}

敏感词处理类

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
package com.yunya.community.miniprogram.basic.nlp;

import lombok.extern.slf4j.Slf4j;
import org.springframework.beans.factory.annotation.Value;
import org.springframework.boot.ApplicationArguments;
import org.springframework.boot.ApplicationRunner;
import org.springframework.stereotype.Component;

import java.util.HashMap;
import java.util.Set;

/**
 * @Program: community-miniprogram
 * @Description: 敏感词处理
 * @Author: LHB
 * @Version: v0.0.1
 * @Time: 2021-12-06 09:31
 **/
@Component
@Slf4j
public class SensitiveWordHandler extends NplAbstractHandler implements ApplicationRunner {
    /** dfa敏感词库 */
    private HashMap dfaWordMap;
    /** 本地词库 */
    private Set<String> wordModelSet;

    @Value("${npl.sensitiveWord.replacement}")
    private String replacement = "*";

    /**
     * 文本中是否包含敏感词
     * @param text 文本
     * @param matchType 敏感词匹配类型 参考{@DfaAbstractHandler}类中的{@MATCH_TYPE}变量
     * @return 包含返回true，否则返回false
     */
    public boolean contains(String text, Enum matchType) {
        return contains(dfaWordMap,text,matchType);
    }

    /**
     * 文本中是否包含敏感词,默认最小匹配模式
     * @param text 文本
     * @return 包含返回true，否则返回false
     */
    public boolean contains(String text) {
        return contains(dfaWordMap,text,MATCH_TYPE.MINIMUM_MATCH);
    }

    /**
     * 获取文本中的敏感词
     * @param text 文本
     * @param matchType 敏感词匹配类型 参考{@DfaAbstractHandler}类中的{@MATCH_TYPE}变量
     * @return 返回敏感词集合
     */
    public Set<String> getSensitiveWordInText(String text, Enum matchType) {
        return getSensitiveWordInText(dfaWordMap,text,matchType);
    }

    /**
     * 获取文本中的敏感词, 默认最小模式匹配
     * @param text 文本
     * @return 返回敏感词集合
     */
    public Set<String> getSensitiveWordInText(String text) {
        return getSensitiveWordInText(dfaWordMap,text,MATCH_TYPE.MINIMUM_MATCH);
    }

    /**
     * 替换文本中的敏感词
     * @param text 文本
     * @param replaceChar 代表敏感词的字符，替换后文本将使用这里指定的符号代表敏感词
     * @param matchType 敏感词匹配类型 参考{@DfaAbstractHandler}类中的{@MATCH_TYPE}变量
     * @return 返回替换后的文本
     */
    public String replaceSensitiveWord(String text, Enum matchType) {
        return replaceSensitiveWord(dfaWordMap,text,replacement.charAt(0),matchType);
    }

    /**
     * 替换文本中的敏感词,默认最小模式匹配
     * @param text 文本
     * @return 返回替换后的文本
     */
    public String replaceSensitiveWord(String text) {
        return replaceSensitiveWord(dfaWordMap,text,replacement.charAt(0),MATCH_TYPE.MINIMUM_MATCH);
    }




    @Override
    public void run(ApplicationArguments args) throws Exception {
        // 这里主要是初始化操作
        this.wordModelSet = loadSensitiveWordResources();
        this.dfaWordMap = new HashMap<>(wordModelSet.size());
        init(this.dfaWordMap,wordModelSet);
    }
}

结果：

测试结果

  • 版权声明： 本博客所有文章除特别声明外，著作权归作者所有。转载请注明出处！

请我喝杯咖啡吧~

支付宝
微信