为什么python的搜索方法吊死？

Question

我正在使用python正则表达式库来解析一些字符串，目前我发现我的正则表达式要么太复杂，要么我搜索的字符串太长。在

下面是一个挂机的例子：

>>> 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

代码执行挂起的原因是catastrophic backtracking，这是因为在量化组(\w+'?\s*)+内有一个强制性的和1+可选的模式（那些可以匹配空字符串的模式），它允许正则表达式引擎测试大量匹配路径，其中很多路径太长以至于无法完成。在

我建议展开有问题的组，使'或{}成为必须的，并将它们包装在一个可选的组中：

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

参见regex demo

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

模式的其余部分：

• \s*[-~]\s*-用0+空格包装的-或{}
• (\$?\d+(?:\.\d+)?\$?)-第2组捕获
  • \$?-1或0$符号
  • \d+-1+位
  • (?:\.\d+)?-1或0零序列：
    • \.-一个点
    • \d+-1+位
  • \$?-1或0$符号