python使用esmre代替ahocorasick实现ac自动机[多模匹配]
Toggle navigationHomesaltstackansiblezabbixdockerpythonGolangweb开发运维开发运维文艺python使用esmre代替ahocorasick实现ac自动机[多模匹配]6-13pythonrfy
·
6-13 368 views
为什么会用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
|
1
2
3
4
5
6
7
8
9
10
|
import esm
index = esm . Index ( )
index . enter ( "宝马" )
index . enter ( "马" )
index . enter ( "奔驰" )
index . enter ( "保时捷" )
index . fix ( )
index . query ( "哎呀，今天在楼下看到了宝马，我老家倒是有养马的，以前的邻居有个奔驰，不对是保时捷，大爷的，都是马" )
|
再来一个完整的例子. 后续有时间我会把ac自动机的服务集成到rpc服务里面,然后用docker打包。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
|
#coding:utf-8
import esm
index = esm . Index ( )
with open ( 'keyword.config' , 'r' ) as f :
for i in f . readlines ( ) :
index . enter ( i . strip ( ) )
index . fix ( )
str = """
head&shoulders海飞丝Hershey‘s
Loreal欧莱雅LUX2
力士
L’OREALMagic2
美即
MysteryCity
谜城
NO.1BABY2
RESIN
SANXIAO
SHISEIDO FINE TOILETRY2
SKII美之匙
Tao yu tang2
淘雨堂
whoo倍加洁
卡尔林奈
娇韻诗
德国帮宝适
Perfect puff2
See Young2
落健
高夫
"""
data = index . query ( str )
print data
|
测了几天，性能还是可以的，500KB的文章，6000多个关键词，消耗的时间在0.002左右，相比ahocorasick一点都不差的。 观察了下，esmre是没有发现内存异常泄露等问题。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
|
[ 2015 - 06 - 12 23 : 34 : 01 , 043 ] INFO extractor "Get keywords takes 0.0003 seconds"
[ 2015 - 06 - 12 23 : 34 : 01 , 069 ] INFO extractor "Get keywords takes 0.0002 seconds"
[ 2015 - 06 - 12 23 : 34 : 01 , 178 ] INFO extractor "Get keywords takes 0.0002 seconds"
[ 2015 - 06 - 12 23 : 34 : 02 , 372 ] INFO extractor "Get keywords takes 0.0002 seconds"
[ 2015 - 06 - 12 23 : 34 : 02 , 386 ] INFO extractor "Get keywords takes 0.0012 seconds"
[ 2015 - 06 - 12 23 : 34 : 02 , 631 ] INFO extractor "Get keywords takes 0.0002 seconds"
[ 2015 - 06 - 12 23 : 34 : 03 , 656 ] INFO extractor "Get keywords takes 0.0021 seconds"
[ 2015 - 06 - 12 23 : 34 : 03 , 744 ] INFO extractor "Get keywords takes 0.0001 seconds"
[ 2015 - 06 - 12 23 : 34 : 03 , 785 ] INFO extractor "Get keywords takes 0.0001 seconds"
[ 2015 - 06 - 12 23 : 34 : 03 , 910 ] INFO extractor "Get keywords takes 0.0002 seconds"
[ 2015 - 06 - 12 23 : 34 : 04 , 031 ] INFO extractor "Get keywords takes 0.0002 seconds"
[ 2015 - 06 - 12 23 : 34 : 05 , 004 ] INFO extractor "Get keywords takes 0.0035 seconds"
[ 2015 - 06 - 12 23 : 34 : 05 , 579 ] INFO extractor "Get keywords takes 0.0055 seconds"
[ 2015 - 06 - 12 23 : 34 : 05 , 602 ] INFO extractor "Get keywords takes 0.0005 seconds"
[ 2015 - 06 - 12 23 : 34 : 05 , 662 ] INFO extractor "Get keywords takes 0.0010 seconds"
[ 2015 - 06 - 12 23 : 34 : 06 , 125 ] INFO extractor "Get keywords takes 0.0002 seconds"
[ 2015 - 06 - 12 23 : 34 : 06 , 299 ] INFO extractor "Get keywords takes 0.0002 seconds"
[ 2015 - 06 - 12 23 : 34 : 06 , 404 ] INFO extractor "Get keywords takes 0.0003 seconds"
[ 2015 - 06 - 12 23 : 34 : 07 , 396 ] INFO extractor "Get keywords takes 0.0002 seconds"
[ 2015 - 06 - 12 23 : 34 : 07 , 595 ] INFO extractor "Get keywords takes 0.0004 seconds"
[ 2015 - 06 - 12 23 : 34 : 08 , 725 ] INFO extractor "Get keywords takes 0.0015 seconds"
[ 2015 - 06 - 12 23 : 34 : 09 , 504 ] INFO extractor "Get keywords takes 0.0004 seconds"
[ 2015 - 06 - 12 23 : 34 : 09 , 515 ] INFO extractor "Get keywords takes 0.0005 seconds"
[ 2015 - 06 - 12 23 : 34 : 10 , 650 ] INFO extractor "Get keywords takes 0.0002 seconds"
[ 2015 - 06 - 12 23 : 34 : 11 , 206 ] INFO extractor "Get keywords takes 0.0003 seconds"
[ 2015 - 06 - 12 23 : 34 : 12 , 298 ] INFO extractor "Get keywords takes 0.0002 seconds"
[ 2015 - 06 - 12 23 : 34 : 12 , 319 ] INFO extractor "Get keywords takes 0.0001 seconds"
[ 2015 - 06 - 12 23 : 34 : 13 , 547 ] INFO extractor "Get keywords takes 0.0006 seconds"
[ 2015 - 06 - 12 23 : 34 : 13 , 853 ] INFO extractor "Get keywords takes 0.0005 seconds"
|
相关的文章
python下的ahocorasick实现快速的关键字匹配
分享python实现的lfu缓存模块-pylfu
浅谈twisted应用中异步回调的方式及线程的应用- python调用zookeeper管理thrift集群可用性队列
利用google authenticator构建平台的otp动态口令
解决hbase跑mapreduce时遇到内存及超时问题
线上测试docker在cpu密集运算的场景下性能的表现
python实现最少使用算法lru包括dict和list队列- nginx1.9新模块ngx_stream_core_module实现stream tcp负载均衡
- 针对redis的HyperLogLog做基数统计性能测试
用gevent开发非阻塞的etcd python客户端模块
聊聊python的轻量级orm peewee及对比SQLAlchemy
别倒贴，要不整死你
转载时必须以链接形式注明原始出处及本声明。
公告
我的另一个博客，偏向 运维方面的 ~ ops.xiaorui.cc
有事可以发邮件，rfyiamcool@163.com
我个人的github地址是， github.com/rfyiamcool
我给pypi提交过的项目，[话说曾经被删过一些] pypi地址
有事可以发邮件，rfyiamcool@163.com
我个人的github地址是， github.com/rfyiamcool
我给pypi提交过的项目，[话说曾经被删过一些] pypi地址
最近访客
标签
ansible ansible api django tornado docker docker api elasticsearch elk etcd gevent golang gunicorn happybase Influxdb InfluxDB 性能 kibana kibana4 logstash python python celery python docker python elasticsearch python etcd python gevent python gunicorn python happybase python hbase python influxdb python mongodb python multiprocessing python redis python rq python socket python threadpool python thrift python zabbix python 任务队列 python 校验数据 python 缓存 redis redis cluster saltstack saltstack api zabbix zabbix二次开发 zabbix开发
最热文章
- 大数据公司招聘高级python程序员10
- 使用python实现高性能代理服务器 [tornado proxy]9
- TB级mysql数据之xtrabackup压缩备份迁移方案9
- 对于nginx线程池thread pool提高性能的疑惑6
- 高薪招聘Devops web 运维开发工程师6
- python版shadowsocks流量及用户管理开发5
- docker无法用exec进入容器的问题[cannot allocate4
- 使用python的mysqldb做like模糊查询时遇到的问题4
随机文章
-
使用iptables管理docker容器...使用iptables管理doc...0
-
关于数据写入的etcd http api...关于数据写入的etcd htt...1
-
docker中使用logrotate对l...docker中使用logrot...0
-
Flask使用token来防御csrf跨...Flask使用token来防御...2
-
使用python PIL库实现复杂的图片...使用python PIL库实现...1
-
nginx tcp实现hbase thr...nginx tcp实现hbas...2
-
实时监控之ajax动态填充highcha...实时监控之ajax动态填充hi...0
-
通过运维工具ansible api来做平...通过运维工具ansible a...0
云原生社区为您提供最前沿的新闻资讯和知识内容
更多推荐
1
0- 0
已为社区贡献3条内容
所有评论(0)