这个算法可以怎么优化?

2017-07-31 09:33:54 +08:00
 xu33

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

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

求优化算法

4516 次点击
所在节点    程序员
25 条回复
denonw
2017-07-31 09:42:00 +08:00
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
给文本分词,关键词做成字典,然后分出来的词在字典里找有没有,这种咧?
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 ??

这是一个专为移动设备优化的页面(即为了让你能够在 Google 搜索结果里秒开这个页面),如果你希望参与 V2EX 社区的讨论,你可以继续到 V2EX 上打开本讨论主题的完整版本。

https://www.v2ex.com/t/379140

V2EX 是创意工作者们的社区,是一个分享自己正在做的有趣事物、交流想法,可以遇见新朋友甚至新机会的地方。

V2EX is a community of developers, designers and creative people.

© 2021 V2EX