python - 匹配长字符串时 finditer 挂起

Question

我有一个有点复杂的正则表达式，我试图将其与一个长字符串(65,535 个字符)进行匹配。我正在寻找字符串中多次出现的 re，因此我使用了 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

如果我用更简单的 re 尝试它，它工作正常。

我在 Windows XP 上的 Cygwin 上运行的 python 2.5.4 上运行它。

我设法让它卡在一个非常短的字符串上。对于这个 50 个字符的字符串，它在大约 5 分钟后再也没有返回:

ddddddeddbedddbddddddddddddddddddddddddddddddddddd

对于这个 39 个字符的字符串，大约需要 15 秒才能返回(并且不显示任何匹配项):

ddddddeddbedddbdddddddddddddddddddddddd

对于这个字符串，它会立即返回:

ddddddeddbedddbdddddddddddddd

Answer 1

绝对是指数行为。您的正则表达式中有太多 d* 部分，以至于当它到达一长串 d 时它会疯狂地回溯，但无法匹配更早的内容。您需要重新考虑正则表达式，以减少可尝试的路径。

我特别认为:

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

可能需要重新考虑，因为他们会强制重试替代匹配。另外，它们在匹配方面也有重叠。例如，它们都会匹配 edb，但如果一个失败并尝试回溯，另一部分可能会有相同的行为。

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