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

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

有一些 catastrophic backtracking根据不匹配字符串的长度，继续下去会导致指数级的处理。这与您的嵌套重复和可选逗号有关(即使某些正则表达式引擎可以确定这与尝试所有无关的重复不匹配)。这是通过优化表达式来解决的。

---

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

为此，您可以使用最初尝试的稍微优化的版本: (?:\d,?)+/$ .首先，我做了你的重复组non-capturing ( (?:...) )这不是必需的，但它提供了“更干净的匹配”。 接下来，也是唯一关键的一步，我不再重复 \d由于组已经在重复，所以在组内部。 最后，我删除了可选的 , 周围不必要的组。自从 ?只影响最后一个字符。几乎这会寻找一个数字，也许是一个逗号，然后重复，最后是尾随 / .

---

这仍然可以匹配一个奇数字符串 1,2,3,/ ，所以我用 negative lookbehind 改进了你原来的正则表达式: (?:\d,?)+(?<!,)/$ .这将断言在尾随 / 之前没有逗号。 .