怎么设计高效的敏感词过滤系统(一)「建议收藏」

怎么设计高效的敏感词过滤系统(一)「建议收藏」最近在做一个项目,寻遍了Node开源社区居然没有发现一个好用的敏感词过滤库,有那么几个库外观上看起来似乎还不错,用起来却一塌糊涂,震惊有余,失望至极。于是花了一天时间自己撸了一个库,库名叫fastscan,这是我的第一个Node开源项目,它也可以用于浏览器环境。fastscan基于广为人知的ahocorasick高性能字符串匹配算法。项目地址:https://github….

大家好,又见面了,我是你们的朋友全栈君。

IM项目需要对上边传输的消息进行必要的过滤。如果总是对着某人输入f**k就显得不太文明了。

一个通用且简单的做法是,设定一批敏感词,如果消息中出现这些词,由系统进行必要的处理。怎么实现这个功能呢?

一、能够实现敏感词过滤功能的方法有很多

方法有很多,我简单罗列了几个。

1、直接将敏感词组织成String后,利用indexOf方法来查询。

2、传统的敏感词入库后SQL查询。

3、利用Lucene建立分词索引来查询。

4、利用DFA算法来进行。

显然,方法1和方法2在性能上基本无法满足IM系统高效处理消息的需求,放弃。

方法3,采用Lucene建立本地分词索引,将消息内容分词后,在索引库里搜索。这个方法较复杂,且分词效率也不会很高,放弃。

大多数的敏感词过滤系统采用的是方法4,DFA算法。

二、DFA简介

DFA是什么?这里有必要简单介绍一下这个概念(这部分看不懂没关系,可以跳过)。

1、DFA定义

DFA翻译成中文是“确定有穷自动机 ”

定义:一个确定有穷自动机(DFA)M是一个五元组:M=(K,Σ,f,S,Z)其中

① K是一个有穷集,它的每个元素称为一个状态;

② Σ是一个有穷字母表,它的每个元素称为一个输入符号,所以也称Σ为输入符号字母表;

③ f是转换函数,是K×Σ→K上的映射(且可以是部分函数),即,如 f(ki,a)=kj,(ki∈K,kj∈K)就意味着,当前状态为ki,输入符为a时,将转换为下一个状态kj,我们把kj称作ki的一个后继状态;

④ S ∈ K是唯一的一个初态;

⑤ Z⊂K是一个终态集,终态也称可接受状态或结束状态。

2、DFA例子

怎么设计高效的敏感词过滤系统(一)「建议收藏」

3、DFA状态图表示

假定DFA M含有m个状态,n个输入字符,那么这个状态图含有m个节点,每个节点最多有n个弧射出,整个图含有唯一一个初态点和若干个终态点,初态节点冠以双箭头“=>”,终态节点用双圈表示,若f(ki ,a)=kj,则从状态结点ki到状态节点kj画标记为a的弧。

怎么设计高效的敏感词过滤系统(一)「建议收藏」

4、DFA所接受

对于Σ* 中的任何符号串t,若存在一条从初态到某一终态的道路,且这条道路上所有弧的标记连接成的字符串等于t,则称t可为DFA M所接受,若M的初态同时又是终态,则空字可为M所识别(接受)。

即:若 t∈ Σ* , f(S, t)=P, 其中S为M的开始状态,P∈Z,Z为 终态集。

则称 t 为 DFA M所接受(识别)。

如果看懂了DFA的介绍,我们可以这么理解敏感词过滤系统。用需要被过滤的敏感词构建一个DFA(确定有穷自动机 ),然后遍历需要过滤的文本,判断文本中是否有DFA可接受(识别)的字符串即可。

如果没有看懂DFA,看下边一节也OK。

三、用Trie树构建DFA

Trie树,即字典树,又称单词查找树或键树,是一种树形结构,是一种哈希树的变种。典型应用是用于统计和排序大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计。它的优点是:最大限度地减少无谓的字符串比较,查询效率比哈希表高。

假设有b,abc,abd,bcd,abcd,efg,hii 这7个单词(实际使用中,这些单词就是敏感词),我们构建的树如下图

怎么设计高效的敏感词过滤系统(一)「建议收藏」

如上图所示,对于每一个节点,从根遍历到他的过程就是一个单词,如果这个节点被标记为红色,就表示这个单词存在,否则不存在。

过滤敏感词,就是把需要过滤的文本,从第一个字开始,逐个字往后在Trie树中查找。如果能走到树的结束节点,则就能发现敏感词!

四、防止回溯

1、回溯的场景

看一句话待过滤的文本(以下简称母串)“瓜子二手车成交量全国领先”,再看下图模拟的几个敏感词。我们来看看检索过程。

怎么设计高效的敏感词过滤系统(一)「建议收藏」

(1)第1个字“瓜”在Trie树的第一层节点(第一层节点有“二”、“瓜”、“西”三个字);继续(在中间的子树)往后找“子”字,在树枝的后续节点;继续找“二”,继续找“手”,继续找“车”,”车”字无法找到,查找失败。

