首页天道酬勤AC自动机视频,js敏感词过滤器

AC自动机视频,js敏感词过滤器

张世龙 05-06 08:42 42次浏览

许多内容系统都需要过滤一些敏感的词语,例如发现里面有“fuck”、“shit”等脏话,比如“fuck you shit up”。

首先,我们需要了解敏感单词过滤的特点。

1 .敏感词很多,一般成千上万

2 .单词长度有限,一般不超过10

3 .过滤的句子长度有限,一般不过1000

根据上述特点,粗略计算,采用暴力匹配方案,复杂度达到1k*10*1k=10^7左右的运算量。

现在让我们来思考一下这个机制用于什么样的系统。 对于内容分发平台,每天调用的次数有限,例如评论功能。 不是特别频繁。 暴力匹配可能是一个好方案,因为它简单,不易出错:

是的,请不要想太多。 暴力匹配就好了。 仔细想想。 并发性不高,不会产生大量匹配过程,CPU不太忙,暴力匹配对系统影响也不大。

但是,如果在IM系统中使用呢? 例如直播。

这种系统的特点是在一段时间内同时有大量的请求。 字符串处理是消耗CPU的操作,在上述暴力匹配方式下,大量的并发请求会不会引起大量的消息延迟?

所以,现在我们需要保存多个字符串,而且迅速匹配的结构。 最适合的不是词典树,而是网络上常见的DFA (: )

对不起,我写得有点紧凑。 画面的大小有限。 )该方法的优点很明显,忽略词典的数量,计算量只剩下10*1k=1w。

上面字典树的好处很明显,但是每次都从路线上去一次的问题也会被发现。 那有什么办法呢? 有。 使用交流自动机在每个节点上记录一个故障指针,该方法经过优化,最终达到10*1k=1w。

在这里,首先推荐交流机器人的库。 https://github.com/eachain/aca和github上的交流机器人库。 此库是调试功能,可以打印整棵树,便于调试和学习。

好了,言归正传,仔细观察,故障指针指向的节点大多还不是完整的单词,往往是浪费跳跃。 所以上面的库对此进行优化,故障指针指向完整的单词,放弃失配情况。 但是同样,这也只是无限接近O(1K )。

已尝试导入7700大小的库,通常如下所示:

找到了吗? 和只有其少数故障指针是定向的。 翻阅几个画面,故障都是0这一点太常见了。 当然,这是优化后的,如果是优化前的,定向故障应该会更多。

一直以来,我们说的是一种机械扫描字符串的方法,就像“江阴毛纺厂”一样,很多时候会被误判为不会分词。 但是,那些方法超出了本篇的范围,所以在这里不说。

最后,如果大家要有敏感的单词过滤机制,而且能做出一定的误判,建议使用优化的交流自动机,99%的情况下,时间复杂度等于串串。

敏感词过滤软件在线,如何设计一级二级标题