9

The following Python code is incredibly slow:

import re
re.match( '([a]+)+c', 'a' * 30 + 'b' )

and it gets worse if you replace 30 with a larger constant.

I suspect that the parsing ambiguity due to the consecutive + is the culprit, but I'm not very expert in regexp parsing and matching. Is this a bug of the Python regexp engine, or any reasonable implementation will do the same?

I'm not a Perl expert, but the following returns quite fast

perl -e '$s="aaaaaaaaaaaaaaaaaaaaaaaaaaaaaab"; print "ok\n" if $s =~ m/([a]+)+c/;'

and increasing the number of 'a' does not alter substantially the execution speed.

4

2 回答 2

13

我假设 Perl 足够聪明，可以将两个+s 合并为一个，而 Python 不是。现在让我们想象一下引擎会做什么，如果它没有被优化掉的话。请记住，捕获通常很昂贵。另请注意，两个+s 都是贪婪的，因此引擎将尝试在一个回溯步骤中使用尽可能多的重复。每个要点代表一个回溯步骤：

  • 引擎尽可能多地使用[a]，并消耗所有三十个a。然后它不能再往前走了，所以它离开了第一次重复并捕获了30a秒。现在下一次重复开始了，它试图与另一个重复消耗更多，([a]+)但这当然不起作用。然后c失败匹配b。
  • 回溯！扔掉a被内在重复消耗的最后一个。在此之后，我们再次离开内部重复，因此引擎将捕获29a秒。然后另一个+开始，再次尝试内部重复（消耗第 30 次a）。然后我们再次离开内部重复，这也离开了捕获组，所以第一个捕获被丢弃，引擎捕获最后一个a。c不匹配b。
  • 回溯！扔掉另一个a里面。我们捕获28a秒。捕获组的第二个（外部重复）消耗了被捕获a的最后 2秒。不匹配。cb
  • 回溯！现在我们可以在第二个其他重复中回溯并丢弃两个as 中的第二个。剩下的那一个会被俘虏。然后我们第三次进入捕获组，捕获最后一个a。c不匹配b。
  • 回溯！a在第一次重复中降至 27秒。

这是一个简单的可视化。每一行代表一个回溯步骤，每组括号表示一次内部重复的消耗。大括号表示为该回溯步骤新捕获的那些，而在该特定回溯步骤中不重新访问普通括号。我省略了b/c因为它永远不会匹配：

{aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa}
{aaaaaaaaaaaaaaaaaaaaaaaaaaaaa}{a}
{aaaaaaaaaaaaaaaaaaaaaaaaaaaa}{aa}
(aaaaaaaaaaaaaaaaaaaaaaaaaaaa){a}{a}
{aaaaaaaaaaaaaaaaaaaaaaaaaaa}{aaa}
(aaaaaaaaaaaaaaaaaaaaaaaaaaa){aa}{a}
(aaaaaaaaaaaaaaaaaaaaaaaaaaa){a}{aa}
(aaaaaaaaaaaaaaaaaaaaaaaaaaa)(a){a}{a}
{aaaaaaaaaaaaaaaaaaaaaaaaaa}{aaaa}
(aaaaaaaaaaaaaaaaaaaaaaaaaa){aaa}{a}
(aaaaaaaaaaaaaaaaaaaaaaaaaa){aa}{aa}
(aaaaaaaaaaaaaaaaaaaaaaaaaa)(aa){a}{a}
(aaaaaaaaaaaaaaaaaaaaaaaaaa){a}{aaa}
(aaaaaaaaaaaaaaaaaaaaaaaaaa)(a){aa}{a}
(aaaaaaaaaaaaaaaaaaaaaaaaaa)(a){a}{aa}
(aaaaaaaaaaaaaaaaaaaaaaaaaa)(a)(a){a}{a}

和。所以。上。

请注意，最后引擎还将尝试所有组合的子集a（仅回溯到前 29a秒，然后通过前 28a秒）只是为了发现，这c也不匹配a。

正则表达式引擎内部的解释基于散布在regular-expressions.info周围的信息。

为了解决这个问题。只需删除其中一个+s。或者r'a+c'，如果您确实想要捕获as use的数量r'(a+)s'。

最后，回答你的问题。我不会认为这是 Python 正则表达式引擎中的错误，而只是（如果有的话）缺乏优化逻辑。这个问题通常不是可以解决的，所以引擎假设你必须自己处理灾难性的回溯并不是太不合理。如果 Perl 足够聪明，能够识别出足够简单的情况，那就更好了。

于 2012-11-01T14:42:12.293 回答
4

通过删除嵌套量词重写您的正则表达式以消除“灾难性回溯”（请参阅​​此问题）：

re.match( '([a]+)+c', 'a' * 30 + 'b' )
# becomes
re.match( 'a+c', 'a' * 30 + 'b' )
于 2012-11-01T14:41:42.517 回答