Python re 无限执行

Question

我正在尝试运行这段代码：

import re
pattern = r"(\w+)\*([\w\s]+)*/$"
re_compiled = re.compile(pattern)
results = re_compiled.search('COPRO*HORIZON 2000                 HOR')
print(results.groups())

但是Python没有任何反应。这个过程占用了100%的CPU，根本停不下来。我在Python 2.7.1和Python 3.2上都试过，结果是一样的。

Answer 1

有趣的是，Perl运行这个的速度非常快。

-> perl -e 'print "Match\n" if "COPRO*HORIZON 2000                 HOR" =~ m|(\w+)\*([\w\s]+)*/$|'
-> perl -e 'print "Match\n" if "COPRO*HORIZON 2000                 HOR/" =~ m|(\w+)\*([\w\s]+)*/$|'
Match

Answer 2

可以试试re2，或者其他基于自动机理论的正则表达式引擎。现在Python的re模块使用的是一种简单且速度较慢的回溯引擎（不过将来可能会有所改变）。不过，基于自动机的引擎有一些限制，比如不允许使用回溯引用。你可以参考这个re2语法页面，看看它是否能满足你的需求。

Answer 3

你的正则表达式出现了灾难性回溯的问题，因为你使用了嵌套的量词（([...]+)*）。由于你的正则表达式要求字符串以/结尾（而你的例子没有满足这个条件），所以正则引擎会尝试字符串的所有排列组合，希望能找到匹配的结果。这就是它卡住的原因。

为了说明这个问题，我们假设输入的字符串是"A*BCD"，看看会发生什么：

1. (\w+) 匹配到 A。很好。
2. * 匹配到 *。太棒了。
3. [\w\s]+ 匹配到 BCD。好的。
4. / 匹配失败（没有剩下的字符可以匹配）。好吧，我们退回一个字符。
5. / 匹配失败 D。嗯，让我们再退回一些。
6. [\w\s]+ 匹配到 BC，重复的 [\w\s]+ 匹配到 D。
7. / 匹配失败。退回。
8. / 匹配失败 D。再退回一些。
9. [\w\s]+ 匹配到 B，重复的 [\w\s]+ 匹配到 CD。
10. / 匹配失败。再退回。
11. / 匹配失败 D。再退回。
12. 那[\w\s]+ 匹配到 B，重复的 [\w\s]+ 匹配到 C，再重复的 [\w\s]+ 匹配到 D呢？不行？那我们试试别的。
13. [\w\s]+ 匹配到 BC。我们在这里停下来看看会发生什么。
14. 真糟糕，/ 还是匹配不到 D。
15. [\w\s]+ 匹配到 B。
16. 还是没运气。/ 匹配不到 C。
17. 嘿，整个组是可选的 (...)*。
18. 不行，/ 还是匹配不到 B。
19. 好吧，我放弃了。

现在这只是一个由三个字母组成的字符串。而你的字符串大约有30个字母，尝试所有排列组合会让你的电脑忙到天荒地老。

我想你想要做的是获取*前后的字符串，在这种情况下，可以使用

pattern = r"(\w+)\*([\w\s]+)$"