Сравнение алгоритмов конфиденциальных слов
В настоящее время в сообществе существует два типа алгоритмов конфиденциальных слов: DFA (Deterministic Finite AutomatonДетерминированные конечные автоматы) и алгоритм AC (автомат Ахо-Корасика), в сообществе Nuggets были найдены две репрезентативные статьи:«js реализует алгоритм фильтрации чувствительных слов»а также«Откройте версию JavaScript Sensitive Word Filter»
Я видел код из моего угла, чтобы сделать простой контрастность (где алгоритм DFA - это версия после оригинального автора, версии)
Тестируемый в настоящее время компьютерMacBook Pro (Retina, 15 дюймов, середина 2015 г.), производительность процессора 2,2 ГГц Intel Core i7
реализация кода
Алгоритм AC относительно сложен, поэтому его реализация также относительно сложна, и его действительно трудно читать, не доставая ручку и бумагу. Однако алгоритм DFA относительно прост и понятен, а построение всей логики реализации можно примерно завершить, взглянув на код. Итак, судя по реализации и удобочитаемости кода, алгоритм DFA довольно популярен в моем сердце.
Алгоритм DFA доминирует
Кодовая функция
Автор алгоритма AC предоставляет множество функций, таких как поддержка быстрого запроса, временное добавление слов и т. д., а первый алгоритм поддерживает только быстрый запрос после моего улучшения, поэтому алгоритм AC немного лучше на этом функциональном уровне, но это не означает, что функции этого алгоритма DFA не могут быть реализованы, это просто зависит от того, нужен он вам или нет, если нужно, я продолжу его улучшать в библиотеке с открытым исходным кодом.
Алгоритм переменного тока доминирует
Алгоритмы во времени и пространстве
Далее, давайте поговорим о времени и использовании памяти алгоритма.Ниже приведен тестовый скрипт, который я использовал.Тестовые данные можно увидеть здесь:портал, сценарий такой:
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()
Мы напрямую используем 100 000 слов в качестве конфиденциальных слов для построения и вводим 100 000 слов для извлечения, и полученные результаты теста следующие: (данные в памяти обрабатываются отдельной функцией, или тест может быть неточным из-за проблем с сборщиком мусора)
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 доминирует
В заключение
«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, Да, это библиотека инструментов с открытым исходным кодом для Amway. Эта библиотека инструментов содержит множество общедоступных функций, которые я использую в своем обычном развитии бизнеса. В настоящее время она разделена на четыре части: математические инструменты, инструменты регулярных выражений, вспомогательные инструменты инструменты и http инструменты обработки.
Как использовать эту библиотеку инструментов?
скачать
npm install awesome-js --save
yarn add awesome-js
использовать
использоватьimport { AwesomeHelp } from 'awesome-js'Обычное использование
Какие функции предусмотрены?
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
}