为什么要花这么长时间才能匹配？是虫子吗？

Question

我需要匹配web应用程序中的某些URL，即/123,456,789，并编写以下正则表达式以匹配模式：

r'(\d+(,)?)+/$'

在测试几分钟后，我甚至没有注意到：

^{pr2}$

预期的结果是没有匹配项。在

但是，此表达式几乎立即执行（请注意后面的斜杠）：

re.findall(r'(\d+(,)?)+/$', '12345121,223456,123123,3234,4523,523523/')

这是虫子吗？在

Answer 1

为了避免灾难性的回溯，我建议

r'\d+(,\d+)*/$'

Answer 2

首先，我必须说它不是一个BUG。正因为如此，它尝试了所有的可能性，它需要时间和计算资源。有时它会吞噬很多时间。当它变得非常糟糕时，它被称为灾难性回溯。在

这是python source代码中findall函数的代码：

 def findall(pattern, string, flags=0):
    """Return a list of all non-overlapping matches in the string.
    If one or more groups are present in the pattern, return a
    list of groups; this will be a list of tuples if the pattern
    has more than one group.
    Empty matches are included in the result."""
    return _compile(pattern, flags).findall(string)

如您所见，它只使用compile()函数，因此基于实际上使用Traditional NFA的_compile()函数，python将其用于正则表达式匹配，并基于 这篇关于正则表达式回溯的简短解释，在掌握正则表达式，第三版，由Jeffrey E.F.Friedl！在

The essence of an NFA engine is this: it considers each subexpression or component in turn, and whenever it needs to decide between two equally viable options, it selects one and remembers the other to return to later if need be. Situations where it has to decide among courses of action include anything with a quantifier (decide whether to try another match), and alternation (decide which alter native to try, and which to leave for later). Whichever course of action is attempted, if it’s successful and the rest of the regex is also successful, the match is finished. If anything in the rest of the regex eventually causes failure, the regex engine knows it can backtrack to where it chose the first option, and can continue with the match by trying the other option. This way, it eventually tries all possible permutations of the regex (or at least as many as needed until a match is found).

让我们进入您的模式：这样您就有了r'(\d+(,)?)+/$'和这个字符串'12345121,223456,123123,3234,4523,523523'我们有以下步骤：

• 首先，字符串的第一部分（12345121）与\d+匹配，然后{}与{}匹配。在
• 然后根据第一步，由于分组（(\d+(,)?)+）之后的+，整个字符串是匹配的
• 最后，/$没有匹配的内容。因此，(\d+(,)?)+需要“回溯”到最后一个字符之前，以便检查/$。同样，它找不到任何合适的匹配，因此在这之后（,）轮到回溯，然后\d+将回溯，并且此回溯将继续结束，直到返回None。 因此，根据字符串的长度，这需要时间，在本例中，时间非常长，并且它会创建一个完全嵌套的限定符！在

作为一个近似的基准，在本例中，您有39字符，因此您需要3^39次回溯尝试（我们有3回溯方法）。在

为了更好地理解，我在改变字符串长度的同时测量程序的运行时间：

^{pr2}$

为了避免这个问题，您可以使用以下方法之一：

• Atomic grouping（Python目前不支持，创建了一个RFE将其添加到python3中）
• 通过将嵌套组拆分为单独的正则表达式来减少回溯的可能性。在

Answer 3

{a1}的长度取决于非指数处理的长度。这与嵌套的重复和可选的逗号有关（即使某些正则表达式引擎可以确定这与尝试所有无关的重复不匹配）。这可以通过优化表达式来解决。在

---

实现这一点的最简单方法是只查找1+位数字或逗号，后跟斜杠和字符串的结尾：^{}。但是，这并不是完美的，因为它允许,123,,4,5/之类的东西。在

为此，您可以使用初始尝试的稍微优化的版本：^{}。首先，我让你的重复组non-capturing（(?:...)），这是不必要的，但它提供了一个“更干净的匹配”。接下来，也是唯一关键的一步，我停止了在组内重复\d，因为小组已经在重复了。最后，我删除了可选,周围不必要的组，因为?只影响最后一个字符。几乎这将寻找一个数字，可能是一个逗号，然后重复，最后是一个尾随/。在

---

这仍然可以匹配一个奇怪的字符串1,2,3,/，因此为了更好地使用negative lookbehind:^{}改进了原始正则表达式。这将断言在尾随的/之前没有逗号。在