当前位置: 首页 > news >正文

DFA算法实现敏感词过滤

DFA算法实现敏感词过滤

需求:检测一段文本中是否含有敏感词。

比如检测一段文本中是否含有:“滚蛋”,“滚蛋吧你”,“有病”,

可使用的方法有:

  • 遍历敏感词,判断文本中是否含有这个敏感词。
for (keyword in [“滚蛋”、“滚蛋吧你”、“有病”]) {if (text.indexOf(keyword) != -1) {return true;}
}
return false;
  • 使用正则表达式
Pattern pattern = Pattern.compile("滚蛋|滚蛋吧你|有病"); // 编写正则表达式
Matcher matcher = pattern.matcher(text); // 编写正则表达式
return matcher.matches(); 

以上两个方法,随着敏感词的增加,效率会越来越低。

而我们使用DFA算法只需遍历一遍文本,就可以找出文本中所有敏感词。

DFA算法

我先大致讲讲DFA算法是怎么做到敏感词过滤的。

DFA查找过程

  • DFA算法会维护一个map结构的敏感词库

    map结构就是一个个key、value。在一个key,value中,【key里装的是敏感词的首个字符】,【value又是一个map结构】,这个value里一般存储两对key,value:一对key,value的key是isEnd变量,value为0表示这个字符不是这个敏感词的最后一个字符;value为1表示这个字符是这个敏感词的最后一个字符。另一对key,value的key里装的则是下一个字符,value则又是一个map结构……;

    也就是说对于每个敏感词的一个字符中,都记录着这个字符是否为最后一个,如果不是最后一个的话还记录下一个字符的信息。

    在这里插入图片描述

    画成树的结构就是这样:
    在这里插入图片描述

  • 遍历文本中的每个字符,【此时的map的key都是敏感词的第一个字符】。

  • 如果map.get(这个字符)不为空,表示这个字符可能是敏感词的第一个字符

  • 获取这个敏感词字符的下一个字符信息,和isEnd信息。【此时的map的key是下一个字符】。判断isEnd是否为1,为1表示匹配到敏感词,结束。

  • 不为1,继续遍历文本的下一个字符,判断map.get(这个字符)是否为空。

  • 如果不为空,获取这个敏感词字符的下一个字符信息,和isEnd信息。【此时的map的key是下一个字符】。判断isEnd是否为1,为1表示匹配到敏感词,结束。

  • 不为1,……

  • 直到isEnd为1

上面的步骤归纳起来,一个循环主要做的就是

  • map.get(这个字符)
  • 是否为空,不为空,获取这个敏感词字符的下一个字符信息和isEnd信息。如果isEnd为1,结束
  • 继续循环遍历。

经过上述步骤,就可以匹配到一个敏感词,如果文本中有多个敏感词炸糕?将文本中的每个字符作为初始字符,都经过上面步骤的匹配,最终都可以找到文本中包含的所有敏感词。

敏感词库初始化

知道了大致匹配的过程后,就是要构建一个敏感词库,也就是给你一堆敏感词,构建一个map结构。如下图:

在这里插入图片描述

与匹配差不多思路:

  • 遍历敏感词的每一个字符

  • curMap一开始就是表示敏感词一个字符的map结构

  • Map<String, Object> wordMap = (Map<String, Object>) curMap.get(key);

  • 如果wordMap 为空,则建一个wordMap ,这个wordMap 涵盖两个信息:下一个字符、isEnd

  • 不管wordMap 为不为空,curMap被赋值为wordMap ,表示下一个字符的map结构。

  • ……循环

