匹配长字符串时,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

如果我用更简单的方法尝试它,它工作正常.

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

我设法让它以一个非常短的字符串挂起.使用这个50个字符的字符串,大约5分钟后它就再也没有返回:

ddddddeddbedddbddddddddddddddddddddddddddddddddddd

使用这个39个字符的字符串返回大约需要15秒(并且不显示匹配项):

ddddddeddbedddbdddddddddddddddddddddddd

并使用此字符串立即返回:

ddddddeddbedddbdddddddddddddd

Answer 1

可能是你的表达式在Python RE引擎中触发了指数行为吗？

本文讨论了这个问题.如果你有时间,你可能想尝试在使用这些想法开发的RE引擎中运行表达式.

Answer 2

绝对指数行为。您d*的正则表达式有很多部分，以至于当到达一串长的d时，它会像疯了似的回溯，但无法更早地匹配某些东西。您需要重新考虑正则表达式，因此尝试路径的可能性更少。

我特别认为：

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

可能需要重新考虑，因为它们将强制重试备用比赛。另外，它们在匹配方面也重叠。例如，它们都匹配edb，但是如果其中一个失败并尝试回溯，则另一部分可能会具有相同的行为。

因此，简而言之，请尽量不要使用，|并尽可能确保模式不会重叠。