数据结构与算法之美
王争
前 Google 工程师
280067 人已学习
新⼈⾸单¥68
登录后,你可以任选4讲全文学习
课程目录
已完结/共 81 讲
基础篇 (38讲)
数据结构与算法之美
15
15
1.0x
00:00/00:00
登录|注册

36 | AC自动机:如何用多模式串匹配实现敏感词过滤功能?

很多支持用户发表文本内容的网站,比如 BBS,大都会有敏感词过滤功能,用来过滤掉用户输入的一些淫秽、反动、谩骂等内容。你有没有想过,这个功能是怎么实现的呢?
实际上,这些功能最基本的原理就是字符串匹配算法,也就是通过维护一个敏感词的字典,当用户输入一段文字内容之后,通过字符串匹配算法,来查找用户输入的这段文字,是否包含敏感词。如果有,就用“***”把它替代掉。
我们前面讲过好几种字符串匹配算法了,它们都可以处理这个问题。但是,对于访问量巨大的网站来说,比如淘宝,用户每天的评论数有几亿、甚至几十亿。这时候,我们对敏感词过滤系统的性能要求就要很高。毕竟,我们也不想,用户输入内容之后,要等几秒才能发送出去吧?我们也不想,为了这个功能耗费过多的机器吧?那如何才能实现一个高性能的敏感词过滤系统呢?这就要用到今天的多模式串匹配算法

基于单模式串和 Trie 树实现的敏感词过滤

我们前面几节讲了好几种字符串匹配算法,有 BF 算法、RK 算法、BM 算法、KMP 算法,还有 Trie 树。前面四种算法都是单模式串匹配算法,只有 Trie 树是多模式串匹配算法。
我说过,单模式串匹配算法,是在一个模式串和一个主串之间进行匹配,也就是说,在一个主串中查找一个模式串。多模式串匹配算法,就是在多个模式串和一个主串之间做匹配,也就是说,在一个主串中查找多个模式串。
确认放弃笔记?
放弃后所记笔记将不保留。
新功能上线,你的历史笔记已初始化为私密笔记,是否一键批量公开?
批量公开的笔记不会为你同步至部落
公开
同步至部落
取消
完成
0/2000
荧光笔
直线
曲线
笔记
复制
AI
  • 深入了解
  • 翻译
    • 英语
    • 中文简体
    • 中文繁体
    • 法语
    • 德语
    • 日语
    • 韩语
    • 俄语
    • 西班牙语
    • 阿拉伯语
  • 解释
  • 总结
仅可试看部分内容,如需阅读全部内容,请付费购买文章所属专栏
《数据结构与算法之美》
新⼈⾸单¥68
立即购买
登录 后留言

全部留言(116)

  • 最新
  • 精选
  • O_o
    做安卓开发的,前边全部都理解+可动手手写。跟到最近几章感到面试可能确实用不到这些了,平时工作也确实用不到了。感谢老师最近的授课,通俗易懂!

    作者回复: 👍 厉害。最近这几讲不讲的话 知识就有缺陷 你可以不用太费劲看懂 知道有这个东西就行

    4
    53
  • 闫飞
    可以讲讲自动机的概念吧,否则总有些感觉突兀

    作者回复: 么机会了。专栏已经更新完了。不过,你的问题我记下来了,我会更新到我的公众号里,你可以关注我的公众号:“小争哥”

    9
  • 懒猫
    老师,这里求最长可匹配后缀子串没理解,您举的例子:abc的最长可匹配后缀子串为bc,但是按照kmp的思想,abc的前缀子串为a、ab,后缀子串为c、bc,这里bc就不是最长可匹配后缀子串了呀,而且abc的最长可匹配后缀子串长度应该为0,不是吗

    作者回复: 你理解错了。这里说的最长可匹配后缀子串是:其他模式串可以匹配到abc的最长后缀子串。并不是abc自己的后缀子串匹配自己。

    2
    6
  • 森鱼
    字符串这几节真烧脑……

    作者回复: 那就看看https://mp.weixin.qq.com/s/t8z4KQMrTrR3NljtWJm2zg

    2
    5
  • wahaha
    “我这里给出一个不是很紧确的上界。” 不是“紧确”应该是“精确”

    编辑回复: 没问题的 就是紧确 意思和精确类似 你可以查一查

    3
  • 吴宇晨
    请教下老师,第三幅图,如果把d换成e,那pc的失败指针是不是要指向root了,但是和之前说的只会指向上一层节点不一样啊,希望老师解答下

    作者回复: 不是指向上一层 而是上层 上几层都有哦可能

    3
  • djfhchdh
    if (p == null) p = root; // 这里能否在p = root之后就直接continue??

    作者回复: 👍可以加,不加逻辑也没错

  • 自信来自成功的体验
    老师您好! 如果ac算法里面有好多需要跳转的 是每个都会跳转吗? 比如 she her hee hea 会怎么实现

    作者回复: ac自动机的跳转是通过fail指针来实现的

  • 一修💤
    在工作中遇到过这个问题 当时我是把敏感词表甚至一些正则的pattern组合在一起用或相连,编译成一个大的pattern对象,然后对字符串进行验证。效率似乎也不低哎 不知道和这个AC自动机的差距在哪里

    作者回复: 正则表达式是基于回溯搜索。效率这个东西要在大规模数据的情况下才能比较出来。

  • 樱桃子77
    想请教一点:即便没有AC自动机,单纯Trie,也可以多模式匹配吧?就像你文章开始说的那样,无论匹配成不成功,下一个主串里的词从新开始,而指向Trie的指针也重新指向root. 这样可以吗? 多谢。

    作者回复: 可以的

收起评论
显示
设置
留言
99+
收藏
沉浸
阅读
分享
手机端
快捷键
回顶部