敏感词过滤算法对比，顺便开源了个工具库_有哪些过滤语句的开源模型

敏感词算法的对比

现在社区内敏感词算法大致实现有两种：DFA(Deterministic Finite Automaton 确定有穷自动机)算法和AC(Aho-Corasick自动机)算法，在掘金社区找到比较有代表性的两篇文章：《js实现敏感词过滤算法》和《开源了一个 JavaScript 版敏感词过滤库》

二者代码我都看了一下，从我角度上来做一个简单对比(其中DFA算法是在原作者基础上的一些改动之后的版本)

当前测试的电脑是MacBook Pro (Retina, 15-inch, Mid 2015)，CPU性能是2.2 GHz Intel Core i7

代码实现上

AC算法相对复杂，所以其实现方案也比较复杂，没有拿出纸和笔的话还真的挺难读懂的。但是DFA算法就比较简单易懂了，看着代码就能大概完成整个实现逻辑的构建。所以从代码的实现以及可读性，DFA算法算是比较深得我心吧

DFA算法占优

代码功能上

AC算法的作者提供了诸多功能，比如支持快查询，支持临时添加单词等等，而第一种算法在我的改进后目前只支持快查询，所以这个功能层面AC算法略好，不过并不意味这DFA算法这些功能就实现不了，只是看大家需不需要了，需要的话我将会在开源库中不断完善。

AC算法占优

算法时间和空间上

接下去说说算法的耗时和内存占用，下面是我使用的benchmark脚本，测试数据可以在这里看到：传送门，脚本如下：

const { makeSensitiveMap, checkSensitiveWord } = require('../dist/help')
const FastScanner = require('fastscan')
const fs = require('fs')
const path  = require('path')

function loadOneHundredThousandSentences() {
  const data = fs.readFileSync(path.resolve(__dirname, './sensitiveWords.txt'), 'utf8')
  const wordsArray = data.trim().split('|')
  console.log(`Now we have sensitive words length is: [${wordsArray.length}]`)
  return wordsArray
}

function loadOneHundredThousandWords() {
  const data = fs.readFileSync(path.resolve(__dirname, './beCheckedWords.txt'), 'utf8')
  const words = data.trim()
  console.log(`Now we have checking words length is: [${words.length}]`)
  return words
}

function benchmarkForDFAalgorithm() {
  const wordsArray = loadOneHundredThousandSentences()
  const before = process.memoryUsage()
  console.time('DFA algorithm load sensitive map tree')
  const wordMaps = makeSensitiveMap(wordsArray)
  console.timeEnd('DFA algorithm load sensitive map tree')
  const after = process.memoryUsage()
  console.log("DFA algorithm build tree of %d words costs rss=%dM heapTotal=%dM heapUsed=%dM", wordsArray.length, (after.rss-before.rss) >> 20, (after.heapTotal - before.heapTotal) >> 20, (after.heapUsed - before.heapUsed) >> 20)

  const toBeCheckedWords = loadOneHundredThousandWords()
  console.time('DFA algorithm check one hundred thousand words')
  checkSensitiveWord(toBeCheckedWords, false, wordMaps)
  console.timeEnd('DFA algorithm check one hundred thousand words')

}

function benchmarkForACalgorithm() {
  const wordsArray = loadOneHundredThousandSentences()
  const before = process.memoryUsage()
  console.time('AC algorithm load sensitive map tree')
  const scanner = new FastScanner(wordsArray)
  console.timeEnd('AC algorithm load sensitive map tree')
  const after = process.memoryUsage()
  console.log("AC algorithm build tree of %d words costs rss=%dM heapTotal=%dM heapUsed=%dM", wordsArray.length, (after.rss-before.rss) >> 20, (after.heapTotal - before.heapTotal) >> 20, (after.heapUsed - before.heapUsed) >> 20)

  const toBeCheckedWords = loadOneHundredThousandWords()
  console.time('AC algorithm check one hundred thousand words')
  scanner.search(toBeCheckedWords)
  console.timeEnd('AC algorithm check one hundred thousand words')
}

// 内存的测试需要单独跑，否则二者之间会有相互冲突的情况
// benchmarkForDFAalgorithm()
// benchmarkForACalgorithm()
复制代码
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

我们直接以100000个词汇作为敏感词汇去构建，并输入100000个单词去检索，得到的测试结果如下：(内存的数据是单独函数跑的，要不因为GC问题可能测试不准确)

