Python re.findall() 不会终止

Question

下面我有一个相当复杂的正则表达式，似乎永远不会终止。这不仅仅是花很长时间的问题——我已经等了几分钟才得到回复，但运气不好。

下面是一些重现问题的代码:

import re    
link = re.compile(u'(?i)((?:https?://|www\d{0,3}[.]|[a-z0-9.\-]+[.][a-z]{2,4}/)(?:[^\s()<>]+|\((?:[^\s()<>]+|(?:\([^\s()<>]+\)))*\))+(?:\((?:[^\s()<>]+|(?:\([^\s()<>]+\)))*\)|[^\s`!()\[\]{};:\'".,<>?\xab\xbb\u201c\u201d\u2018\u2019]))', re.IGNORECASE)
text = "Check out this link http://ru.wikipedia.org/wiki/%D0%9B%D0%BE%D0%B2%D0%B5%D1%86_%D1%81%D0%BD%D0%BE%D0%B2_(%D0%B0%D0%BC%D1%83%D0%BB%D0%B5%D1%82"
matches = re.findall(link, text)

这里是将 re.DEBUG 作为标志传递给模式的输出:

subpattern 1
  subpattern None
    branch
      literal 104
      literal 116
      literal 116
      literal 112
      max_repeat 0 1
        literal 115
      literal 58
      literal 47
      literal 47
    or
      literal 119
      literal 119
      literal 119
      max_repeat 0 3
        in
          category category_digit
      literal 46
    or
      max_repeat 1 4294967295
        in
          range (97, 122)
          range (48, 57)
          literal 46
          literal 45
      literal 46
      max_repeat 2 4
        in
          range (97, 122)
      literal 47
  max_repeat 1 4294967295
    subpattern None
      branch
        max_repeat 1 4294967295
          in
            negate None
            category category_space
            literal 40
            literal 41
            literal 60
            literal 62
      or
        literal 40
        max_repeat 0 4294967295
          subpattern None
            branch
              max_repeat 1 4294967295
                in
                  negate None
                  category category_space
                  literal 40
                  literal 41
                  literal 60
                  literal 62
            or
              subpattern None
                literal 40
                max_repeat 1 4294967295
                  in
                    negate None
                    category category_space
                    literal 40
                    literal 41
                    literal 60
                    literal 62
                literal 41
        literal 41
  subpattern None
    branch
      literal 40
      max_repeat 0 4294967295
        subpattern None
          branch
            max_repeat 1 4294967295
              in
                negate None
                category category_space
                literal 40
                literal 41
                literal 60
                literal 62
          or
            subpattern None
              literal 40
              max_repeat 1 4294967295
                in
                  negate None
                  category category_space
                  literal 40
                  literal 41
                  literal 60
                  literal 62
              literal 41
      literal 41
    or
      in
        negate None
        category category_space
        literal 96
        literal 33
        literal 40
        literal 41
        literal 91
        literal 93
        literal 123
        literal 125
        literal 59
        literal 58
        literal 39
        literal 34
        literal 46
        literal 44
        literal 60
        literal 62
        literal 63
        literal 171
        literal 187
        literal 8220
        literal 8221
        literal 8216
        literal 8217

Answer 1

如果您从字符串的末尾删除 %D0%B5%D1%82，它会起作用(尽管大约需要 10 秒)。随着字符串和匹配项的复杂性增加，检查表达式条件所需的处理量呈指数级增长，并且您的 CPU 利用率可能会一直飙升至 100%。

这叫做 catastrphic backtracking -- 在我看来你遇到了 99 到 100 个问题 ;)

CPU 被阻塞到无法继续处理表达式的程度。

解决方案:

• 简化你的表达方式(更可靠和明智的选择)，或者
• 在尝试验证样本之前缩短/截断样本(这首先违背了使用表达式的目的)

老实说，我不知道这是否会为您减少，但由于您有很多重叠的条件，这似乎可以减少它们。最好检查一堆样本来验证:

(?i)(?:https?://|www\d{0,3}[.]|[a-z0-9.\-]+[.][a-z]{2,4}/)((?:\(?[^\s()<>]+\)?)*[^\s`!()\[\]{};:\'".,<>?\xab\xbb\u201c\u201d\u2018\u2019])

示例:http://regex101.com/r/lV0oL4

我相信您可以进一步简化它，这只是一个快速尝试。字符串处理时间:小于 100 毫秒。