豆米的画像
首页Home博客Blogs标签Tags分类Categories时间线Timeline豆米DouMi本站Website登录Login

敏感词过滤算法对比，顺便开源了个工具库

发表于 2019-08-26
更新于 2024-05-23
分类于 技术专栏
阅读量 10209
字数统计 13397
首页图片引用自：[互联网潜规则：如何进行敏感词屏蔽](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

公众号关注一波~

微信公众号

关于评论和留言

如果对本文 敏感词过滤算法对比，顺便开源了个工具库 的内容有疑问，请在下面的评论系统中留言，谢谢。

网站源码：linxiaowu66 · 豆米的博客

Follow：linxiaowu66 · Github