python - 永远不会运行完的正则表达式

Question

我写了一个小的、朴素的正则表达式，用于查找括号内的文本:


re.search(r'\((.|\s)*\)', 名称)


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

x (y)                                            z

我已经对此进行了试验，并确定“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

但除空格以外的字符也不具有相同的效果:

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

注意:我并不是在寻找更好的正则表达式或其他解决方案来解决这个问题。我们不再使用它。

Answer 1

灾难性回溯

正如 CaffGeek 的回答正确暗示的那样，问题是由于 catastrophic backtracking 的一种形式引起的.这两个选项都匹配一个空格(或制表符)，并且贪婪地无限次应用。此外，点与右括号匹配，因此一旦左括号匹配，此表达式始终匹配到字符串的末尾，然后它必须煞费苦心地回溯以找到右括号。并且在此回溯过程中，在每个位置尝试另一个替代方案(对于空格或制表符也是成功的)。因此，在引擎可以回溯一个位置之前，必须尝试每一种可能的匹配组合序列。右括号后有很多空格，加起来很快。可以通过简单地使星号量词惰性化(即 r'\((.|\s)*?\)')来解决存在匹配闭括号的情况的具体问题，但是对于在主题字符串中有一个没有匹配的闭括号的开括号的不匹配情况，失控的正则表达式问题仍然存在。

原来的正则表达式真的，真的很糟糕! (并且当有超过一对时也不能正确匹配右括号)。

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

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

所有正则表达式作者都应该阅读 MRE3!

Jeffrey Friedl 的 正则表达式作者必读 中对此进行了非常详细的解释(带有详尽的示例和推荐的最佳实践):Mastering Regular Expressions (3rd Edition) .我可以诚实地说，这是我读过的最有用的书。正则表达式是一种非常强大的工具，但就像一把上膛的武器，必须非常小心和精确地使用(否则你会搬起石头砸自己的脚!)