比较非匹配正则表达式的速度

Question

以下Python代码非常慢:

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

如果用更大的常数替换30,情况会变得更糟.

我怀疑由于连续性导致的解析歧义+是罪魁祸首,但我在regexp解析和匹配方面不是很专业.这是Python regexp引擎的错误,还是任何合理的实现都会这样做？

我不是Perl专家,但以下回复非常快

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

并且增加'a'的数量并不会显着改变执行速度.

Answer 1

我认为Perl足够聪明,可以将两个+s合并为一个,而Python则不然.现在让我们想象一下引擎的功能,如果没有优化的话.请记住,捕获通常很昂贵.另请注意,两者+都是贪婪的,因此引擎将尝试在一个回溯步骤中尽可能多地使用重复.每个项目符号点代表一个回溯步骤:

• 引擎使用尽可能多的[a],并消耗全部30 a秒.然后它不能再进一步,所以它留下第一次重复并捕获 30 a秒.现在下一个重复开始,它试图与另一个重复消耗,([a]+)但当然不起作用.然后c无法匹配b.
• 原路返回!抛弃a内心重复所消耗的最后一次.在此之后我们再次离开内部重复,因此引擎将捕获 29 a秒.然后另一个+开始,内部重复再次尝试(消耗30日a).然后我们再次离开内部重复,这也离开捕获组,因此第一次捕获被丢弃,引擎捕获最后一次a.c无法匹配b.
• 原路返回!扔掉另一个a里面.我们捕获 28 a秒.捕获组的第二(外重复)消耗的最后2个aS的被捕获.c无法匹配b.
• 原路返回!现在我们可以在第二个重复中回溯并扔掉两个中a的第二个.剩下的那个将被捕获.然后我们第三次进入捕获组并捕获最后一个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(仅仅通过前29 a秒然后通过前28 a秒回溯)只是为了发现,这c也是不匹配的a.

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

要解决这个问题.只需删除其中一个+.要么r'a+c'或者如果你不想要捕获量a的使用r'(a+)s'.

最后,回答你的问题.我不认为这是Python的正则表达式引擎中的错误,但只是(如果有的话)缺乏优化逻辑.这个问题通常是不可解决的,所以对于一个引擎来说,假设你必须自己处理灾难性的回溯并不是太不合理.如果Perl足够聪明,能够识别出足够简单的案例,那就更好了.

Answer 2

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

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