为什么python的re.search方法挂起？

Question

我正在使用python regex库解析一些字符串，目前我发现我的regex太复杂或正在搜索的字符串太长。

这是挂断的示例：

>>> import re
>>> reg = "(\w+'?\s*)+[-|~]\s*((\d+\.?\d+\$?)|(\$?\d+\.?\d+))"
>>> re.search(reg, "**LOOKING FOR PAYPAL OFFERS ON THESE PAINTED UNCOMMONS**") #Hangs here...

我不确定发生了什么。任何帮助表示赞赏！

编辑：这是与我要匹配的示例的链接：Regxr

Answer 1

代码执行被挂起的原因是灾难性的回溯，这是由于量化组内有一个强制性模式和1+个可选模式（可以匹配空字符串的模式）(\w+'?\s*)+，该模式允许regex引擎测试很多匹配路径，因此需要花费很多完成时间太长。

我建议以这样一种方式解开有问题的组，'或者\s将其打包成一个可选的组：

(\w+(?:['\s]+\w+)*)\s*[-~]\s*(\$?\d+(?:\.\d+)?\$?)
^^^^^^^^^^^^^^^^^^^***

见正则表达式演示

在这里，(\w+(?:['\s]+\w+)*)将匹配1+个单词字符，然后匹配0+个1+ '或空格的序列，后跟1+个单词字符。这样，模式变为线性，并且如果出现不匹配的字符串，则正则表达式引擎会更快地使匹配失败。

模式的其余部分：

• \s*[-~]\s* - -或~用0+空格包裹
• (\$?\d+(?:\.\d+)?\$?) -第2组拍摄
  • \$?-1或0个$符号
  • \d+ -1个以上的数字
  • (?:\.\d+)? -1个或0个以下零序列：
    • \. -一个点
    • \d+ -1个以上的数字
  • \$?-1或0个$符号