/*** 生成敏感词库* @param words* @return*/
private Map<String, Object> handleToMap(Collection<String> words) {if (words == null) {return null;}// map初始长度words.size(),整个字典库的入口字数(小于words.size(),因为不同的词可能会有相同的首字)Map<String, Object> map = new HashMap<>(words.size());// 遍历过程中当前层次的数据Map<String, Object> curMap = null;Iterator<String> iterator = words.iterator();while (iterator.hasNext()) {String word = iterator.next();curMap = map;int len = word.length();for (int i =0; i < len; i++) {// 遍历每个词的字String key = String.valueOf(word.charAt(i));// 当前字在当前层是否存在, 不存在则新建, 当前层数据指向下一个节点, 继续判断是否存在数据Map<String, Object> wordMap = (Map<String, Object>) curMap.get(key);if (wordMap == null) {// 每个节点存在两个数据: 下一个节点和isEnd(是否结束标志)wordMap = new HashMap<>(2);wordMap.put("isEnd", "0");curMap.put(key, wordMap);}curMap = wordMap;// 如果当前字是词的最后一个字,则将isEnd标志置1if (i == len -1) {curMap.put("isEnd", "1");}}}return map;
}
/*** 文本中是否含有敏感词* @param text* @param beginIndex* @return*/
private int checkWord(String text, int beginIndex) {if (dictionaryMap == null) {throw new RuntimeException("字典不能为空");}boolean isEnd = false;int wordLength = 0;Map<String, Object> curMap = dictionaryMap;int len = text.length();// 从文本的第beginIndex开始匹配for (int i = beginIndex; i < len; i++) {String key = String.valueOf(text.charAt(i));// 获取当前key的下一个节点curMap = (Map<String, Object>) curMap.get(key);if (curMap == null) {break;} else {wordLength ++;if ("1".equals(curMap.get("isEnd"))) {isEnd = true;}}}if (!isEnd) {wordLength = 0;}return wordLength;
}/*** 获取匹配到的敏感词和命中次数* @param text* @return*/
public Map<String, Integer> matchWords(String text) {Map<String, Integer> wordMap = new HashMap<>();int len = text.length();for (int i = 0; i < len; i++) {int wordLength = checkWord(text, i);if (wordLength > 0) {String word = text.substring(i, i + wordLength);// 添加敏感词匹配次数if (wordMap.containsKey(word)) {wordMap.put(word, wordMap.get(word) + 1);} else {wordMap.put(word, 1);}i += wordLength - 1;}}return wordMap;
}
put(word, wordMap.get(word) + 1);} else {wordMap.put(word, 1);}i += wordLength - 1;}}return wordMap;
}

参考:
https://www.zhihu.com/collection/922374522
https://www.jianshu.com/p/e58a148eecc5

相关文章:

DFA算法实现敏感词过滤

DFA算法实现敏感词过滤 需求&#xff1a;检测一段文本中是否含有敏感词。 比如检测一段文本中是否含有&#xff1a;“滚蛋”&#xff0c;“滚蛋吧你”&#xff0c;“有病”&#xff0c; 可使用的方法有&#xff1a; 遍历敏感词&#xff0c;判断文本中是否含有这个敏感词。 …...

Python自动化运维:技能掌握与快速入门指南

#编程小白如何成为大神&#xff1f;大学生的最佳入门攻略# 在当今快速发展的IT行业中&#xff0c;Python自动化运维已经成为了一个不可或缺的技能。本文将为您详细介绍Python自动化运维所需的技能&#xff0c;并提供快速入门的资源&#xff0c;帮助您迅速掌握这一领域。 必备…...

在linux系统中安装pygtftk软件

1.下载和安装 网址&#xff1a; https://dputhier.github.io/pygtftk/index.html ## 手动安装 git clone http://gitgithub.com:dputhier/pygtftk.git pygtftk cd pygtftk # Check your Python version (>3.8,<3.9) pip install -r requirements.txt python setup.py in…...

decodeURIComponentSafe转义%问题记录URI malformed

decodeURIComponentSafe转义%问题记录 问题背景 当我们解析包涵 % 字符的字符串时&#xff0c;会出现错误如下 Uncaught URIError: URI malformed 解决方案&#xff1a; function decodeURIComponentSafe(s) {if (!s) {return s;}return decodeURIComponent(s.replace(/%(?…...

自由学习记录(18)

动画事件的碰撞器触发 Physics 类的常用方法 RaycastHit hit; if (Physics.Raycast(origin, direction, out hit, maxDistance)) {Debug.Log("Hit: " hit.collider.name); } Physics.Raycast&#xff1a;从指定点向某个方向发射射线&#xff0c;检测是否与碰撞体…...

vue3-ref 和 reactive

文章目录 vue3 中 ref 和 reactivereactive 与 ref 不同之处ref 处理复杂类型ref在dom中的应用 vue3 中 ref 和 reactive ref原理 基本原理 ref是Vue 3中用于创建响应式数据的一个函数。它的基本原理是通过Object.defineProperty()&#xff08;在JavaScript的规范中用于定义对…...

Apache Calcite - 查询优化之自定义优化规则

RelOptRule简介 为了自定义优化规则&#xff0c;我们需要继承RelOptRule类。org.apache.calcite.plan.RelOptRule 是 Apache Calcite 中的一个抽象类&#xff0c;用于定义优化规则。优化规则是用于匹配查询计划中的特定模式&#xff0c;并将其转换为更优化的形式的逻辑。通过继…...

大型语言模型(LLM)的小型化研究进展

