8

我写了一个小而朴素的正则表达式，它应该在括号内找到文本：

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

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

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

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

4

2 回答 2

6

灾难性的回溯

正如 CaffGeek 的回答正确暗示的那样，问题是由于一种形式的灾难性回溯. 这两种选择都匹配空格（或制表符），并且贪婪地无限次应用。此外，点匹配右括号，所以一旦匹配左括号，这个表达式总是匹配到字符串的最后，然后它必须煞费苦心地回溯以找到右括号。在这个回溯过程中，在每个位置都尝试了另一种选择（对于空格或制表符也是成功的）。因此，在引擎可以回溯一个位置之前，必须尝试所有可能的匹配组合序列。在结束括号后有很多空格，这很快就会增加。可以通过简单地使星量词惰性（即r'\((.|\s)*?\)')，但是对于不匹配的情况，仍然存在失控的正则表达式问题，即在主题字符串中有一个开括号而没有匹配的闭括号。

原来的正则表达式真的非常非常糟糕！（当有一对以上时，也不能正确匹配右括号）。

匹配最内层括号的正确表达式（对于匹配和不匹配的情况都非常快），当然是：

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

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

Jeffrey Friedl 的正则表达式作者必读：掌握正则表达式（第 3 版）中详细解释了这一切（带有详尽的示例和推荐的最佳实践） 。老实说，这是我读过的最有用的书。正则表达式是一个非常强大的工具，但就像装载的武器一样，必须非常小心和精确地使用（否则你会在脚上开枪！）

于 2012-10-05T16:41:03.223 回答
5

可能是重做问题。

见：http ://en.wikipedia.org/wiki/ReDoS

可以在构造不佳的正则表达式上创建正则表达式拒绝服务。

例如，从这里：https ://www.owasp.org/index.php/Regular_expression_Denial_of_Service_-_ReDoS

这个正则表达式^(a+)+$

在此处输入图像描述

对于输入 aaaaX，上图中有 16 条可能的路径。但是对于 aaaaaaaaaaaaaaaX，有 65536 条可能的路径，并且每增加一个 a，这个数字就会翻倍。这是朴素算法存在问题的极端情况，因为它必须通过许多路径，然后失败。

我怀疑你的正则表达式的很大一部分问题是这(.|\s)有点令人困惑，因为\s它已经包含在.. 但创造了一个选择点。

编辑：我认为这是对我读过的问题的更好解释之一。

http://msdn.microsoft.com/en-us/magazine/ff646973.aspx

于 2012-10-05T15:18:19.493 回答