当前位置: 首页 > 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在水泵、筋膜枪、吸尘器和电动工具等设备中的应用优势和特点。 …...

C++:std::is_convertible

C++标志库中提供is_convertible,可以测试一种类型是否可以转换为另一只类型: template <class From, class To> struct is_convertible; 使用举例: #include <iostream> #include <string>using namespace std;struct A { }; struct B : A { };int main…...

在HarmonyOS ArkTS ArkUI-X 5.0及以上版本中,手势开发全攻略:

在 HarmonyOS 应用开发中&#xff0c;手势交互是连接用户与设备的核心纽带。ArkTS 框架提供了丰富的手势处理能力&#xff0c;既支持点击、长按、拖拽等基础单一手势的精细控制&#xff0c;也能通过多种绑定策略解决父子组件的手势竞争问题。本文将结合官方开发文档&#xff0c…...

蓝牙 BLE 扫描面试题大全(2):进阶面试题与实战演练

前文覆盖了 BLE 扫描的基础概念与经典问题蓝牙 BLE 扫描面试题大全(1)&#xff1a;从基础到实战的深度解析-CSDN博客&#xff0c;但实际面试中&#xff0c;企业更关注候选人对复杂场景的应对能力&#xff08;如多设备并发扫描、低功耗与高发现率的平衡&#xff09;和前沿技术的…...

服务器硬防的应用场景都有哪些?

服务器硬防是指一种通过硬件设备层面的安全措施来防御服务器系统受到网络攻击的方式&#xff0c;避免服务器受到各种恶意攻击和网络威胁&#xff0c;那么&#xff0c;服务器硬防通常都会应用在哪些场景当中呢&#xff1f; 硬防服务器中一般会配备入侵检测系统和预防系统&#x…...

VTK如何让部分单位不可见

最近遇到一个需求&#xff0c;需要让一个vtkDataSet中的部分单元不可见&#xff0c;查阅了一些资料大概有以下几种方式 1.通过颜色映射表来进行&#xff0c;是最正规的做法 vtkNew<vtkLookupTable> lut; //值为0不显示&#xff0c;主要是最后一个参数&#xff0c;透明度…...

Android Bitmap治理全解析:从加载优化到泄漏防控的全生命周期管理

引言 Bitmap&#xff08;位图&#xff09;是Android应用内存占用的“头号杀手”。一张1080P&#xff08;1920x1080&#xff09;的图片以ARGB_8888格式加载时&#xff0c;内存占用高达8MB&#xff08;192010804字节&#xff09;。据统计&#xff0c;超过60%的应用OOM崩溃与Bitm…...

Swagger和OpenApi的前世今生

Swagger与OpenAPI的关系演进是API标准化进程中的重要篇章&#xff0c;二者共同塑造了现代RESTful API的开发范式。 本期就扒一扒其技术演进的关键节点与核心逻辑&#xff1a; &#x1f504; 一、起源与初创期&#xff1a;Swagger的诞生&#xff08;2010-2014&#xff09; 核心…...

rnn判断string中第一次出现a的下标

# coding:utf8 import torch import torch.nn as nn import numpy as np import random import json""" 基于pytorch的网络编写 实现一个RNN网络完成多分类任务 判断字符 a 第一次出现在字符串中的位置 """class TorchModel(nn.Module):def __in…...

push [特殊字符] present

push &#x1f19a; present 前言present和dismiss特点代码演示 push和pop特点代码演示 前言 在 iOS 开发中&#xff0c;push 和 present 是两种不同的视图控制器切换方式&#xff0c;它们有着显著的区别。 present和dismiss 特点 在当前控制器上方新建视图层级需要手动调用…...

LLMs 系列实操科普(1)

写在前面&#xff1a; 本期内容我们继续 Andrej Karpathy 的《How I use LLMs》讲座内容&#xff0c;原视频时长 ~130 分钟&#xff0c;以实操演示主流的一些 LLMs 的使用&#xff0c;由于涉及到实操&#xff0c;实际上并不适合以文字整理&#xff0c;但还是决定尽量整理一份笔…...