Now we have sensitive words length is: [107888]
DFA algorithm load sensitive map tree: 244.374ms
DFA algorithm build tree of 107888 words costs rss=121M heapTotal=117M heapUsed=98M
Now we have checking words length is: [100000]
DFA algorithm check one hundred thousand words: 98.768ms

Now we have sensitive words length is: [107888]
AC algorithm load sensitive map tree: 1529.913ms
AC algorithm build tree of 107888 words costs rss=174M heapTotal=161M heapUsed=136M
Now we have checking words length is: [100000]
AC algorithm check one hundred thousand words: 98.532ms
复制代码
1
2
3
4
5
6
7
8
9
10
11
12

从上面的测试结果，AC的测试结果和原作者提供的大致一直，并且可以看出在词汇树的构建和内存占用上，DFA算法远远比AC算法好，执行搜索的时候，二者才不相上下，因此这回合DFA算法占优

DFA算法占优

结论

最后综上所述，结论如下：

• 如果你要简单判断少量词汇，二者都可以使用
• 如果你的敏感词汇很大，那么建议你使用DFA算法

《js实现敏感词过滤算法》的代码改动

原文作者已经介绍了很多DFA算法的思路，这里就不再赘述，因为原作者将校验的函数分成了两个，容易遗漏掉第二个函数filterSensitiveWord。所以我就想整合成一个函数，一开始想着使用递归的尾调用来实现的，伪代码实现如下：

checkSensitiveWord(sensitiveMap: wordMap, txt: string, index: number) {
  let currentMap = sensitiveMap;
  // const matchWords = new Map()
  let wordNum = 0;//记录过滤
  let sensitiveWord = ''; //记录过滤出来的敏感词
  // 递归到结尾了，结束递归
  if (index === txt.length) {
    return
  }
  for (let i = index; i < txt.length; i++) {
    const word = txt.charAt(i);
    currentMap = currentMap.get(word);
    if (currentMap) {
      wordNum++;
      sensitiveWord += word;
      if (currentMap.get('laster') === true) {
        // 表示已到词的结尾，将该敏感词存储起来
        存储的代码....
        // 再继续递归
        return this.checkSensitiveWord(sensitiveMap, txt, index + 1)
      }
    } else {
      return this.checkSensitiveWord(sensitiveMap, txt, index + 1)
    }
  }
}
复制代码
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

结果因为nodejs从版本8开始不再支持递归尾调用的优化，所以这段代码如果检查比较少的文本的话是没问题，但是文本量一旦变大，就很容易造成栈溢出了。

所以还是老老实实地使用循环遍历的方式，并增加支持快速搜索的功能，最后的代码如下

/**
 * 检查搜寻的文本是否含有敏感词汇
 * @param txt 需要查找敏感词的文本
 * @param sensitiveWordsMap 敏感词汇的Map结构，允许自定义，如果自定义需要使用上面的函数makeSensitiveMap去生成
 * @param isQuickSearch 是否需要快速查询，如果是的话查找到值是返回true，反之是false
 */
export function checkSensitiveWord(
  txt: string,
  isQuickSearch = false,
  sensitiveWordsMap?: wordMap) {
  const defaultMap = () => {
    const data = fs.readFileSync(path.resolve(__dirname, '../utils/sensitiveWords.txt'), 'utf8')
    const wordsArray = data.trim().split('|')
    return makeSensitiveMap(wordsArray)
  }
  const _sensitiveWordsMap = sensitiveWordsMap ? sensitiveWordsMap : defaultMap()
  const matchWords = new Map()
  for (let i = 0; i < txt.length; i++) {
    let currentMap = _sensitiveWordsMap;
    let sensitiveWord = ''; //记录过滤出来的敏感词
    for (let j = i; j < txt.length; j++) {
      const word = txt.charAt(j);
      currentMap = currentMap.get(word);
      if (currentMap) {
        sensitiveWord += word;
        if (currentMap.get('isEnd') === true) {
          // 如果是快速查找，不关心敏感词的搜索结果，找到一个即返回，适用于正常的输入检测
          if (isQuickSearch) {
            return true
          }
          // 表示已到词的结尾
          const isExist = matchWords.get(sensitiveWord)
          if (isExist) {
            isExist.push({ location: i })
            matchWords.set(sensitiveWord, isExist)
          } else {
            matchWords.set(sensitiveWord, [{ location: i }])
          }
          break
        }
      } else {
        break;
      }
    }
  }
  // 到这一步如果是快速查询还没有返回，说明没有找到敏感词
  if (isQuickSearch) {
    return false
  }
  return matchWords
}
复制代码
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

