首頁圖片引用自：[互聯(lián)網(wǎng)潛規(guī)則：如何進行敏感詞屏蔽](https://www.iyunying.org/yunying/yyjc/81040.html)
敏感詞算法的對比
現(xiàn)在社區(qū)內(nèi)敏感詞算法大致實現(xiàn)有兩種：DFA(Deterministic Finite Automaton 確定有窮自動機)算法和AC(Aho-Corasick自動機)算法，在掘金社區(qū)找到比較有代表性的兩篇文章：《js實現(xiàn)敏感詞過濾算法》和《開源了一個 JavaScript 版敏感詞過濾庫》
二者代碼我都看了一下，從我角度上來做一個簡單對比(其中DFA算法是在原作者基礎(chǔ)上的一些改動之后的版本)
當(dāng)前測試的電腦是MacBook Pro (Retina, 15-inch, Mid 2015)，CPU性能是2.2 GHz Intel Core i7
代碼實現(xiàn)上
AC算法相對復(fù)雜，所以其實現(xiàn)方案也比較復(fù)雜，沒有拿出紙和筆的話還真的挺難讀懂的。但是DFA算法就比較簡單易懂了，看著代碼就能大概完成整個實現(xiàn)邏輯的構(gòu)建。所以從代碼的實現(xiàn)以及可讀性，DFA算法算是比較深得我心吧
DFA算法占優(yōu)
代碼功能上
AC算法的作者提供了諸多功能，比如支持快查詢，支持臨時添加單詞等等，而第一種算法在我的改進后目前只支持快查詢，所以這個功能層面AC算法略好，不過并不意味這DFA算法這些功能就實現(xiàn)不了，只是看大家需不需要了，需要的話我將會在開源庫中不斷完善。
AC算法占優(yōu)
算法時間和空間上
接下去說說算法的耗時和內(nèi)存占用，下面是我使用的benchmark腳本，測試數(shù)據(jù)可以在這里看到：傳送門，腳本如下：
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')
}
// 內(nèi)存的測試需要單獨跑，否則二者之間會有相互沖突的情況
// benchmarkForDFAalgorithm()
// benchmarkForACalgorithm()
我們直接以100000個詞匯作為敏感詞匯去構(gòu)建，并輸入100000個單詞去檢索，得到的測試結(jié)果如下：(內(nèi)存的數(shù)據(jù)是單獨函數(shù)跑的，要不因為GC問題可能測試不準(zhǔn)確)
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
從上面的測試結(jié)果，AC的測試結(jié)果和原作者提供的大致一直，并且可以看出在詞匯樹的構(gòu)建和內(nèi)存占用上，DFA算法遠(yuǎn)遠(yuǎn)比AC算法好，執(zhí)行搜索的時候，二者才不相上下，因此這回合DFA算法占優(yōu)
DFA算法占優(yōu)
結(jié)論
最后綜上所述，結(jié)論如下：
- 如果你要簡單判斷少量詞匯，二者都可以使用
- 如果你的敏感詞匯很大，那么建議你使用DFA算法
《js實現(xiàn)敏感詞過濾算法》的代碼改動
原文作者已經(jīng)介紹了很多DFA算法的思路，這里就不再贅述，因為原作者將校驗的函數(shù)分成了兩個，容易遺漏掉第二個函數(shù)filterSensitiveWord。所以我就想整合成一個函數(shù)，一開始想著使用遞歸的尾調(diào)用來實現(xiàn)的，偽代碼實現(xiàn)如下：
checkSensitiveWord(sensitiveMap: wordMap, txt: string, index: number) {
let currentMap = sensitiveMap;
// const matchWords = new Map()
let wordNum = 0;//記錄過濾
let sensitiveWord = ''; //記錄過濾出來的敏感詞
// 遞歸到結(jié)尾了，結(jié)束遞歸
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) {
// 表示已到詞的結(jié)尾，將該敏感詞存儲起來
存儲的代碼....
// 再繼續(xù)遞歸
return this.checkSensitiveWord(sensitiveMap, txt, index + 1)
}
} else {
return this.checkSensitiveWord(sensitiveMap, txt, index + 1)
}
}
}
結(jié)果因為nodejs從版本8開始不再支持遞歸尾調(diào)用的優(yōu)化，所以這段代碼如果檢查比較少的文本的話是沒問題，但是文本量一旦變大，就很容易造成棧溢出了。
所以還是老老實實地使用循環(huán)遍歷的方式，并增加支持快速搜索的功能，最后的代碼如下
/**
* 檢查搜尋的文本是否含有敏感詞匯
* @param txt 需要查找敏感詞的文本
* @param sensitiveWordsMap 敏感詞匯的Map結(jié)構(gòu)，允許自定義，如果自定義需要使用上面的函數(shù)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) {
// 如果是快速查找，不關(guān)心敏感詞的搜索結(jié)果，找到一個即返回，適用于正常的輸入檢測
if (isQuickSearch) {
return true
}
// 表示已到詞的結(jié)尾
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
順便開源了一個工具庫
眼尖的童鞋發(fā)現(xiàn)了，這些函數(shù)不僅僅是直接粘貼復(fù)制使用，而是隸屬于這個工具庫awesome-js，是的，這就是要給大家安利的開源工具庫，該工具庫包含了很多我在平時業(yè)務(wù)開發(fā)中用到的一些公共函數(shù)，目前分為四大塊：數(shù)學(xué)工具、正則表達式工具、輔助工具以及http處理工具。
怎么使用這個工具庫呢？
下載
npm install awesome-js --save
yarn add awesome-js
使用
使用import { AwesomeHelp } from 'awesome-js'即可正常使用
提供了哪些功能呢？
得益于ts的類型定義，我們?nèi)シ环璽ypes文件就行了，為了讓大家省事，貼在這里也無妨~
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 隱私手機號，會將手機號的中間四位數(shù)替換成*
*/
export const privacyMobile: (mobile: string) => string;
/**
* @description 姓名脫敏，將除第一個字之外的非空字符替換為*
*/
export const privacyName: (name: string) => string;
/**
* @description 匹配中文字符和全角字符
*/
export const chineseAndfullWidthChar: RegExp;
/**
* @description 匹配image標(biāo)簽里面的src屬性,常用于將src的http去掉
*/
export const imgSrc: RegExp;
/**
* @description 簡單的匹配身份證號
*/
export const simpleIdentityNo: RegExp;
/**
* @description 匹配中文名字
*/
export const chineseName: RegExp;
/**
* @description 匹配正整數(shù)
*/
export const positiveInteger: RegExp;
/**
* @description 匹配整數(shù)
*/
export const integer: RegExp;
/**
* @description 匹配負(fù)整數(shù)
*/
export const negativeInteger: RegExp;
/**
* @description 匹配非負(fù)整數(shù)
*/
export const nonnegativeInteger: RegExp;
/**
* @description 匹配非正整數(shù)
*/
export const nonPostiveInterger: RegExp;
/**
* @description 匹配正浮點數(shù)
*/
export const postiveFloat: RegExp;
/**
* @description 匹配負(fù)浮點數(shù)
*/
export const negativeFloat: RegExp;
/**
* @description 匹配浮點數(shù)
*/
export const float: RegExp;
/**
* @description 匹配非負(fù)浮點數(shù)
*/
export const nonNegativeFloat: RegExp;
/**
* @description 匹配非正浮點數(shù)
*/
export const nonPositiveFloat: RegExp;
/**
* @description 匹配英文26個字母
*/
export const alphabat: RegExp;
/**
* @description 匹配大寫的英文字母
*/
export const upperAlpha: RegExp;
/**
* @description 匹配小寫的英文字母
*/
export const lowerAlpha: RegExp;
/**
* @description 匹配英文字母和數(shù)字加下劃線
*/
export const alphaNumWithUnderline: RegExp;
/**
* @description 匹配雙字節(jié)字符
*/
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 根據(jù)對象的某些字段的值對數(shù)組對象進行分類
* @param list 需要分類的數(shù)組對象(必須是一個數(shù)組)
* @param fields 需要分類的字段(必須傳遞一個函數(shù), 支持多個字段)
*/
export function groupBySomeFields<T>(list: T[], fields: (item: T) => any[]): T[][]
/**
* @description 對Date的擴展，將 Date 轉(zhuǎn)化為指定格式的String
* @param date 需要轉(zhuǎn)換格式的日期
* @param format 日期轉(zhuǎn)換的最后格式，比如YYYY-MM-DD
*/
export function convertDate(date: Date, format: string): string
/**
* @description 浮點數(shù)相加
*/
export function addFloat(arg1: number, arg2: number): number
/**
* @description 浮點數(shù)相減
*/
export function minusFloat(arg1: number, arg2: number): number
/**
* @description 浮點數(shù)相除
*/
export function divFloat(arg1: number, arg2: number): number
/**
* @description 浮點數(shù)相乘
*/
export function timesFloat(arg1: number, arg2: number): number
export function makeDeferred(): Deferred
/**
* @description 判斷是否是生成器
*/
export function isGenerator(obj: any): boolean
/**
* @description 判斷是否是生成器函數(shù)
*/
export function isGeneratorFunction(obj: any): boolean
/**
* @description 判斷是否是Promise
*/
export function isPromise(obj: any): boolean
/**
* @description 千分法計數(shù)
*/
export function toThousands(num: number): string
/**
* 隱藏所有的數(shù)字位除了指定的某一位，比如需要轉(zhuǎn)換100000的所有0為？，那么就要這樣調(diào)用hiddenNumberExpectSpecified(100000, 0, '?') => 1?????
* @param num 需要操作的數(shù)字
* @param expected 不想被隱藏的位數(shù)，從左邊最高index開始算起,默認(rèn)是最高位也就是0
* @param hiddenStr 希望隱藏的數(shù)字轉(zhuǎn)換成哪個字符，默認(rèn)是?
*/
export function hiddenNumberExpectSpecified(num: number, expected: number, hiddenStr: string): string
/**
* 將所有的敏感詞匯組成一個嵌套的Map結(jié)構(gòu)，使用的是DFA數(shù)據(jù)結(jié)構(gòu)算法
* @param sensitiveWordList
*/
export function makeSensitiveMap(sensitiveWordList: string[]): wordMap
/**
* 檢查搜尋的文本是否含有敏感詞匯
* @param txt 需要查找敏感詞的文本
* @param sensitiveWordsMap 敏感詞匯的Map結(jié)構(gòu)，允許自定義，如果自定義需要使用上面的函數(shù)makeSensitiveMap去生成，如果沒有傳，默認(rèn)使用自帶的敏感詞庫
* @param isQuickSearch 是否需要快速查詢,默認(rèn)是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 計算多邊形的中間點的坐標(biāo)(經(jīng)緯度)
*/
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
/**
* 轉(zhuǎn)換經(jīng)度或者緯度為地圖可識別的格式
* @param origin
*/
export function decodeLatLng(origin: number): number
/**
*
* @param origin 轉(zhuǎn)換經(jīng)度或者緯度為整數(shù)格式
*/
export function encodeLatLng(origin : number): number
}
export namespace AwesomeHttp {
/**
* @description 更新url中query請求的某個參數(shù),可以配合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，添加更多函數(shù)，方便你我他我也會不斷更新該工具庫，歡迎watch
