解决RegEx中的灾难性回溯问题

Question

我使用正则表达式来查找字符串中的URL子字符串。 我使用的RegEx是从tohster的答案中提取的- What's the cleanest way to extract URLs from a string using Python?

RE是-

r'^(?:(?:https?|ftp)://)(?:\S+(?::\S*)?@)?(?:(?:[1-9]\d?|1\d\d|2[01]\d|22[0-3])(?:\.(?:1?\d{1,2}|2[0-4]\d|25[0-5])){2}(?:\.(?:[1-9]\d?|1\d\d|2[0-4]\d|25[0-4]))|(?:(?:[a-z\u00a1-\uffff0-9]+-?)*[a-z\u00a1-\uffff0-9]+)(?:\.(?:[a-z\u00a1-\uffff0-9]+-?)*[a-z\u00a1-\uffff0-9]+)*(?:\.(?:[a-z\u00a1-\uffff]{2,})))(?::\d{2,5})?(?:/[^\s]*)?$'

我对它做了一些改动-

1. In the IPv4 detection part, I changed the order of the IP range to be found. > Precisely, changed [1-9]\d?|1\d\d|2[01]\d|22[0-3] to 25[0-5]|2[0-4][0-9]|1[0-> 9]{2}|[1-9][0-9]|[0-9] at 2 instances.
2. Made the https group - (?:https?|ftp):\/\/)?(?:\S+(?::\S*)?@) optional.

最终版本是-

^{pr2}$

我正在使用的最后一个RE似乎非常有前途，并且根据我的需求（与最初的RE相比）有了显著的改进，并且可以在Python和Java脚本中工作，除了由于我所做的更改，下面的示例给出了"catastrophic backtracking"错误-

asasasasasac31.23.53.122asasassasd

12312312312321.32.34.2312312312321

12.3423423432.234123123.123

31.134232131.231.34

可在-https://regex101.com/r/i6jDei/1处测试

我的观点是，第一个例子-asasasasasac31.23.53.122asasassasd应该有一些巧妙的方法来传递，因为IP被非数字字符包围。在

另外，有没有一种方法可以将上面的前两个示例作为有效的IPv4地址传递？在

为了解决歧义，我会选择尽可能大的地址，即

31.23.53.122

21.32.34.231

Answer 1

灾难性回溯的问题是由模式(?:(?:[a-z\u00a1-\uffff0-9]+-?)*[a-z\u00a1-\uffff0-9]+)(?:\.(?:[a-z\u00a1-\uffff0-9]+-?)*[a-z\u00a1-\uffff0-9]+)*(?:\.(?:[a-z\u00a1-\uffff]{2,}))引起的，其中{}将跳过许多组合，如果整个模式无法匹配。如您所见，字符类基本上是相同的，因此例如对于asasasasasac31，它可以匹配如下：

(asasasasasac31)
(a)(sasasasasac31)
(a)(s)(asasasasac31)
(as)(asasasasac31)

这并不是实际需要的方式，只是为了显示存在多少种组合。在

这里的错误似乎是-是可选的，我看没有理由。如果我们删除-，我们可以让它为您的示例工作（并减少已经在工作的示例的步骤数）。在

请参阅更新的regex101-demo，其中我还添加了导致灾难性回溯的示例。在

最后的模式是：

^{pr2}$