完整的实例请参考： awesome-js

顺便开源了一个工具库

眼尖的童鞋发现了，这些函数不仅仅是直接粘贴复制使用，而是隶属于这个工具库awesome-js，是的，这就是要给大家安利的开源工具库，该工具库包含了很多我在平时业务开发中用到的一些公共函数，目前分为四大块：数学工具、正则表达式工具、辅助工具以及http处理工具。

怎么使用这个工具库呢？

下载

npm install awesome-js --save

yarn add awesome-js
复制代码
1
2
3
4

使用

使用import { AwesomeHelp } from 'awesome-js'即可正常使用

提供了哪些功能呢？

得益于ts的类型定义，我们去翻一翻types文件就行了，为了让大家省事，贴在这里也无妨~

export interface Deferred {
  resolve: (value?: any) => any
  reject: (reason?: any) => void
  promise: Promise<any>
}

type wordMap = Map<string, recursiveMap | boolean>

interface recursiveMap extends wordMap {}

export namespace AwesomeRegx {
  /**
   * @description 匹配手机号码
   */
  export const phoneNumber: RegExp;
  /**
   * @description 匹配Emoji字符
   */
  export const isEmoji: RegExp;
  /**
   * @description 隐私手机号，会将手机号的中间四位数替换成*
   */
  export const privacyMobile: (mobile: string) => string;
  /**
   * @description 姓名脱敏，将除第一个字之外的非空字符替换为*
   */
  export const privacyName: (name: string) => string;
  /**
   * @description 匹配中文字符和全角字符
   */
  export const chineseAndfullWidthChar: RegExp;
  /**
   * @description 匹配image标签里面的src属性,常用于将src的http去掉
   */
  export const imgSrc: RegExp;
  /**
   * @description 简单的匹配身份证号
   */
  export const simpleIdentityNo: RegExp;
  /**
   * @description 匹配中文名字
   */
  export const chineseName: RegExp;
  /**
   * @description 匹配正整数
   */
  export const positiveInteger: RegExp;
  /**
   * @description 匹配整数
   */
  export const integer: RegExp;
  /**
   * @description 匹配负整数
   */
  export const negativeInteger: RegExp;
  /**
   * @description 匹配非负整数
   */
  export const nonnegativeInteger: RegExp;
  /**
   * @description 匹配非正整数
   */
  export const nonPostiveInterger: RegExp;
  /**
   * @description 匹配正浮点数
   */
  export const postiveFloat: RegExp;
  /**
   * @description 匹配负浮点数
   */
  export const negativeFloat: RegExp;
  /**
   * @description 匹配浮点数
   */
  export const float: RegExp;
  /**
   * @description 匹配非负浮点数
   */
  export const nonNegativeFloat: RegExp;
  /**
   * @description 匹配非正浮点数
   */
  export const nonPositiveFloat: RegExp;
  /**
   * @description 匹配英文26个字母
   */
  export const alphabat: RegExp;
  /**
   * @description 匹配大写的英文字母
   */
  export const upperAlpha: RegExp;
  /**
   * @description 匹配小写的英文字母
   */
  export const lowerAlpha: RegExp;
  /**
   * @description 匹配英文字母和数字加下划线
   */
  export const alphaNumWithUnderline: RegExp;
  /**
   * @description 匹配双字节字符
   */
  export const DBC: RegExp;
  /**
   * @description 匹配空行
   */
  export const emptyLine: RegExp;
  /**
   * @description 匹配首部或者尾部有空白字符的字符串
   */
  export const emptyCharInStartAndEnd: RegExp;
  /**
   * @description 匹配中文字符
   */
  export const chinese: RegExp;
  /**
   * @description 匹配邮箱
   */
  export const email: RegExp;
  /**
   * @description 匹配url
   */
  export const url: RegExp;
  /**
   * @description 匹配ip地址
   */
  export const ip: RegExp;
  /**
   * @description 匹配电话座机
   */
  export const telPhone: RegExp;
  /**
   * @description 匹配邮政编码
   */
  export const postalCode: RegExp;
}
export namespace AwesomeHelp {
  /**
   * @description 根据对象的某些字段的值对数组对象进行分类
   * @param list 需要分类的数组对象(必须是一个数组)
   * @param fields 需要分类的字段(必须传递一个函数, 支持多个字段)
   */
  export function groupBySomeFields<T>(list: T[], fields: (item: T) => any[]): T[][]
  /**
   * @description 对Date的扩展，将 Date 转化为指定格式的String
   * @param date 需要转换格式的日期
   * @param format 日期转换的最后格式，比如YYYY-MM-DD
   */
  export function convertDate(date: Date, format: string): string
  /**
   * @description 浮点数相加
   */
  export function addFloat(arg1: number, arg2: number): number
   /**
   * @description 浮点数相减
   */
  export function minusFloat(arg1: number, arg2: number): number
     /**
   * @description 浮点数相除
   */
  export function divFloat(arg1: number, arg2: number): number
     /**
   * @description 浮点数相乘
   */
  export function timesFloat(arg1: number, arg2: number): number

