从未完成运行的正则表达式

Question

从未完成运行的正则表达式

我写了一个小的,天真的正则表达式,应该在括号内找到文本:

re.search(r'$(.|\s)*$', name)

我知道这不是出于某些原因这样做的最好方法,但它工作得很好.我正在寻找的只是一个解释,为什么对于某些字符串,这个表达式开始呈指数级增长然后永远不会完成.昨晚,在运行此代码数月之后,我们的一台服务器突然卡住了匹配类似于以下内容的字符串:

x (y)                                            z

Run Code Online (Sandbox Code Playgroud)

我已经对它进行了实验,并确定在"y"和"z"之间的每个空间所花费的时间都会翻倍:

In [62]: %timeit re.search(r'\((.|\s)*\)', 'x (y)' + (22 * ' ') + 'z')
1 loops, best of 3: 1.23 s per loop

In [63]: %timeit re.search(r'\((.|\s)*\)', 'x (y)' + (23 * ' ') + 'z')
1 loops, best of 3: 2.46 s per loop

In [64]: %timeit re.search(r'\((.|\s)*\)', 'x (y)' + (24 * ' ') + 'z')
1 loops, best of 3: 4.91 s per loop

Run Code Online (Sandbox Code Playgroud)

但是除了空格之外的字符也没有相同的效果:

In [65]: %timeit re.search(r'\((.|\s)*\)', 'x (y)' + (24 * 'a') + 'z')
100000 loops, best of 3: 5.23 us per loop

Run Code Online (Sandbox Code Playgroud)

注意:我不是在寻找更好的正则表达式或此问题的其他解决方案.我们不再使用它了.

Answer 1

rid*_*ner 6

灾难性的回溯

正如CaffGeek的答案正确暗示的那样,问题是由于某种形式的灾难性回溯.这两个选项都匹配一个空格(或制表符),这是无限次地贪婪地应用.此外,点匹配右括号,因此一旦打开paren匹配,此表达式始终匹配字符串的最末端,然后必须艰苦地回溯以找到结束括号.在此回溯过程中,在每个位置尝试另一种替代方案(对于空格或制表符也是成功的).因此,必须在引擎可以回溯一个位置之前尝试每个可能的匹配组合序列.在收盘后有很多空间,这很快就会增加.有一个匹配的紧密paren的情况下的具体问题可以通过简单地使星形量化器懒惰(即r'$(.|\s)*?$')来解决,但是对于不匹配的情况仍然存在失控的正则表达式问题,其中存在没有匹配关闭的开放paren主题字符串中的paren.

原来的正则表达式非常非常糟糕!(如果有多对,也不能正确匹配关闭的parens).

正确的表达式匹配最里面的括号(匹配和非匹配情况都非常快),当然是:

re_innermostparens = re.compile(r"""
    \(        # Literal open paren.
    [^()]*    # Zero or more non-parens.
    \)        # Literal close paren.
    """, re.VERBOSE)

Run Code Online (Sandbox Code Playgroud)