代码之家 › 专栏 › 技术社区 › Ben

与长字符串匹配时,finditer挂起

performance regex python

Ben · 技术社区 · 17 年前

我有一个比较复杂的正则表达式,我正试图与一个长字符串(65535个字符)进行匹配。我在查找字符串中多次出现的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

如果我用一个更简单的重新测试,它会很好地工作。

我在python 2.5.4上运行这个,在cygwin上运行windows xp。

我设法用一根很短的绳子把它挂起来。有了这个50个字符的字符串,它在大约5分钟后不会返回:

ddddddeddbedddbddddddddddddddddddddddddddddddddddd

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

ddddddeddbedddbdddddddddddddddddddddddd

使用这个字符串,它会立即返回:

ddddddeddbedddbdddddddddddddd

6 回复 | 直到 14 年前

John Montgomery 14 年前

绝对是指数行为。你有那么多 d* 部分到你的regexp,它会像疯了一样回溯到d的长字符串,但不能匹配早些时候的东西。您需要重新考虑regexp,这样它的尝试路径就更少了。

特别是我认为:

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

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

所以简而言之,不要使用 | 如果可以,并尽量确保模式在可能的情况下不会重叠。

unwind 17 年前

您的表达式是否会触发python re引擎中的指数行为?

This article 解决问题。如果你有时间的话,你可能想尝试在一个使用这些想法开发的重新引擎中运行你的表达式。

Tomalak 17 年前

我认为你经历了所谓的“灾难性回溯”。

您的regex有许多可选/可选部分,所有部分仍然尝试匹配,因此在本地失败时,前面的子表达式会将字符返回给下面的表达式。这会导致regex中出现后退和第四种行为,执行时间呈指数级增长。

Python(2.7 +)?,我不确定)支持原子分组和所有格量词,您可以检查regex,以确定应该匹配或整体失败的部分。不必要的回溯可以用它来控制。

Jeff Atwood 17 年前

灾难性的回溯!

正则表达式可能非常昂贵。某些(意外的和预期的)字符串可能会导致正则表达式显示指数行为。我们为此做了几次修补。正则表达式非常方便,但开发人员确实需要了解它们的工作方式;我们已经被它们咬了。

示例和调试器:

http://www.codinghorror.com/blog/archives/000488.html

Ben 14 年前

感谢所有的回答,这是非常有帮助的。最后,令人惊讶的是,它很容易加速。这是原始的regex:

(([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)

现在它几乎在65536字符串上瞬间工作。我想现在我只需要确保regex真正匹配我需要它匹配的字符串…

Community Mohan Dere 9 年前

你已经给了自己答案:正则表达式是复杂和模糊的。

您应该尝试找到一个更容易处理的不那么复杂、更独特的表达式。或者告诉我们你想完成什么,我们可以帮助你找到一个。

编辑 ___,如果你只想允许 d 正如你在评论中所说的 John Montgomeryâs answer ,您应该在测试模式之前移除它们:

import re

string = "ddddddeddbedddbddddddddddddddddddddddddddddddddddd"
pattern = "(([ef]|([gh](a[gh])*b))b([ef]b)*c)"
matches = re.finditer(pattern, re.sub("d+", "", string))
for match in matches:
    print "(%d-%d): %s" % (match.start(), match.end(), match.group())