这个算法可以怎么优化？

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

这是一个创建于 2672 天前的主题，其中的信息可能已经有所发展或是发生改变。

有一段文本要在几万个关键词里搜索然后替换成固定格式

我现在是遍历这几万个关键词依次在给定文本中查找和替换但是效率很低

求优化算法

算法

文本

替换

关键词

25 条回复 • 2017-07-31 14:12:21 +08:00

denonw

2017-07-31 09:42:00 +08:00 via iPhone

ac 自动机？

gamexg

2017-07-31 09:53:59 +08:00

今天刚收到邮件：
小时到分钟 - 一步步优化巨量关键词的匹配
http://www.cnblogs.com/zhenbianshu/p/7197349.html?f=tt&hmsr=toutiao.io&utm_medium=toutiao.io&utm_source=toutiao.io

hxndg

2017-07-31 09:54:46 +08:00

@denonw 多匹配是不是用的字典树？记得不是很轻，但是无论如何文本都得遍历一遍。

hxndg

2017-07-31 09:56:37 +08:00

@gamexg 忽然有点感叹，很多程序员并不知道学术界已经对很多问题总结出了优化算法啊，很多都是在闭门造车啊

xu33

2017-07-31 10:04:13 +08:00

@hxndg 我知道 trie 树和 KMP 算法但这个多模式匹配的 AC 自动机确实没听过

不过因为这是个比较常见的问题直觉上感觉应该有成熟算法上来问问果然有收获

hxndg

2017-07-31 10:11:31 +08:00

@xu33 我没有说你哈，我只是看到那个帖子下面一大堆人不太清楚这个感觉很迷。我记得 KMP 算法实际上就是 AC 自动机的一种吧，你如果想看字符串匹配方面的东西我建议你看看 algorithms on string,trees and sequence。可能有你想要的答案

zix

2017-07-31 10:42:45 +08:00

https://github.com/WojciechMula/pyahocorasick/

看你的文本长度。我用这个来做疾病的抽取，共有 2w 多个疾病术语，百字量级的文本上（包含 1 到 10 个疾病），耗时接近但不到 1ms。

hand515

2017-07-31 10:43:27 +08:00

前缀树匹配(Double Array Trie) 搜索下这个算法

gamexg

2017-07-31 11:05:25 +08:00

@hxndg #4 应该是知道的都不回复了吧？
以前看过多篇关键字匹配的文章(虽然细节都不记得了)，收到这个打开瞄了一眼就关了，别说回复了。

sampeng

2017-07-31 11:38:55 +08:00

感觉很像敏感词过滤= =！哈哈哈哈。
前缀匹配应该基本够使了

denonw

2017-07-31 11:41:26 +08:00

@hxndg 额。我理解的这种匹配基本都要遍历一遍文本吧。。。

sampeng

2017-07-31 11:45:55 +08:00

@denonw 几万个关键词。如果是暴力扫描，最坏情况是几万次遍历。所以得用算法来解决

hxndg

2017-07-31 11:50:55 +08:00

@gamexg 是的，但是那个帖子里很多人并不清楚这一点。还有人使用数据库等等做操作，但是底层也是基本的算法原理不太清楚，所以才有了那个尴尬的感叹

hustlike

2017-07-31 11:51:09 +08:00

你有代码吗？如果有代码更好给意见。如果是搜索词库的速度太慢，可以考虑用 hashmap。

hxndg

2017-07-31 11:52:34 +08:00

@sampeng
denow 的意思就是用算法来找的，但是无论怎么找都是要遍历文本的，这点避不开。

gamexg

2017-07-31 12:36:49 +08:00

@hxndg #13 手里有锤子看见什么都像钉子...
面向 google 编程可解，Google 大量关键字匹配，第一个就是关键字过虑实现的思路及 Aho – Corasick 高效字符串匹配算法应用。

Cooky

2017-07-31 12:44:30 +08:00 via Android

给文本分词，关键词做成字典，然后分出来的词在字典里找有没有，这种咧？

ic2y

2017-07-31 12:58:13 +08:00

将这“几万关键字 /词语” 生成自动机模型。自动机的入口用 hash 表进行组织。

然后对这段文本逐字进行扫描，用 hash 表发现入口，就进入自动机判定。否则，就继续线性扫描。

sampeng

2017-07-31 13:02:36 +08:00

@hxndg 我理解他的意思是忘了算那几万个关继字。。
当然，搜索最少一次是要遍历是跑不掉的

jesusRui

2017-07-31 13:21:14 +08:00

直接 linux sed ？？

ZSeptember

2017-07-31 13:27:52 +08:00

本来觉的楼上的分词可以，就看分词的性能了。然后仔细想想，虽然不是做 NLP 的，但是分词肯定也是要用到前缀树的吧。
所以，还是裸的前缀树吧。

troycheng

2017-07-31 13:31:13 +08:00

ac 自动机足够好用了，扫描文本的过程中就可以完成多模匹配了，替换也就是顺手加一行的事情

zjsxwc

2017-07-31 13:39:51 +08:00

单独开个机器作为敏感词过滤服务，使用 Trie 树，推荐这个 go 写的项目，https://github.com/huayuego/wordfilter

guyskk

2017-07-31 13:42:08 +08:00

把关键词构造成一个正则表达式，然后调用正则的 API 直接替换
```
>>> import re
>>> kws = ['几万', '关键词', '查找', '替换']
>>> r = '|'.join(kws)
>>> text = """
... 有一段文本要在几万个关键词里搜索然后替换成固定格式
...
... 我现在是遍历这几万个关键词依次在给定文本中查找和替换但是效率很低
...
... 求优化算法
... """
>>> re.sub(r, '[马赛克]', text)
'\n 有一段文本要在[马赛克]个[马赛克]里搜索然后[马赛克]成固定格式\n\n 我现在是遍历这[马赛克]个[马赛克] 依次在给定文本中[马赛克]和[马赛克] 但是效率很低\n\n 求优化算法\n'
>>>
```

hxndg

2017-07-31 14:12:21 +08:00

@gamexg
我倒没觉得“看什么都是钉子”有什么问题,如果旧有的工具能够满足性能需求，追求新方法未必是好的，毕竟不是系统瓶颈。。。
毕竟这么久了字符串算法还是就那么几个，手动斜眼