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

Question

我正在使用 RegEx 在字符串中查找 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]*)?$'

我对它做了一些修改-

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.

Made the https group - (?:https?|ftp):\/\/)?(?:\S+(?::\S*)?@) optional.

最终版本是-

(?:(?:https?|ftp):\/\/)?(?:\S+(?::\S*)?@)?(?:((25[0-5]|2[0-4][0-9]|1[0-9]{2}|[1-9][0-9]|[0-9])\.){3}(25[0-5]|2[0-4][0-9]|1[0-9]{2}|[1-9][0-9]|[0-9])|(?:(?:[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]*)?

我使用的最终 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,}))引起的，其中(?:[a-z\u00a1-\uffff0-9]+-?)*[a-z\u00a1-\uffff0-9]+)会跳过很多组合，如果整体模式无法匹配。如您所见，字符类基本相同，例如对于 asasasasasac31 它可以像这样匹配：

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

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

这里的错误似乎是 - 是可选的，我认为没有理由这样做。如果我们删除 - ，我们会使其适用于您的示例（并减少已经工作的示例的步骤数）。

查看更新后的 regex101-demo，我在其中添加了导致灾难性回溯的样本。

最后的模式是：

(?:(?:https?|ftp):\/\/)?(?:\S+(?::\S*)?@)?(?:((25[0-5]|2[0-4][0-9]|1[0-9]{2}|[1-9][0-9]|[0-9])\.){3}(25[0-5]|2[0-4][0-9]|1[0-9]{2}|[1-9][0-9]|[0-9])|(?:(?:[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]*)?

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

Resolving Catastrophic Backtracking issue in RegEx

python

regex

url

ip-address

ipv4