  export function makeDeferred(): Deferred

  /**
   * @description 判断是否是生成器
   */
  export function isGenerator(obj: any): boolean

  /**
   * @description 判断是否是生成器函数
   */
  export function isGeneratorFunction(obj: any): boolean

  /**
   * @description 判断是否是Promise
   */
  export function isPromise(obj: any): boolean
  /**
   * @description 千分法计数
   */
  export function toThousands(num: number): string

  /**
   * 隐藏所有的数字位除了指定的某一位，比如需要转换100000的所有0为？，那么就要这样调用hiddenNumberExpectSpecified(100000, 0, '?') => 1?????
   * @param num 需要操作的数字
   * @param expected 不想被隐藏的位数，从左边最高index开始算起,默认是最高位也就是0
   * @param hiddenStr 希望隐藏的数字转换成哪个字符，默认是?
   */
  export function hiddenNumberExpectSpecified(num: number, expected: number, hiddenStr: string): string

  /**
   * 将所有的敏感词汇组成一个嵌套的Map结构，使用的是DFA数据结构算法
   * @param sensitiveWordList
   */
  export function makeSensitiveMap(sensitiveWordList: string[]): wordMap

  /**
   * 检查搜寻的文本是否含有敏感词汇
   * @param txt 需要查找敏感词的文本
   * @param sensitiveWordsMap 敏感词汇的Map结构，允许自定义，如果自定义需要使用上面的函数makeSensitiveMap去生成，如果没有传，默认使用自带的敏感词库
   * @param isQuickSearch 是否需要快速查询,默认是false，如果是的话查找到值是返回true，反之是false
   */
  export function checkSensitiveWord(
    txt: string,
    isQuickSearch?: null,
    sensitiveWordsMap?: wordMap): Map<string, { location: number}[] >
  export function checkSensitiveWord(
    txt: string,
    isQuickSearch: boolean,
    sensitiveWordsMap?: wordMap): boolean
}

export namespace AwesomeMath {
  export class Region {
    constructor(points: number[][])
  /**
   * @description 计算多边形的中间点的坐标(经纬度)
   */
    public centroid: () => { x: number, y: number}
  /**
   * @description 简单的匹配身份证号
   */
    private area: () => number
  }
  /**
   * @description 计算两点之间的直线距离
   * @param {number} lng1 起点纬度
   * @param {number} lat1 起点纬度
   * @param {number} lng2 终点纬度
   * @param {number} lat2 终点纬度
   * @returns {number} 两点之间的直线距离，单位：米
   */
  export function getDistance(lng1: number, lat1: number, lng2: number, lat2: number): number

  /**
   * 转换经度或者纬度为地图可识别的格式
   * @param origin
   */
  export function decodeLatLng(origin: number): number

  /**
   *
   * @param origin 转换经度或者纬度为整数格式
   */
  export function encodeLatLng(origin : number): number
}

export namespace AwesomeHttp {
  /**
   * @description 更新url中query请求的某个参数,可以配合replaceState去更新浏览器的历史记录
   * @param baseUrl 需要更新的url
   * @param key 需要更新的key
   * @param value 更新的新值
   */
  export function updateQueryStringParam(baseUrl: string, key: string, value: any): string
  /**
   * @description 解析queryObject后组合一起追加到path后面
   */
  export function queryObject2String(path: string, queryObject: object): string
}
复制代码
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

最后

欢迎大家PR，添加更多函数，方便你我他_{我也会不断更新该工具库，欢迎watch}

作者：小兀666
链接：https://juejin.im/post/5d63c86ef265da03ef7a209b

服务推荐

• 蜻蜓代理
• 代理ip
• 微信域名检测
• 微信域名拦截检测
• 微信域名在线拦截检测工具
• 微信域名在线批量拦截检测工具