敏感词过滤算法对比，顺便开源了个工具库
2019-10-16 本文已影响0人
小兀666
首页图片引用自：[互联网潜规则：如何进行敏感词屏蔽](https://www.iyunying.org/yunying/yyjc/81040.html)
敏感词算法的对比
现在社区内敏感词算法大致实现有两种：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()
我们直接以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
从上面的测试结果，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)
}
}
}
结果因为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
}
完整的实例请参考： awesome-js
顺便开源了一个工具库
眼尖的童鞋发现了，这些函数不仅仅是直接粘贴复制使用，而是隶属于这个工具库awesome-js，是的，这就是要给大家安利的开源工具库，该工具库包含了很多我在平时业务开发中用到的一些公共函数，目前分为四大块：数学工具、正则表达式工具、辅助工具以及http处理工具。
怎么使用这个工具库呢？
下载
npm install awesome-js --save
yarn add awesome-js
使用
使用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
}
最后
欢迎大家PR，添加更多函数，方便你我他我也会不断更新该工具库，欢迎watch
