Python re.match 需要更长的时间来匹配这个

Question

我需要找到匹配如下模式的输入字符串:

'fe{10,20}.clustera1.example.com'
'fe{10,20}.clustera{1,2}.example.com,fe{1,5}.clusterb{1,8}.example.com'

主机名或主机名中的 {} block 可以在输入字符串中重复任意次数。

我首先尝试使用 re 模块进行匹配，在某些情况下需要 10-30 秒。例如，如果在输入字符串的末尾添加一个空格，如下所示:

'fe{10,20}.clustera{1,2}.example.com,fe{1,5}.clusterb{1,8}.example.com '

这需要很长时间才能完成。

import re
string = 'fe{10,20}.clustera{1,2}.example.com,fe{1,5}.clusterb{1,8}.example.com '
print re.match('^([a-z.-]+|{[\d]+(,[\d]+)*})+(,([a-z.-]+|{[\d]+(,[\d]+)*})+)*$', string).group(0)

即使是简化版本(不检查 , 在 {} block 中的正确位置)也有相同的行为方式。

print re.match('^([a-z.-]+|{[\d,]+})+(,([a-z.-]+|{[\d,]+})+)*$', string).group(0)

尝试在 Perl 中使用相同的正则表达式并使用 Python 正则表达式模块。两者都运行良好且快速。

在这里，两者都不匹配(预期)但运行速度非常快。

echo 'fe{10,20}.clustera{1,2}.example.com,fe{1,5}.clusterb{1,8}.example.com ' | \
perl -nle 'print $_ if /^([a-z.-]+|{[\d]+(,[\d]+)*})+(,([a-z.-]+|{[\d]+(,[\d]+)*})+)*$/'

import regex
string = 'fe{10,20}.clustera{1,2}.example.com,fe{1,5}.clusterb{1,8}.example.com '
print re.match('^([a-z.-]+|{[\d]+(,[\d]+)*})+(,([a-z.-]+|{[\d]+(,[\d]+)*})+)*$', string).group(0)

我使用的正则表达式模式真的有问题吗？是否可以使用 re 模块本身使其工作？

用于测试的Python版本为2.7.6和2.7.8

Answer 1

您的输入字符串示例有尾随空格，但您的正则表达式不允许尾随空格。所以，无论是这些:

>>> text = 'fe{10,20}.clustera{1,2}.example.com,fe{1,5}.clusterb{1,8}.example.com'
>>> re.match('^([a-z.-]+|{[\d,]+})+(,([a-z.-]+|{[\d,]+})+)*$', text)
    <_sre.SRE_Match object; span=(0, 69), match='fe{10,20}.clustera{1,2}.example.com,fe{1,5}.clust>
>>> text = 'fe{10,20}.clustera{1,2}.example.com,fe{1,5}.clusterb{1,8}.example.com '
>>> re.match('^([a-z.-]+|{[\d,]+})+(,([a-z.-]+|{[\d,]+})+)*\s*$', text)
    <_sre.SRE_Match object; span=(0, 70), match='fe{10,20}.clustera{1,2}.example.com,fe{1,5}.clust>

快速匹配。在您的原始输入上，我不确定它是否能找到匹配项——它会根据规则进行穷举搜索，直到穷尽所有可能性，然后再没有匹配项。

给定正则表达式的具体规则是什么？如果您使用 re.DEBUG 编译正则表达式，您可以查看它们标志:

>>> re.compile('^([a-z.-]+|{[\d]+(,[\d]+)*})+(,([a-z.-]+|{[\d]+(,[\d]+)*})+)*$', re.DEBUG)
at at_beginning
max_repeat 1 4294967295
  subpattern 1
    branch
      max_repeat 1 4294967295
        in
          range (97, 122)
          literal 46
          literal 45
    or
      literal 123
      max_repeat 1 4294967295
        in
          category category_digit
      max_repeat 0 4294967295
        subpattern 2
          literal 44
          max_repeat 1 4294967295
            in
              category category_digit
      literal 125
max_repeat 0 4294967295
  subpattern 3
    literal 44
    max_repeat 1 4294967295
      subpattern 4
        branch
          max_repeat 1 4294967295
            in
              range (97, 122)
              literal 46
              literal 45
        or
          literal 123
          max_repeat 1 4294967295
            in
              category category_digit
          max_repeat 0 4294967295
            subpattern 5
              literal 44
              max_repeat 1 4294967295
                in
                  category category_digit
          literal 125
at at_end
    re.compile(r'^([a-z.-]+|{[\d]+(,[\d]+)*})+(,([a-z.-]+|{[\d]+(,[\d]+)*})+)*$',
re.UNICODE|re.DEBUG)

哪里写着 literal <num> ，您可以在 ascii 或 unicode 点表中找到它的翻译结果，例如在 asciitable.com 中找到的那个.

如果你能看到这里有两个巨大的循环，第一个 max_repeat第二个max_repeat ，每个包含许多子循环/搜索。正则表达式引擎正在搜索此排列以尝试找到匹配项。如果你能对re.DEBUG返回的操作规则稍微推理一下，它可以帮助您了解正则表达式引擎可能在做什么。