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

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-]+)/$

根据上面的link：

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.

Answer 2

Wiktor Stribizew 是正确的。问题是重复模式内斜线后的问号。所以，你给出的模式：

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

说，寻找一组或多组一个或多个单词字符或破折号可能后跟一个斜杠，那么最后应该有一个斜杠。

因此，对于像 arm/ 这样的字符串，内部分组可以是以下任何一种：

(arm)/
(ar)(m)/
(a)(rm)/
(a)(r)(m)/

随着字符串变长，如果正则表达式第一次尝试匹配失败，它将检查越来越多的组合来尝试匹配。为避免这种情况，可以使用以下方法实现相同的匹配：

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

因为此版本只能以一种方式匹配您的目标字符串。

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

Understanding what makes this regexp so slow

python

regex

regex-greedy

例子

备注