为什么会用AC自动机? 如果你想知道一篇文章有没有你要过滤的敏感词,怎么办? 不可能用正则一个个的匹配吧?  敏感词超过300个之后,用Trie来构建模式树 (字典树)的速度优势相当的明显… …

Hello Boys , 文章的原文转自 http://xiaorui.cc   http://xiaorui.cc/?p=1649


特别说下,trie图也是一种DFA,可以由trie树为基础构造出来,对于插入的每个模式串,其插入过程中使用的最后一个节点都作为DFA的一个终止节点。

如果要求一个母串包含哪些模式串,以用母串作为DFA的输入,在DFA 上行走,走到终止节点,就意味着匹配了相应的模式串。

ps: AC自动机是Trie的一种实现,也就是说AC自动机是构造Trie图的DFA的一种方法。还有别的构造DFA的方法… 

不扯淡了,我们后端都是python写的,python的ahocorasick模块跟我们的业务不太匹配,问题是这样的 !    如果你的服务是用来做敏感词匹配,也就是说所有文章里面只要含有一个关键词,那就说明匹配了。  但是我们的业务是文章中的所有能匹配到的关键词都一一的抽取出来。   我想有些朋友可能还不太明白,那么我举个例子, 如果我的关键词里面有宝马和马,那么用python的ahocorasick库只会得到宝马,而不会得到马。  问题是处在马这个字节是在宝马的链条里面的。  如何避开这个问题,我们也懒得自己重写了,已经有人给出了解决的模块。  已经测试完成,并上线使用了。 

安装简单,直接pip install esmre

再来一个完整的例子.  后续有时间我会把ac自动机的服务集成到rpc服务里面,然后用docker打包。


测了几天,性能还是可以的,500KB的文章,6000多个关键词,消耗的时间在0.002左右,相比ahocorasick一点都不差的。  观察了下,esmre是没有发现内存异常泄露等问题。



对Python及运维开发感兴趣的朋友可以加QQ群 : 478476595 !!!
{ 2000人qq大群内有各厂大牛,常组织线上分享及沙龙,对高性能及分布式场景感兴趣同学欢迎加入该QQ群 }

另外如果大家觉得文章对你有些作用!   帮忙点击广告. 一来能刺激我写博客的欲望,二来好维护云主机的费用.
如果想赏钱,可以用微信扫描下面的二维码. 另外再次标注博客原地址  xiaorui.cc  ……   感谢!
暂无相关产品

发表评论