python - 在 Python 中匹配 2 个正则表达式

Question

是否可以在 Python 中匹配 2 个正则表达式？

例如，我有一个用例，其中我需要比较 2 个这样的表达式:

re.match('google\.com\/maps', 'google\.com\/maps2', re.IGNORECASE)

我希望返回一个 RE 对象。

但很明显，Python 需要一个字符串作为第二个参数。
有没有办法实现这一点，还是正则表达式匹配工作方式的限制？

背景:我有一个匹配字符串的正则表达式列表 [r1, r2, r3, ...] ，我需要找出哪个表达式是给定字符串的最具体匹配。我认为我可以使它工作的方式是:
(1) 将 r1 与 r2 匹配。
(2) 然后将 r2 与 r1 匹配。
如果两者匹配，我们就有一个“平局”。如果只有 (1) 有效，则 r1 比 r2 是“更好”的匹配，反之亦然。
我会在整个列表中循环 (1) 和 (2)。

我承认这有点令人费解(主要是因为我的描述可能不连贯)，但如果有人能让我深入了解如何实现这一点，我将不胜感激。谢谢!

Answer 1

除了对 re.match 的语法澄清之外，我想我理解您正在努力采用两个或多个未知(用户输入)正则表达式并分类哪个是针对字符串的更“特定”匹配。

回想一下，Python 正则表达式确实是一种计算机程序。大多数现代形式，包括 Python 的正则表达式，都是基于 Perl 的。 Perl 的正则表达式具有递归、回溯和其他无法进行简单检查的形式。实际上，流氓正则表达式可以用作 denial of service attack 的形式。

要在您自己的计算机上查看此内容，请尝试:

>>> re.match(r'^(a+)+$','a'*24+'!')

在我的电脑上这大约需要 1 秒钟。现在将 24 中的 'a'*24 增加到更大的数字，比如 28 。那需要更长的时间。尝试 48 ... 您现在可能需要按 CTRL+C。时间随着 a 的数量增加而增加，实际上是指数级的。

您可以在 Russ Cox 关于 'Regular Expression Matching Can Be Simple And Fast' 的精彩论文中阅读有关此问题的更多信息。 Russ Cox 是 2006 年构建 Google Code Search 的 Goggle 工程师。 正如 Cox 所观察到的，考虑将正则表达式 'a?'*33 + 'a'*33 与 'a'*99 的字符串与 awk 和 Perl(或 Python 或 PCRE 或 Java 或 PHP 或 ...)匹配，但 2000 微秒匹配由于指数回溯，Perl 需要 1015 年。

所以结论是:视情况而定!更具体的比赛是什么意思？查看 RE2 中 Cox 的一些正则表达式简化技术。如果您的项目大到足以编写自己的库(或使用 RE2)并且您愿意限制使用的正则表达式语法(即，没有回溯或递归形式)，我认为答案是您将分类为“更好的匹配”以多种方式。

如果您正在寻找一种简单的方法来说明 (regex_3 < regex_1 < regex_2) 当使用 Python 或 Perl 的正则表达式语言与某个字符串匹配时，我认为答案是非常非常困难(即 this problem 是 NP Complete )

编辑

我上面说的都是真的! 但是，这里是根据一种“特定”形式对匹配的正则表达式进行排序的尝试:从正则表达式到字符串要进行多少次编辑。编辑次数越多(或 Levenshtein 距离越大)，正则表达式的“具体”程度越低。

你是判断这是否有效(我不知道你的申请对你来说“特定”意味着什么):

import re

def ld(a,b):
    "Calculates the Levenshtein distance between a and b."
    n, m = len(a), len(b)
    if n > m:
        # Make sure n <= m, to use O(min(n,m)) space
        a,b = b,a
        n,m = m,n

    current = range(n+1)
    for i in range(1,m+1):
        previous, current = current, [i]+[0]*n
        for j in range(1,n+1):
            add, delete = previous[j]+1, current[j-1]+1
            change = previous[j-1]
            if a[j-1] != b[i-1]:
                change = change + 1
            current[j] = min(add, delete, change)      
    return current[n]

s='Mary had a little lamb'    
d={}
regs=[r'.*', r'Mary', r'lamb', r'little lamb', r'.*little lamb',r'\b\w+mb',
        r'Mary.*little lamb',r'.*[lL]ittle [Ll]amb',r'\blittle\b',s,r'little']