(2)(这里不能从“二”字开始找,需要回溯到“子”字,万一有“子”字开始的敏感词呢 )第2个字“子”不在Trie树第一层节点,查找失败。

(3)第3个字“二”字,在Trie树第一层节点……

(4)后续文字按此方法逐字往后查找即可。

这个查找方法能够求解,但是效率不高(注意第2步),我们读到了后边的文字,但是由于没有命中,检索发生了回退,导致效率下降。事实上,我们在第1步已经比较过“二手”这个词,如果能利用第1步中比较的结果,直观感觉是能够加快匹配出“二手车”这个敏感词的。

2、前缀指针

前面的场景很像字符串查找的KMP算法,KMP算法可以防止字符串查找过程中的指针回溯。那Trie树的结构有没有办法也避免这种情况发生呢?

答案是肯定的。参考KMP算法(百度一下你就知道了) 的最长相同前后缀的方法,来避免回溯。

这里首先需要理解“前缀”、“后缀”的思想。如果不了解这两个概念,推荐一篇KMP算法讲得特别清楚的博文http://www.cnblogs.com/c-cloud/p/3224788.html(一定要读)。

为了避免回溯,参考KMP的next数组,在Trie图中定义“前缀指针 ”

“前缀指针 ”定义:从根节点到节点P可以得到一个字符串S,节点P的前缀指针定义为 指向树中出现过的S的最长后缀(不能等于S)

后续文章将详细讲解怎么高效构建“前缀指针 ”,如何快速遍历母串,以及工程上如何实现的问题。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/130164.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • navicat mac 激活码【中文破解版】[通俗易懂]

    (navicat mac 激活码)本文适用于JetBrains家族所有ide,包括IntelliJidea,phpstorm,webstorm,pycharm,datagrip等。IntelliJ2021最新激活注册码,破解教程可免费永久激活,亲测有效,下面是详细链接哦~https://javaforall.cn/ide…

  • 我的校园服务小程序_有创意校园的微信小程序

    我的校园服务小程序_有创意校园的微信小程序微信小程序——校园服务小程序(四)校园论坛加预约理发服务上一篇介绍了如何用户如何将帖子的内容发送到数据库中。这次我们来介绍一下如何将库中数据渲染出来,通过get得到对应表的数据,在wxml上通过for循环渲染数据表中的值。这里以我们的主页面为例,首先思考一下,一个展示帖子的主页面要有什么功能,1.帖子在添加时会将新的帖子放在最后,再渲染时也会被渲染在后面,这样是不可以的,每一次进入界面都是第一个用户上传的帖子。这里我们需要对帖子进行一次排序,这里我使用了orderBy(‘timeone’,‘d

  • WPF教程(二十五)WrapPanel[通俗易懂]

    WPF教程(二十五)WrapPanel[通俗易懂]WrapPanel用于一个接一个的排列子控件,以水平或者垂直方向,当空间不足时就会自动切换到下一行。适合于需要水平或者垂直排列控件且能自动换行的情况。水平方向排列时,每一行所有子控件的高度都被统一成固定的值,这个值由最高的那个决定;每一列垂直方向排列时,所有子控件的宽度都被统一成固定的值,这个值由最宽的那个决定。我们先来看默认情况下的WrapPanel:

  • 剑指 Offer 56 – II. 数组中数字出现的次数 II

    剑指 Offer 56 – II. 数组中数字出现的次数 II在一个数组 nums 中除一个数字只出现一次之外,其他数字都出现了三次。请找出那个只出现一次的数字。示例 1:输入:nums = [3,4,3,3]输出:4示例 2:输入:nums = [9,1,7,9,7,9,7]输出:1限制:1 <= nums.length <= 100001 <= nums[i] < 2^31设置一个数组代表32位,每一位代表当前所有数组中当前位出现次数之和。然后%3,然后拼凑class Solution {public: in

  • idea免费激活码-激活码分享

    (idea免费激活码)好多小伙伴总是说激活码老是失效,太麻烦,关注/收藏全栈君太难教程,2021永久激活的方法等着你。https://javaforall.cn/100143.htmlIntelliJ2021最新激活注册码,破解教程可免费永久激活,亲测有效,上面是详细链接哦~9071407CR5-eyJsaWNlbnNlSWQiOi…

  • Ubuntu18.04安装GCC8.3.0

    Ubuntu18.04安装GCC8.3.0转自:https://blog.csdn.net/bjzhaoxiao/article/details/102525241Ubuntu系统是自带GCC安装指令的aptinstallgcc,当前apt源中gcc版本为5.4.0,版本太低,推荐手动安装gcc8.3.0手动安装gcc8.3.0之前需要先确保安装gcc环境依赖GMP4.2+、MPFR2.3.1+、MPC0.8.0+,否则会报出以下错误configure:error:BuildingGCCrequiresGMP4.

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号