2024年&#xff0c;大型语言模型&#xff08;LLM&#xff09;的小型化研究取得了显著进展&#xff0c;主要采用以下几种方法实现&#xff1a; 模型融合&#xff1a;通过将多个模型或检查点合并为一个单一模型&#xff0c;减少资源消耗并提升整体性能。例如&#xff0c;《WARM: …...

MiniWord

1.nuget 下载配置 2.引用 3. var value = new Dictionary<string, object>() { ["nianfen"] = nianfen, ["yuefen"] = yuefen, ["yuefenjian1"] = (int.Par…...

Netty 常见组件介绍

Netty 常见组件介绍 上篇文章Netty入门程序echo 基本包含了Netty常见的组件&#xff0c;本文分别介绍各个组件 Bootstrap or ServerBootstrapEventLoopEventLoopGroupChannelPipelineChannelFuture or ChannelFutureChannelInitializerChannelHandler Bootstrap vs ServerBo…...

高频电子线路---倍频器与振荡器

目录 倍频电路原理 丙类倍频器原理电路 问题: 提升滤波方法: 导通角 振荡器 振荡器基本工作原理 首先是怎么维持 那么如何振荡呢? 思考题: 组成要素 振荡器的起振条件 平衡条件 要点提示 稳定条件 振幅平衡 硬激励起振时: 稳定条件 相位平衡 倍频电路原理 简单原理 : …...

删除 git submodule

直接运行下面命令即可&#xff1a; git rm <path-to-submodule>然后提交修改即可。 但是&#xff0c;还有一个小问题&#xff1a;上面命令只是将 submodule 的代码目录删除了。 以下痕迹还存在你的仓库中&#xff1a; .gitmodule 中关于该 submodule 的信息.git 目录…...

el-table 多选默认选中(根据返回的id给数据加默认选中状态)

前言 el-table是我们最常用的展示数据的方式&#xff0c;但是有时候需要用到多选来选择数据&#xff0c;新增数据的时候还好&#xff0c;选中状态都是正常的&#xff0c;但是修改就遇到问题&#xff0c;需要对这个已经选择过的数据加上默认的选中状态&#xff0c;本次就是解决…...

境外网站翻译之自由职业

Polls Do you use AI tools (e.g ChatGPT, Midjourney, Github Copilot) as part of your work? 你在工作中会使用人工智能工具&#xff08;如 ChatGPT、Midjourney、Github Copilot&#xff09;吗&#xff1f; Yes, as an assistant 是的&#xff0c;作为一种辅助工具。 Y…...

批量图片转PDF文件的多种方法详解

要将批量图片转换为PDF文件&#xff0c;可以使用多种方法&#xff0c;包括使用在线工具、桌面应用程序或编程语言。以下是几种常见的方法&#xff1a; 方法一&#xff1a;使用在线工具 选择工具&#xff1a;搜索“图片转PDF”在线工具&#xff0c;如 Smallpdf、ILovePDF 等。…...

Web服务器(理论)

目录 Web服务器www简介常见Web服务程序介绍&#xff1a;服务器主机主要数据浏览器 网址及HTTP简介URLhttp请求方法:2.3 HTTP协议请求的工作流程&#xff1a; www服务器的类型静态网站动态网站 快速安装Apache安装准备工作httpd所需目录主配置文件 nignx安装1、安装2、准备工作 …...

js:()=>(,);()的作用:明确表达式的边界。

()>{表达式1&#xff1b;表达式2&#xff1b;表达式3&#xff1b;... return 结果} 等同于 ()>(表达式1,表达式2,表达式3,... 结果&#xff09; 例子&#xff1a; const strarr [a, b, c];const result strarr.reduce((acc, curr) > {(acc[curr] 1);console.lo…...

RSI 5G通信技术中用于标识小区的特定参数

RSI是指在5G通信技术中用于标识小区的特定参数&#xff0c;全称为Radio Subframe Indicator&#xff08;无线子帧指示符&#xff09;。在原文的上下文中&#xff0c;RSI被用来确保相邻小区间有足够的间隔&#xff0c;避免由于RSI冲突导致用户设备&#xff08;UE&#xff09;随机…...

JavaScript中的闭包、递归问题

一、函数定义和调用 1.函数的定义方式 方式一 函数声明方式 function 关键字(命名函数) function fn(){}方式二 函数表达式&#xff08;匿名函数&#xff09; var fn function(){}方式三 new Function() var f new Function(a,b,console.log(a b););//语法 var fn new Fu…...

【青牛科技】GC4938替代A4938/Allegro在水泵、筋膜枪、吸尘器和电动工具中的应用

随着技术的不断进步&#xff0c;电机驱动控制器在各类电动设备中的应用越来越广泛。GC4938作为一种新型的电机驱动控制器&#xff0c;逐渐被视为A4938/Allegro的替代品。在这篇文章中&#xff0c;我们将探讨GC4938在水泵、筋膜枪、吸尘器和电动工具等设备中的应用优势和特点。 …...

UE5 学习系列(二)用户操作界面及介绍

这篇博客是 UE5 学习系列博客的第二篇&#xff0c;在第一篇的基础上展开这篇内容。博客参考的 B 站视频资料和第一篇的链接如下&#xff1a; 【Note】&#xff1a;如果你已经完成安装等操作&#xff0c;可以只执行第一篇博客中 2. 新建一个空白游戏项目 章节操作&#xff0c;重…...

华为云AI开发平台ModelArts

华为云ModelArts&#xff1a;重塑AI开发流程的“智能引擎”与“创新加速器”&#xff01; 在人工智能浪潮席卷全球的2025年&#xff0c;企业拥抱AI的意愿空前高涨&#xff0c;但技术门槛高、流程复杂、资源投入巨大的现实&#xff0c;却让许多创新构想止步于实验室。数据科学家…...

【杂谈】-递归进化:人工智能的自我改进与监管挑战

递归进化&#xff1a;人工智能的自我改进与监管挑战 文章目录 递归进化&#xff1a;人工智能的自我改进与监管挑战1、自我改进型人工智能的崛起2、人工智能如何挑战人类监管&#xff1f;3、确保人工智能受控的策略4、人类在人工智能发展中的角色5、平衡自主性与控制力6、总结与…...

阿里云ACP云计算备考笔记 (5)——弹性伸缩

目录 第一章 概述 第二章 弹性伸缩简介 1、弹性伸缩 2、垂直伸缩 3、优势 4、应用场景 ① 无规律的业务量波动 ② 有规律的业务量波动 ③ 无明显业务量波动 ④ 混合型业务 ⑤ 消息通知 ⑥ 生命周期挂钩 ⑦ 自定义方式 ⑧ 滚的升级 5、使用限制 第三章 主要定义 …...

Robots.txt 文件

什么是robots.txt&#xff1f; robots.txt 是一个位于网站根目录下的文本文件&#xff08;如&#xff1a;https://example.com/robots.txt&#xff09;&#xff0c;它用于指导网络爬虫&#xff08;如搜索引擎的蜘蛛程序&#xff09;如何抓取该网站的内容。这个文件遵循 Robots…...

CRMEB 框架中 PHP 上传扩展开发:涵盖本地上传及阿里云 OSS、腾讯云 COS、七牛云

目前已有本地上传、阿里云OSS上传、腾讯云COS上传、七牛云上传扩展 扩展入口文件 文件目录 crmeb\services\upload\Upload.php namespace crmeb\services\upload;use crmeb\basic\BaseManager; use think\facade\Config;/*** Class Upload* package crmeb\services\upload* …...

DeepSeek 技术赋能无人农场协同作业:用 AI 重构农田管理 “神经网”

目录 一、引言二、DeepSeek 技术大揭秘2.1 核心架构解析2.2 关键技术剖析 三、智能农业无人农场协同作业现状3.1 发展现状概述3.2 协同作业模式介绍 四、DeepSeek 的 “农场奇妙游”4.1 数据处理与分析4.2 作物生长监测与预测4.3 病虫害防治4.4 农机协同作业调度 五、实际案例大…...

回溯算法学习

一、电话号码的字母组合 import java.util.ArrayList; import java.util.List;import javax.management.loading.PrivateClassLoader;public class letterCombinations {private static final String[] KEYPAD {"", //0"", //1"abc", //2"…...

JVM 内存结构 详解

内存结构 运行时数据区&#xff1a; Java虚拟机在运行Java程序过程中管理的内存区域。 程序计数器&#xff1a; ​ 线程私有&#xff0c;程序控制流的指示器&#xff0c;分支、循环、跳转、异常处理、线程恢复等基础功能都依赖这个计数器完成。 ​ 每个线程都有一个程序计数…...

音视频——I2S 协议详解

I2S 协议详解 I2S (Inter-IC Sound) 协议是一种串行总线协议&#xff0c;专门用于在数字音频设备之间传输数字音频数据。它由飞利浦&#xff08;Philips&#xff09;公司开发&#xff0c;以其简单、高效和广泛的兼容性而闻名。 1. 信号线 I2S 协议通常使用三根或四根信号线&a…...