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

Question

是否有可能在Python中匹配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的正则表达式有递归,回溯和其他形式,无视琐碎的检查.实际上,流氓正则表达式可以用作拒绝服务攻击的一种形式.

要在您自己的计算机上查看此信息,请尝试:

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

这在我的电脑上大约需要1秒钟.现在24,'a'*24将数量增加到更大的数字28.这需要更长的时间.试试48......你可能需要CTRL+ C现在.实际上,随着增加数量的增加,时间增加是指数级的.

您可以在Russ Cox关于"正则表达式匹配可以简单快速"的精彩论文中阅读有关此问题的更多信息.Russ Cox是2006年构建谷歌代码搜索的Goggle工程师.正如考克斯观察到的那样,考虑将正则表达式与awk和Perl(或Python或PCRE或Java或PHP或......)'a?'*33 + 'a'*33字符串'a'*99匹配,在200微秒内匹配awk匹配由于指数反向跟踪,Perl需要10年¹⁵ 年.

所以结论是:它取决于!什么是更具体的比赛是什么意思？看看RE2中Cox的一些正则表达式简化技术.如果您的项目足够大以编写自己的库(或使用RE2)并且您愿意限制使用的正则表达式语法(即,没有回溯或递归形式),我认为答案是您将"更好的匹配"分类以各种方式.

如果你正在寻找一种简单的方法来说明(regex_3 <regex_1 <regex_2),当使用Python或Perl的正则表达式语言匹配某些字符串时,我认为答案是非常非常困难(即,这个问题是NP完整的)

编辑

我上面说的一切都是真的!但是,这里是基于"特定"的一种形式对正则表达式进行排序的排序:从正则表达式到字符串的编辑数量.编辑的次数越多(或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)从匹配的子字符串到初始字符串的编辑.(只需一个)

作为两个简单的例子:

1. .*(或.*.*或.*?.*等等)针对任何刺是大量的编辑才能到串,实际上等于字符串长度.这是最大可能的编辑,最高分和最少"特定"正则表达式.
2. 字符串本身对字符串的正则表达式尽可能具体.没有编辑可以将一个更改为另一个,从而导致0或最低分.

如上所述,这很简单.锚点应该增加特异性,但在这种情况下它们不会.非常短的叮咬不起作用,因为外卡可能比字符串长.

编辑2

我使用sre_parsePython中的未记录模块让锚解析工作得非常好.类型>>> help(sre_parse),如果你想了解更多...

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

以下是修订后的清单:

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) 

并投了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