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

许多内容系统都需要过滤一些敏感的词语，例如发现里面有“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%的情况下，时间复杂度等于串串。