为什么这需要很长时间才能匹配？这是一个错误吗？

Question

我需要匹配Web应用程序中的某些URL,即/123,456,789编写此正则表达式以匹配模式:

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

我注意到它似乎没有评估,即使在测试模式几分钟后:

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

预期的结果是没有匹配.

但是,此表达式几乎立即执行(请注意尾部斜杠):

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

这是一个错误吗？

Answer 1

有一些灾难性的回溯正在进行,这将导致指数量的处理,具体取决于非匹配字符串的长度.这与您的嵌套重复和可选逗号有关(即使某些正则表达式引擎可以确定这与尝试所有无关重复不匹配).这通过优化表达式来解决.

完成此操作的最简单方法是只查找1位数字或逗号后跟斜杠和字符串结尾:[\d,]+/$.然而,这并不完美,因为它会允许类似的东西,123,,4,5/.

为此,您可以使用初始尝试的稍微优化的版本:(?:\d,?)+/$.首先,我使你的重复组非捕获((?:...))这是不必要的,但它提供了"更清晰的匹配".接下来,也是唯一关键的一步,\d因为小组已经在重复,所以我不再重复小组内部了.最后,我删除了可选项周围不必要的组,,因为?只影响最后一个字符.几乎这将寻找一个数字,可能是一个逗号,然后重复,最后是一个尾随/.

这仍然可以匹配一个奇数字符串1,2,3,/,所以对于它,我改善了你的原始正则表达式与负面的lookbehind : (?:\d,?)+(?<!,)/$. 这将断言在尾随之前没有直接的逗号/.

Answer 2

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

这是python源代码中的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()函数,因此基于 _compile()实际使用Traditional NFA该python用于其正则表达式匹配的函数,并基于关于正则表达式中的正则表达式的回溯的简短解释,由Jeffrey EF Friedl编写.!

NFA引擎的本质是:它依次考虑每个子表达式或组件,每当需要在两个同样可行的选项之间做出决定时,它会选择一个并记住另一个,如果需要则返回到以后.它必须在行动方案中决定的情况包括具有量词的任何事物(决定是否尝试另一场比赛)和交替(决定哪个改变本地尝试,以及哪个稍后离开).无论尝试哪种行为,如果它成功并且正则表达式的其余部分也成功,则匹配结束.如果正则表达式的其余部分中的任何内容最终导致失败,则正则表达式引擎知道它可以回溯到它选择第一个选项的位置,并且可以通过尝试其他选项继续匹配.这样,它最终会尝试正则表达式的所有可能的排列(或者至少在找到匹配项之前所需的数量).

让我们进入你的模式:所以你有r'(\d+(,)?)+/$'这个字符串'12345121,223456,123123,3234,4523,523523'我们有这个步骤:

• 首先,你的string(12345121)的第一部分匹配\d+,然后,匹配(,)?.
• 然后根据第一步,整个字符串匹配,因为+分组后((\d+(,)?)+)
• 然后在最后,没有什么/$可以匹配的.因此,(\d+(,)?)+需要在最后一个字符之前"回溯"到一个字符进行检查/$.再一次,它没有找到任何正确的匹配,所以在那之后它(,)转向回溯,然后\d+将回溯,并且这种回溯将继续结束直到它返回None.所以基于你的字符串的长度需要时间,在这种情况下非常高,它完全创建一个嵌套的量词!

作为一个近似的基准测试,在这种情况下,你有39个字符,所以你需要3 ^ 39回溯尝试(我们有3 个回溯方法).

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

'12345121,223456,123123,3234,4523,' 3^33 = 5.559060567×10¹?
~/Desktop $ time python ex.py

real    0m3.814s
user    0m3.818s
sys     0m0.000s

'12345121,223456,123123,3234,4523,5' 3^24 = 1.66771817×10¹? #X2 before
~/Desktop $ time python ex.py

real    0m5.846s
user    0m5.837s
sys     0m0.015s

'12345121,223456,123123,3234,4523,523' 3^36= 1.500946353×10¹? #~10X before 
~/Desktop $ time python ex.py

real    0m15.796s
user    0m15.803s
sys     0m0.008s

因此,要避免此问题,您可以使用以下方法之一:

• 原子分组(目前不支持Python,创建RFE以将其添加到Python 3)
• 通过打破嵌套组以分离正则表达式来减少回溯的可能性.

Answer 3

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

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