防止正则表达式中的灾难性回溯

Question

我有一个代码可以抓取一百万个网站并从他们的主页检测联系信息。

出于某些原因，当我运行编码时，它卡住了并且在抓取大约 60k 个请求后无法继续，我将我的数据库中的网站 URL 标记为 status=done

我有几次运行代码，但它卡在大约 60k 个请求中。

不会卡在某个网站

这是我正在使用的正则表达式

    emails = re.findall('[\w\.-]+@[\w-]+\.[\w\.-]+', lc_body)
    mobiles = re.findall(r"(\(?(?<!\d)\d{3}\)?-? *\d{3}-? *-?\d{4})(?!\d)|(?<!\d)(\+\d{11})(?!\d)", lc_body)
    abns = re.findall('[a][-\.\s]??[b][-\.\s]??[n][-\:\.\s]?[\:\.\s]?(\d+[\s\-\.]?\d+[\s\-\.]?\d+[\s\-\.]?\d+)', lc_body)

    licences = re.findall(r"(Licence|Lic|License|Licence)\s*(\w*)(\s*|\s*#\s*|\s*.\s*|\s*-\s*|\s*:\s+)(\d+)", lc_body, re.IGNORECASE)

我的想法是 licences 的正则表达式引起了问题，我该如何简化它？如何删除回溯？

我想找到所有可能的许可证号。

可以是License No: 2543、License: 2543、License # 2543、License #2543、License# 2543等多种组合。

Answer 1

问题是由第三组引起的：(\s*|\s*#\s*|\s*.\s*|\s*-\s*|\s*:\s+) - 所有备选方案均以 \s* 开头。这会导致大量冗余回溯，因为这些替代项可以匹配字符串中的相同位置。 最佳做法是在交替组中使用在同一位置不匹配的备选方案。

现在，看看你需要匹配的字符串，我建议使用

Lic(?:en[cs]e)?(?:\W*No:)?\W*\d+

见regex demo

使模式更加具体和线性，摆脱尽可能多的 alternations as possible, use 和字符 class。

详情:

Lic(?:en[cs]e)? - Lic 后跟 1 次或 0 次出现（(?:...)? 是可选的 non-capturing group，因为 ? 量词匹配 1 次或 0 次出现ence 或 ense 的量化子模式（字符 class [sc] 匹配 s 或 c 并且比 (s|c))
(?:\W*No:)? - 匹配 1 次或 0 次出现的 0+ 非单词字符（\W*）后跟 No: 子串
\W*
\d+ - 1 个或多个数字。

防止正则表达式中的灾难性回溯

Prevent Catastrophic Backtracking in Regex

python

regex

backtracking

python-2.7