文档章节

【面试被虐】游戏中的敏感词过滤是如何实现的?

爱编程的浪子
 爱编程的浪子
发布于 06/27 11:30
字数 2068
阅读 32
收藏 1

小秋今天去面试了,面试官问了一个与敏感词过滤算法相关的问题,然而小秋对敏感词过滤算法一点也没听说过。于是,有了以下事情的发生…..

面试官开怼

面试官:玩过王者荣耀吧?了解过敏感词过滤吗?,例如在游戏里,如果我们发送“你在干嘛?麻痹演员啊你?”,由于“麻痹”是一个敏感词,所以当你把聊天发出来之后,我们会用“**”来代表“麻痹”这次词,所以发送出来的聊天会变成这样:“你在干嘛?**演员啊你?”。

小秋:听说过啊,在各大社区也经常看到,例如评论一个问题等,一些粗话经常被过滤掉了。

面试官:嗯,如果我给你一段文字,以及给你一些需要过滤的敏感词,你会怎么来实现这个敏感词过滤的算法呢?例如我给你一段字符串“abcdefghi",以及三个敏感词"de", "bca", "bcf"。

小秋:(敏感词过来算法??不就是字符串匹配吗?)我可以通过字符串匹配算法,例如在字符串”abcdefghi"在查找是否存在字串“de",如果找到了就把”de“用""代替。通过三次匹配之后,接变成这样了:“abcfghi"。

面试官:可以说说你采用哪种字符串匹配算法吗?

小秋:最简单的方法就是采用两个for循环保留求解了,不过每次匹配的都时间复杂度为O(n*m),我可以采用 KMP 字符串匹配算法,这样时间复杂度是 O(m+n)。

n 表示字符串的长度,m 表示每个敏感词的长度。

面试官:这是一个方法,对于敏感词过滤,你还有其他方法吗?

小秋:(其他方法?说实话,我也觉得不是采用这种 KMP 算法来匹配的了,可是,之前也没去了解过敏感词,这下要凉)对敏感词过来之前也没了解过,暂时没想到其他方法。

trie 树

面试官:了解过 trie 树吗?

小秋:(嘿嘿,数据结构这方法,我得争气点)了解过,我还用代码实现过。

面试官:可以说说它的特点吗?

小秋:trie 树也称为字典树、单词查找树,最大的特点就是共享字符串的公共前缀来达到节省空间的目的了。例如,字符串 "abc"和"abd"构成的 trie 树如下:

trie 树的根节点不存任何数据,每整个个分支代表一个完整的字符串。像 abc 和 abd 有公共前缀 ab,所以我们可以共享节点 ab。如果再插入 abf,则变成这样:

如果我再插入 bc,则是这样(bc 和其他三个字符串没有公共前缀)

面试官:那如果再插入 "ab" 这个字符串呢?

小秋:差点说了,每个分支的内部可能也含有完整的字符串,所以我们可以对于那些是某个字符串结尾的节点做一个标记,例如 abc, abd,abf 都包含了字符串 ab,所以我们可以在节点 b 这里做一个标记。如下(我用红色作为标记):

面试官:可以说说 trie 树有哪些应用吗?

小秋:trie 最大的特点就是利用了字符串的公共前缀,像我们有时候在百度、谷歌输入某个关键字的时候,它会给我们列举出很多相关的信息

这种就是通过 trie 树来实现的。

小秋:(嗯? trie 又称为单词查找树,好像可以用 trie 来实现刚才的敏感词匹配?面试官无缘无故提 trie 树难道别有用意?)

面试官:刚才的敏感词过滤,其实也可以采用 trie 来实现,你知道怎么实现吗?

trie 树来实现敏感词过滤

小秋:(果然,面试官真是个好人啊,直接提示了,要是还不知道怎么实现,那不真凉?)我想想……..我知道了,我可以这样来实现:

先把你给我的三个敏感词:"de", "bca", "bcf" 建立一颗 trie 树,如下:

接着我们可以采用三个指针来遍历,我直接用上面你给你例子来演示吧。

1、首先指针 p1 指向 root,指针 p2 和 p3 指向字符串第一个字符

2、然后从字符串的 a 开始,检测有没有以 a 作为前缀的敏感词,直接判断 p1 的孩子节点中是否有 a 这个节点就可以了,显然这里没有。接着把指针 p2 和 p3 向右移动一格。

3、然后从字符串 b 开始查找,看看是否有以 b 作为前缀的字符串,p1 的孩子节点中有 b,这时,我们把 p1 指向节点 b,p2 向右移动一格,不过,p3不动。

4、判断 p1 的孩子节点中是否存在 p2 指向的字符c,显然有。我们把 p1 指向节点 c,p2 向右移动一格,p3不动。

5、判断 p1 的孩子节点中是否存在 p2 指向的字符d,这里没有。这意味着,不存在以字符b作为前缀的敏感词。这时我们把p2和p3都移向字符c,p1 还是还原到最开始指向 root。

6、和前面的步骤一样,判断有没以 c 作为前缀的字符串,显然这里没有,所以把 p2 和 p3 移到字符 d。

