专栏首页普通程序员怎么设计高效的敏感词过滤系统(一)

怎么设计高效的敏感词过滤系统(一)

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)

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

本文分享自微信公众号 - 普通程序员(farmerbrag),作者:封宇

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2017-09-07

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 我是如何用 Webpack 虐待代码尺寸的 (第二回合)

    base64 从 css 中去掉, 直接使用外部文件, 因为本身这些文件只是一些表情, 显示的时候现加载影响也不大。

    普通程序员
  • ID生成策略——SnowFlake

    某个项目采用了数据库(MySQL)自增ID作为主要业务数据的主键。数据库自增ID使用简单,自动编号,速度快,而且是增量增长,按顺序存放,对于检索非常有利。

    普通程序员
  • Tigase手动安装过程

    网上已有很多Tigase的安装文档,Tigase官方文档(英文)也很详细。但是我还是要再写一下安装过程,主要原因是网上的安装文档基本都是在特别简单的环境中进行安...

    普通程序员
  • 漫画:如何合并两个有序链表

    第21题:将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

    程序员小浩
  • 18:肿瘤面积

    18:肿瘤面积 总时间限制: 1000ms 内存限制: 65536kB描述 在一个正方形的灰度图片上,肿瘤是一块矩形的区域,肿瘤的边缘所在的像素点在图片中用...

    attack
  • Zookeeper开源客户端Curator之事件监听详解

    Curator对Zookeeper典型场景之事件监听进行封装,提供了使用参考。这篇博文笔者带领大家了解一下Curator的实现方式。 引入依赖 对于Curato...

    用户1161110
  • 重温数据结构:二叉排序树的查找、插入、删除

    我们知道,二分查找可以缩短查找的时间,但是有个要求就是 查找的数据必须是有序的。每次查找、操作时都要维护一个有序的数据集,于是有了二叉排序树这个概念。 上篇文章...

    张拭心 shixinzhang
  • 零基础学并查集算法

    并查集是我暑假从高手那里学到的一招,觉得真是太精妙的设计了。以前我无法解决的一类问题竟然可以用如此简单高效的方法搞定。不分享出来真是对不起party了。(pa...

    Angel_Kitty
  • 东京奥运会将部署人脸识别技术

    2020年东京奥运会和残奥会将运用脸部识别技术来提高效率和保证安全。 ? 据组委会的消息人士透露,2020年东京奥运会和残奥会将采用面部识别技术,以简化运动员、...

    人工智能快报
  • 绝对想尝试的创意 Android 库,你关注了吗?| 码云周刊第 43 期

    码云项目推荐 随着 Android 开发走向成熟,每天都会涌现出各种各样与 Android 相关的开发工具,但是我们每天使用的各类库总是不可或缺的。这里,小...

    码云Gitee

扫码关注云+社区

领取腾讯云代金券