我定义了一个数组,长度目前是 200 ,未来应该会更长,数组内元素都是 re.compile 大概长这样 _list = [ (re.compile("正则表达式 1", re.IGNORECASE), (re.compile("正则表达式 2", re.IGNORECASE), ]
正则表达式中有若干 .* 的操作,但是能避免的都避免了 在取值的时候我用的 re.findall()
每来一个新的字符串,都要遍历一遍数组,再加上正则表达式,感觉速度很慢 想请教有没有什么更好的方法
1
Yuan2One 2023-07-06 16:55:10 +08:00 via Android
类似于前缀树一样写匹配树?但是好麻烦,要重新设计树结构,还得写匹配方法
|
2
billlee 2023-07-06 16:55:37 +08:00 via Android 2
去调 C++ 的 hyperscan.
|
3
mervinmemory 2023-07-06 17:15:45 +08:00 1
来自 gpt 的回复:
对于每次来的新字符串都要遍历整个正则表达式数组,这可能导致性能下降。如果你希望提高匹配速度,可以考虑使用更高效的数据结构,如字典( Dictionary )或者前缀树( Trie )。 下面是一种可能的优化方法: 1. 使用字典替代列表:将正则表达式和相应的操作存储在字典中,其中键为正则表达式字符串,值为对应的操作。这样可以通过正则表达式快速查找到对应的操作,而无需遍历整个列表。 2. 在字典中使用前缀树:将正则表达式作为前缀树的键,操作作为对应节点的值。前缀树可以提高匹配效率,特别是当正则表达式存在共同前缀时,可以减少不必要的匹配操作。 这是一个示例代码,展示了如何使用字典和前缀树进行优化: ```python import re from collections import defaultdict class TrieNode: def __init__(self): self.children = defaultdict(TrieNode) self.operations = [] def insert(root, regex, operation): node = root for char in regex: node = node.children[char] node.operations.append(operation) def find_operations(root, text): results = [] node = root for char in text: if char in node.children: node = node.children[char] results.extend(node.operations) elif '*' in node.children: node = node.children['*'] results.extend(node.operations) else: node = root return results # 构建前缀树 root = TrieNode() for regex, operation in _list: insert(root, regex.pattern, operation) # 搜索匹配操作 text = "待匹配的字符串" matching_operations = find_operations(root, text) # 对匹配操作进行处理 for operation in matching_operations: # 处理匹配操作 ``` 注意,这只是一种优化思路,并且需要根据你的具体需求进行适当的调整。如果正则表达式的数量非常庞大,可能需要使用更高级的算法和数据结构来进一步提高性能。 |
4
aloxaf 2023-07-06 17:31:12 +08:00
发一下你的正则长啥样?
200+ 个正则,这是在搞敏感词过滤? |
5
coderxy 2023-07-06 17:39:26 +08:00
首先,多个正则规则可以写到一起,用|分开。
|
6
coderxy 2023-07-06 17:41:29 +08:00 1
其次, 用正则做这种性能不好,如果是敏感词后期可能有十几万个, 要改用 DFA 去实现
|
7
skyrim61 2023-07-06 17:54:59 +08:00 1
来自 newbing 的回复
如果你需要在一个字符串中查找多个正则表达式模式,可以考虑以下几种方法来提高性能: 避免使用过于复杂的正则表达式。正则表达式中的某些特殊字符(如 .* 和 .+)可能会导致回溯,从而降低匹配速度。尽量使用简单的正则表达式,避免使用过多的特殊字符。 将多个正则表达式合并为一个。如果你需要在一个字符串中查找多个正则表达式模式,可以考虑将这些模式合并为一个正则表达式,然后一次性进行匹配。例如,你可以使用 | 字符将多个模式连接起来,形成一个新的正则表达式。 使用第三方库。Python 标准库中的 re 模块提供了基本的正则表达式功能,但是在某些情况下可能不够高效。你可以考虑使用第三方库(如 regex ),它们通常提供了更快的匹配速度和更多的功能。 希望这些建议能够帮助你提高正则表达式匹配的性能。如果你有其他问题,欢迎随时咨询我 |
8
iOCZ 2023-07-06 17:57:38 +08:00
没办法
|
9
lasuar 2023-07-06 18:57:31 +08:00
参考 #5
|
10
NoOneNoBody 2023-07-06 19:34:16 +08:00
这种非 IO 的最适合多进程并发了,不过 200 体现不出优势
|
11
volvo007 2023-07-06 21:51:41 +08:00
我想到的也是多线程,拆成 10 份每个 20 不是瞬间做完。这个案例也不用加锁
|
12
flyqie 2023-07-06 22:04:56 +08:00
解决方法就是并发,当然这个是用资源换时间。。
|
13
harrozze 2023-07-06 22:13:39 +08:00
@coderxy #6 以前做过你在 #5 说的方式,用 python 做一个论坛的过滤还是能行的。DFA 是一种方式,还有一种方式是分级处理。如果 OP 也是要做敏感词过滤的话。也就是说,对于非卡脖子的敏感词,用先发后审的方式分布式处理。
|
14
dqzcwxb 2023-07-06 22:16:16 +08:00
DFA
|
15
GeruzoniAnsasu 2023-07-06 22:16:24 +08:00 2
|
16
xiangyuecn 2023-07-06 22:40:47 +08:00 4
用 Trie 树,.*这种的简单正则表达式完全可以转换成多个关键词的匹配,复杂的也不怕 尽量提取出关键词 先高速判断这个正则是确定要参与匹配计算 过滤掉不参与的正则,那 200 个正则瞬间 从 1 秒 变成 1 毫秒💪
|
17
est 2023-07-06 22:57:29 +08:00
intel hyperscan
|
18
jiulang 2023-07-06 23:28:12 +08:00
如果是域名匹配,记录可以放到哈希表,输入的字符串做子域名切割(分词)来逐一匹配
|
19
0xWalker 2023-07-07 09:04:51 +08:00 1
hyperscan 正解,并行匹配还有指令优化
|
20
liangxin1998 2023-07-07 09:33:09 +08:00 1
以下是来自 GPT4 的回复:
在 Python 中,正则表达式确实可能是相当消耗资源的,特别是当你处理大量的数据或者复杂的正则表达式时。这是因为正则表达式的匹配机制是回溯的,也就是当一个匹配失败时,它会返回上一个状态并尝试其他可能的匹配方式。而使用 "." 和 "*" 这样的通配符可以增加正则表达式的复杂度,使得匹配过程变得更慢。 根据你的描述,你似乎在对每一个新的字符串遍历这个长度可能会增长到 200 以上的正则表达式列表。这种情况下,优化的方式可能依赖于你的具体应用场景。以下是一些可能的优化建议: 尽可能使正则表达式更简单:越复杂的正则表达式需要的计算资源就越多,尤其是当你有许多复杂的正则表达式需要匹配时。尽可能地避免使用 ".*" 和其他可能导致大量回溯的模式。 考虑预处理字符串:如果可能的话,考虑在正则表达式匹配之前对字符串进行预处理,以减小正则表达式的复杂性。这可能包括删除或替换不必要的字符,将字符串切分成较小的部分,或者将字符串转换为更容易处理的格式。 使用编译的正则表达式:Python 的 re 模块提供了一个 compile 函数,可以用来预编译正则表达式。这样做可以让你的代码在匹配正则表达式时运行得更快。 考虑使用其他字符串匹配算法:如果你的问题可以通过其他的字符串匹配算法来解决,那么可能会更有效率。例如,如果你只是在寻找特定的字串,那么使用 KMP ,Boyer-Moore 或 Rabin-Karp 这样的字符串匹配算法可能会更快。 使用多线程或多进程:如果你有大量的字符串需要处理,你可以考虑使用 Python 的 multiprocessing 或 threading 模块来并行处理这些字符串。 如果你的正则表达式是有序的,你可以在匹配时使用二分搜索:这样做的前提是你的正则表达式可以按照一定的规则排序,这样你可以在匹配时使用二分搜索而不是遍历整个列表。 这只是一些可能的优化方法,并不能保证在所有情况下都有效。具体的优化方法需要根据你的应用场景和需求来定。 |
21
yesterdaysun 2023-07-07 09:48:48 +08:00
我支持合并正则的方案, 在以前的类似的案例里面, 把一批 200 个左右的正则合成 1 个, 能够提高 30 倍左右的效率, 当然这个和具体的数据有关系, 但是说明这个方案是可行的.
原理我猜应该就是合并后的正则, 引擎编译时会自动优化形成类似 DFA 的数据结构或者算法, 合并正则可能也要一定的优化, 比如排序, 尽可能让有相同前缀的放在一组, 然后也要优化一些.*这样的写法, 就不同的方案都简单试试, 套入实际数据看看那种效率会变高 |
22
snylonue 2023-07-07 17:18:09 +08:00
rust 的 regex 有 RegexSet ,可以找找有没有 python 绑定
|
23
kaneg 2023-07-07 20:02:40 +08:00 via iPhone
还有一个思路,如果说这些正则匹配率差异比较大,可以给正则按照匹配的命中率动态排序,这样可以尽可能早地匹配到。
|