for reg in regs:
    m=re.search(reg,s)
    if m:
        print "'%s' matches '%s' with sub group '%s'" % (reg, s, m.group(0))
        ld1=ld(reg,m.group(0))
        ld2=ld(m.group(0),s)
        score=max(ld1,ld2)
        print "  %i edits regex->match(0), %i edits match(0)->s" % (ld1,ld2)
        print "  score: ", score
        d[reg]=score
        print
    else:
        print "'%s' does not match '%s'" % (reg, s)   

print "   ===== %s =====    === %s ===" % ('RegEx'.center(10),'Score'.center(10))

for key, value in sorted(d.iteritems(), key=lambda (k,v): (v,k)):
    print "   %22s        %5s" % (key, value) 

该程序正在获取正则表达式列表并与字符串 Mary had a little lamb 匹配。

以下是从“最具体”到“最不具体”的排序排名:

   =====   RegEx    =====    ===   Score    ===
   Mary had a little lamb            0
        Mary.*little lamb            7
            .*little lamb           11
              little lamb           11
      .*[lL]ittle [Ll]amb           15
               \blittle\b           16
                   little           16
                     Mary           18
                  \b\w+mb           18
                     lamb           18
                       .*           22

这基于(可能是简单的)假设:a)从正则表达式本身到匹配子字符串的编辑次数(Levenshtein 距离)是通配符扩展或替换的结果； b) 从匹配的子字符串到初始字符串的编辑。 (随便拿一个)

作为两个简单的例子:

.*(或 .*.* 或 .*?.* 等)对任何字符串进行大量编辑以获取字符串，实际上等于字符串长度。这是最大可能的编辑、最高分和最不“特定”的正则表达式。

字符串本身对字符串的正则表达式尽可能具体。没有编辑将一个更改为另一个导致 0 或最低分数。

如前所述，这很简单。 anchor 应该增加特异性，但在这种情况下它们不会。非常短的字符串不起作用，因为通配符可能比字符串长。

编辑 2

我使用 Python 中未记录的 sre_parse 模块使 anchor 解析工作得非常好。如果您想阅读更多内容，请输入 >>> help(sre_parse)...

这是 re 模块下的 goto worker 模块。自 2001 年以来，它一直存在于每个 Python 发行版中，包括所有 P3k 版本。它可能会消失，但我认为不太可能......

这是修订后的 list :

import re
import sre_parse

def ld(a,b):
    "Calculates the Levenshtein distance between a and b."
    n, m = len(a), len(b)
    if n > m:
        # Make sure n <= m, to use O(min(n,m)) space
        a,b = b,a
        n,m = m,n

    current = range(n+1)
    for i in range(1,m+1):
        previous, current = current, [i]+[0]*n
        for j in range(1,n+1):
            add, delete = previous[j]+1, current[j-1]+1
            change = previous[j-1]
            if a[j-1] != b[i-1]:
                change = change + 1
            current[j] = min(add, delete, change)      
    return current[n]

s='Mary had a little lamb'    
d={}
regs=[r'.*', r'Mary', r'lamb', r'little lamb', r'.*little lamb',r'\b\w+mb',
        r'Mary.*little lamb',r'.*[lL]ittle [Ll]amb',r'\blittle\b',s,r'little',
        r'^.*lamb',r'.*.*.*b',r'.*?.*',r'.*\b[lL]ittle\b \b[Ll]amb',
        r'.*\blittle\b \blamb$','^'+s+'$']

for reg in regs:
    m=re.search(reg,s)
    if m:
        ld1=ld(reg,m.group(0))
        ld2=ld(m.group(0),s)
        score=max(ld1,ld2)
        for t, v in sre_parse.parse(reg):
            if t=='at':      # anchor...
                if v=='at_beginning' or 'at_end':
                    score-=1   # ^ or $, adj 1 edit

                if v=='at_boundary': # all other anchors are 2 char
                    score-=2

        d[reg]=score
    else:
        print "'%s' does not match '%s'" % (reg, s)   

print
print "   ===== %s =====    === %s ===" % ('RegEx'.center(15),'Score'.center(10))

for key, value in sorted(d.iteritems(), key=lambda (k,v): (v,k)):
    print "   %27s        %5s" % (key, value) 

和 soted RegEx 的:

   =====      RegEx      =====    ===   Score    ===
        Mary had a little lamb            0
      ^Mary had a little lamb$            0
          .*\blittle\b \blamb$            6
             Mary.*little lamb            7
     .*\b[lL]ittle\b \b[Ll]amb           10
                    \blittle\b           10
                 .*little lamb           11
                   little lamb           11
           .*[lL]ittle [Ll]amb           15
                       \b\w+mb           15
                        little           16
                       ^.*lamb           17
                          Mary           18
                          lamb           18
                       .*.*.*b           21
                            .*           22
                         .*?.*           22