finditer在长字符串匹配时挂起

Question

我有一个比较复杂的正则表达式，我想用它去匹配一段很长的字符串（65,535个字符）。我想在这个字符串中找到多个匹配的地方，所以我使用了finditer这个方法。它确实能工作，但不知道为什么在找到前几个匹配后就卡住了。有人知道这可能是什么原因吗？以下是代码片段：

pattern = "(([ef]|([gh]d*(ad*[gh]d)*b))d*b([ef]d*b|d*)*c)"

matches = re.finditer(pattern, string)
for match in matches:
    print "(%d-%d): %s" % (match.start(), match.end(), match.group())

它能打印出前四个匹配，但之后就卡住了。当我按Ctrl-C强制停止时，它告诉我是在迭代器中被杀掉的：

Traceback (most recent call last):
  File "code.py", line 133, in <module>
    main(sys.argv[1:])
  File "code.py", line 106, in main
    for match in matches:
KeyboardInterrupt

如果我用一个简单的正则表达式，它就能正常工作。

我是在Windows XP的Cygwin上运行Python 2.5.4。

我发现即使用一个短得多的字符串，它也会卡住。这个50个字符的字符串，经过大约5分钟后也没有返回：

ddddddeddbedddbddddddddddddddddddddddddddddddddddd

而这个39个字符的字符串大约花了15秒才返回（并且没有显示任何匹配）：

ddddddeddbedddbdddddddddddddddddddddddd

而这个字符串则能立刻返回：

ddddddeddbedddbdddddddddddddd

Answer 1

感谢大家的回复，真的很有帮助。最后，令人惊讶的是，提升速度其实很简单。以下是原来的正则表达式：

(([ef]|([gh]d*(ad*[gh]d)*b))d*b([ef]d*b|d*)*c)

我注意到最后的 |d* 其实并不是我需要的，所以我做了如下修改：

(([ef]|([gh]d*(ad*[gh]d)*b))d*b([ef]d*bd*)*c)

现在它在处理65,536个字符的字符串时几乎是瞬间完成。我想我现在只需要确保这个正则表达式确实能匹配到我想要匹配的字符串就行了……

Answer 2

你的表达式可能会在Python的正则表达式引擎中引发指数级的行为吗？

这篇文章讨论了这个问题。如果你有时间，可以试着在一个基于这些想法开发的正则表达式引擎中运行你的表达式。

Answer 3

这绝对是指数级的表现。你的正则表达式里有太多的 d* 部分，当它处理一长串 d 的时候，如果之前的匹配失败，它就会疯狂地回溯。你需要重新考虑一下这个正则表达式，让它的可能路径少一些。

特别是我觉得：

([ef]d\*b|d\*)*</pre></code> and <code><pre>([ef]|([gh]d\*(ad\*[gh]d)\*b))d\*b

可能需要重新思考，因为它们会强制重新尝试其他匹配。而且它们在匹配的内容上也有重叠。例如，它们都会匹配 edb，但如果其中一个失败并尝试回溯，另一个部分可能也会有同样的表现。

所以简而言之，如果可以的话，尽量不要使用 |，并确保模式之间尽量不重叠。