python - 理解是什么让这个正则表达式如此缓慢

Question

我有一个正则表达式:

import re

regexp = re.compile(r'^(?P<parts>(?:[\w-]+/?)+)/$')

它匹配一个像foo/bar/baz/这样的字符串，并将foo/bar/baz放在一个名为parts的组中( /? 结合 /$ 支持这个)。

这工作得很好，直到您匹配一个不以斜线结尾的字符串。然后，随着您添加到要匹配的字符串中的每个新字符，它会以看似指数的速度变慢。

例子

# This is instant (trailing slash)
regexp.match('this-will-take-no-time-at-all/')

# This is slow
regexp.match('this-takes-about-5-seconds')

# This will not finish
regexp.match('this-probably-will-not-finish-until-the-day-star-turns-black')

我试图理解为什么这个特定的递归问题只在 /$(尾部斜线)不在字符串中(即不匹配)时发生。你能帮我理解在尾部斜杠和非尾部斜杠情况下底层算法的控制流吗？

注意事项

我不是在为我想要的模式寻找解决方案。我正在尝试了解特定的正则表达式。

Answer 1

由于 catastrophic backtracking，它变得越来越慢在你的正则表达式中:

您可以使用此正则表达式修复灾难性回溯:

^(?P<parts>(?:[\w-]+/)*[\w-]+)/$

根据上面的链接:

The solution to avoid catastrophic backtracking is simple. When nesting repetition operators, make absolutely sure that there is only one way to match the same match.