7、然后从字符串 d 开始查找,看看是否有以 d 作为前缀的字符串,p1 的孩子节点中有 d,这时,我们把 p1 指向节点 b,p2 向右移动一格,不过,p3和刚才一样不动。(看到这里,我猜你已经懂了)

8、判断 p1 的孩子节点中是否存在 p2 指向的字符e,显然有。我们把 p1 指向节点 e,并且,这里e是最后一个节点了,查找结束,所以存在敏感词de,即 p3 和 p2 这个区间指向的就是敏感词了,把 p2 和 p3 指向的区间那些字符替换成 *。并且把 p2 和 p3 移向字符 f。如下:

9、接着还是重复同样的步骤,知道 p3 指向最后一个字符。

复杂度分析

面试官:可以说说时间复杂度吗?

小秋:如果敏感词的长度为 m,则每个敏感词的查找时间复杂度是 O(m),字符串的长度为 n,我们需要遍历 n 遍,所以敏感词查找这个过程的时间复杂度是 O(n * m)。如果有 t 个敏感词的话,构建 trie 树的时间复杂度是 O(t * m)。

这里我说明一下,在实际的应用中,构建 trie 树的时间复杂度我觉得可以忽略,因为 trie 树我们可以在一开始就构建了,以后可以无数次重复利用的了。

10、如果让你来 构建 trie 树,你会用什么数据结构来实现?

小秋:我一般使用 Java,我会采用 HashMap 来实现,因为一个节点的字节点个数未知,采用 HashMap 可以动态拓展,而且可以在 O(1) 复杂度内判断某个子节点是否存在。

面试官:嗯,回去等通知吧。

总结

今天主要将了 trie 树以及 trie 树的一些应用,还要就是如何通过 trie 树来实现敏感词的过滤,至于代码的实现,我这里就不给出了,在实现的时候,为了防止这种”麻 痹"或者“麻¥痹”等,我们也要对特殊字符进行过滤等,有兴趣的可以去实现一波。

© 著作权归作者所有

爱编程的浪子
粉丝 5
博文 65
码字总数 162626
作品 0
长沙
私信 提问
【面试被虐】腾讯面试必备题解析:游戏中的敏感词过滤是如何实现的?

文末有面试资料免费领取 小秋今天去面试了,面试官问了一个与敏感词过滤算法相关的问题,然而小秋对敏感词过滤算法一点也没听说过。于是,有了以下事情的发生….. 面试官开怼 面试官:玩过王...

我最喜欢三大框架
05/09
0
0
利用函数计算实现网络游戏或视频直播中的敏感词检测

一、概述 目前,网络游戏和视频直播都是很火爆的产业,然而,无论在多人在线网络游戏(MMORPG)中,还是在游戏视频直播或者其他直播中(弹幕),玩家或者用户的在线交流和互动都是它们的核心乐趣...

rsong
2017/12/26
0
0
5分钟Serverless实践 | 构建无服务器的敏感词过滤后端系统

前言 在上一篇“5分钟Serverless实践”系列文章中,我们介绍了什么是Serverless,以及如何构建一个无服务器的图片鉴黄Web应用,本文将延续这个话题,以敏感词过滤为例,介绍如何构建一个无服...

中间件小哥
2018/08/22
0
0
python实现敏感词过滤的几种方法

1.replace过滤 最简单也是最直接的就是直接循环敏感词,然后使用replace过滤关键词,文章和敏感词少的时候还可以,多的时候效率就真的很一般了。 2.使用正则过滤 有两个技术要点, 1.使用Pyt...

俊采星驰_87e0
2018/11/21
0
0
编程珠玑 - 算法优化 - 过滤敏感词

编程珠玑 - 算法优化 - 过滤敏感词 - 第一步:快速实现 http://my.oschina.net/fangxu/blog/32380 编程珠玑 - 算法优化 - 过滤敏感词 - 第二步:效率问题 http://my.oschina.net/fangxu/blo...

方旭
2011/09/21
5.3K
12

没有更多内容

加载失败,请刷新页面

加载更多

Linux的基本命令

目录的操作命令(增删改查) 增: mkdir 目录名称; 查: ls 可以看到该目录下的所有的目录和文件 ls -a,可以看到该目录下的所有文件和目录,包括隐藏的 ls -l,可以看到该目录下的所有目录和...

凹凸凸
今天
2
0
在古老unix中增加新用户

Installing 4.3 BSD Quasijarus on SIMH 目标:要在4.3BSD中新增加用户dmr,指定目录/home/dmr,uid为10 gid=31(guest组,系统已建立) 4.3BSD还没有adduser或useradd 直接修改/etc/passwd...

wangxuwei
今天
2
0
Bootstrap(六)表单样式

基本样式 所有设置了 .form-control 类的 <input>、<textarea> 和 <select> 元素都将被默认设置宽度属性为 width: 100%;。 将 label 元素和前面提到的控件包裹在 .form-group 中可以获得最好...

ZeroBit
昨天
3
0
SSL 证书格式转换

SSL 证书格式转换 不同服务器情况下,需要不同的证书格式。 比如 pem 转 pfx。 pem在window 平台下可以导入,但是无法正常使用。 需要转换成pfx。 推荐在线转换工具,由中国数字证书网站提供...

DrChenXX
昨天
2
0
HAProxy

xx

Canaan_
昨天
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部