V2EX = way to explore
V2EX 是一个关于分享和探索的地方
Sign Up Now
For Existing Member Sign In
• 请不要在回答技术问题时复制粘贴 AI 生成的内容
This topic created in 3193 days ago, the information mentioned may be changed or developed.
有一段文本 要在几万个关键词里搜索 然后替换成固定格式
我现在是遍历这几万个关键词 依次在给定文本中查找和替换 但是效率很低
求优化算法
 |
1
denonw Jul 31, 2017 via iPhone
ac 自动机？
|
 |
2
gamexg Jul 31, 2017
今天刚收到邮件：
小时到分钟 - 一步步优化巨量关键词的匹配 http://www.cnblogs.com/zhenbianshu/p/7197349.html?f=tt&hmsr=toutiao.io&utm_medium=toutiao.io&utm_source=toutiao.io |
2 |
5
xu33 OP |
 |
6
hxndg Jul 31, 2017
@xu33 我没有说你哈，我只是看到那个帖子下面一大堆人不太清楚这个感觉很迷。我记得 KMP 算法实际上就是 AC 自动机的一种吧，你如果想看字符串匹配方面的东西我建议你看看 algorithms on string,trees and sequence。可能有你想要的答案
|
 |
7
zix Jul 31, 2017
https://github.com/WojciechMula/pyahocorasick/
看你的文本长度。我用这个来做疾病的抽取，共有 2w 多个疾病术语，百字量级的文本上（包含 1 到 10 个疾病），耗时接近但不到 1ms。 |
 |
8
Finest Jul 31, 2017
前缀树匹配(Double Array Trie) 搜索下这个算法
|
 |
10
sampeng Jul 31, 2017
感觉很像敏感词过滤= =！哈哈哈哈。
前缀匹配应该基本够使了 |
 |
14
hustlike Jul 31, 2017
你有代码吗？如果有代码更好给意见。如果是搜索词库的速度太慢，可以考虑用 hashmap。
|
|
16
gamexg Jul 31, 2017
@hxndg #13 手里有锤子看见什么都像钉子...
面向 google 编程可解，Google 大量 关键字 匹配 ，第一个就是 关键字过虑实现的思路及 Aho – Corasick 高效字符串匹配算法应用 。 |
 |
17
Cooky Jul 31, 2017 via Android
给文本分词，关键词做成字典，然后分出来的词在字典里找有没有，这种咧？
|
 |
18
ic2y Jul 31, 2017
将这“几万关键字 /词语” 生成自动机模型。 自动机的入口用 hash 表进行组织。
然后对 这段文本逐字进行扫描，用 hash 表发现入口，就进入自动机判定。否则，就继续线性扫描。 |
 |
20
jesusRui Jul 31, 2017
直接 linux sed ？？
|
 |
21
looplj Jul 31, 2017
本来觉的楼上的分词可以，就看分词的性能了。然后仔细想想，虽然不是做 NLP 的，但是分词肯定也是要用到前缀树的吧。
所以，还是裸的前缀树吧。 |
 |
22
troycheng Jul 31, 2017
ac 自动机足够好用了，扫描文本的过程中就可以完成多模匹配了，替换也就是顺手加一行的事情
|
 |
23
zjsxwc Jul 31, 2017
单独开个机器作为敏感词过滤服务，使用 Trie 树，推荐这个 go 写的项目，https://github.com/huayuego/wordfilter
|
 |
24
guyskk Jul 31, 2017
把关键词构造成一个正则表达式，然后调用正则的 API 直接替换
``` >>> import re >>> kws = ['几万', '关键词', '查找', '替换'] >>> r = '|'.join(kws) >>> text = """ ... 有一段文本 要在几万个关键词里搜索 然后替换成固定格式 ... ... 我现在是遍历这几万个关键词 依次在给定文本中查找和替换 但是效率很低 ... ... 求优化算法 ... """ >>> re.sub(r, '[马赛克]', text) '\n 有一段文本 要在[马赛克]个[马赛克]里搜索 然后[马赛克]成固定格式\n\n 我现在是遍历这[马赛克]个[马赛克] 依次在给定文本中[马赛克]和[马赛克] 但是效率很低\n\n 求优化算法\n' >>> ``` |
Select Language