python下的ahocorasick实现快速的关键字匹配

这两天在折腾下数据的分析及导出,爬虫抓取页面的时候,我们会坐做关键字的匹配,在数据库中标记这个url是否有我们需要的关键字。 这个时候你不能再用find()了,这太没有效率了,而且你会发现在同时处理几千个任务的时候,会出现cpu的瓶颈。 如果采用ahocorasick来实现,可以很有效的减轻cpu的消耗。 

AC自动机是多模式匹配的一个经典数据结构,原理是和KMP一样的构造fail指针,不过AC自动机是在Trie树上构造的,但原理是一样的。我这里就不多说ac的原理了,有兴趣的朋友可以自己找自己瞅瞅。 


python下已经有个现成的库了 ,大家直接 pip install ahocorasick .



如果不想用现成的ac的库,可以自己照着ac的原理写一份,只是过程很痛苦,我还是喜欢拿来主意 。毕竟实现算法的过程是个十分xxx的事情。 


有个网友已经把ac自动机和redis做了一些联合 。


对Golang感兴趣的朋友可以加群: 278517979 !!!
另外如果大家觉得文章对你有些作用! 如果想赏钱,可以用微信扫描下面的二维码, 感谢!
另外再次标注博客原地址  xiaorui.cc

1 Response

  1. orangleliu 2014年10月31日 / 下午5:32

    KMP 这些都开始研究啦,不错

发表评论

电子邮件地址不会被公开。 必填项已用*标注

您可以使用这些HTML标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code class="" title="" data-url=""> <del datetime=""> <em> <i> <q cite=""> <strike> <strong> <pre class="" title="" data-url=""> <span class="" title="" data-url="">