Python使用正则匹配URL触发无限循环，如何排查优化？

原正则写法的问题 #

原正则不是完全错误，普通场景下可以匹配大部分URL，但存在严重的性能缺陷：嵌套可选重复分组的设计会触发正则引擎的灾难性回溯，遇到包含嵌套/相邻括号的特殊文本时会出现执行时间指数级增长，表现为类似无限循环的卡死现象。

无限循环的核心原因 #

Python的re模块使用NFA（非确定性有限自动机）正则引擎，原正则中如下片段存在设计缺陷：

(?:[^\s()<>]+|\(([^\s()<>]+|(\([^\s()<>]+\)))*\))+

该片段存在多层嵌套的可选重复分组，分组之间的匹配范围有大量重叠区域。当匹配示例文本中-(purchase-protection-for-buyers)这段结构时，引擎会不断尝试不同的分组匹配组合，匹配失败后就回溯重试，整体尝试次数会随文本长度指数级增长，最终表现为程序长时间无响应。

修复方案 #

可以通过以下两种方式修改：

方案1：使用原子组消除无效回溯（适合Python 3.11及以上版本） #

原子组(?>...)会让引擎匹配成功后就丢弃该分组的回溯分支，从根源上避免无效的路径尝试，修改后代码如下：

import re
# 把嵌套的重复分组替换为原子组
regex = r"(?i)\b((?:https?://|www\d{0,3}[.]|[a-z0-9.\-]+[.][a-z]{2,4}/)(?>(?:[^\s()<>]+|\(([^\s()<>]+|(\([^\s()<>]+\)))*\))+)(?:\(([^\s()<>]+|(\([^\s()<>]+\)))*\)|[^\s`!()\[\]{};:'\".,<>?«»“”‘’]))"
def replace_urls(text):
    return re.sub(regex, 'URL_ENTITY', text, flags=re.MULTILINE)

方案2：简化正则结构（兼容所有Python3版本） #

如果使用低于3.11的Python版本，可以直接简化URL匹配逻辑，去掉不必要的嵌套分组，使用更高效的匹配规则：

import re
# 简化后的正则，优先匹配非空白字符，再用边界规则过滤末尾的非URL字符
regex = r"(?i)\b(?:https?://|www\d{0,3}[.]|[a-z0-9.\-]+[.][a-z]{2,4}/)\S+[^\s`!()\[\]{};:'\".,<>?«»“”‘’]"
def replace_urls(text):
    return re.sub(regex, 'URL_ENTITY', text, flags=re.MULTILINE)

两种修改后的代码测试示例文本都可以秒出结果，不会出现卡死问题。

内容的提问来源于stack exchange，提问作者MAC