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

Question

在Python中可以匹配两个正则表达式吗？

例如，我有一个用例，我需要比较两个类似的表达式：

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

这取决于你有什么样的正则表达式；正如@carrot top所建议的那样，如果你实际上不是在处理CS意义上的“正则表达式”，而是有疯狂的扩展，那么你肯定是运气不佳。

但是，如果您有传统的正则表达式，您可能会取得更大的进步。首先，我们可以定义“更具体”的含义。假设R是正则表达式，L（R）是R生成的语言，那么如果L（R1）是L（R2）（L（R1）<；L（R2）的（严格）子集，我们可以说R1比R2更具体。到目前为止，我们只知道：在很多情况下，L（R1）既不是L（R2）的子集，也不是L（R2）的超集，所以我们可以想象这两者是不可比拟的。例如，尝试匹配“mary had a little lamb”，我们可能会找到两个匹配的表达式：.*mary和lamb.*。

一个不含糊的解决方案是通过实现定义特异性。例如，以确定的（实现定义的）方式将正则表达式转换为DFA并简单地计算状态。不幸的是，对于用户来说，这可能是相对不透明的。

实际上，您似乎有一个直观的概念，即您希望如何比较两个正则表达式。为什么不根据正则表达式的语法，简单地写下一个与你的直觉相当吻合的定义呢？

完全武断的规则如下：

1. 字符=1。
2. 字符n字符的字符范围n（比如说\b=5，因为我不确定您可能会选择如何用长的手写出来）。
3. 每个锚都是5。
4. *将其参数除以2。
5. +将其参数除以2，然后添加1。
6. .=-10。

不管怎样，只要好好想想，其他的答案能很好地勾勒出你所面临的一些问题；希望能有所帮助。

Answer 2

我觉得不可能。

另一种方法是尝试计算正则表达式也匹配的长度为n的字符串数。与长度为15个字符的100000000个字符串匹配的正则表达式比仅与长度为15个字符的10个字符串匹配的正则表达式更不具体。

当然，除非正则表达式很简单，否则计算可能的匹配数并不容易。

Answer 3

除了对re.match的语法说明之外，我认为我理解您正在努力获取两个或多个未知（用户输入）正则表达式，并对与字符串更“特定”的匹配进行分类。

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

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

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

在我的电脑上大约需要1秒钟。现在把'a'*24中的24增加到一个更大的数字，比如28。那要花很长时间。尝试48。。。现在您可能需要CTRL+C。事实上，时间随着a的增加呈指数增长。

你可以在Russ Cox关于'Regular Expression Matching Can Be Simple And Fast'的精彩论文中阅读更多关于这个问题的内容。罗斯考克斯是2006年建造的护目镜工程师。正如Cox所观察到的，考虑将regex'a?'*33 + 'a'*33与awk和Perl（或Python、PCRE、Java或PHP或……）的字符串'a'*99匹配，awk在200微秒内匹配，但是Perl需要10^{15年，因为指数回溯。}

所以结论是：这取决于！更具体的匹配是什么意思？看看RE2中Cox的一些正则表达式简化技术。如果您的项目足够大，可以编写自己的库（或使用RE2），并且您愿意限制所使用的regex语法（即，没有回溯或递归形式），我认为答案是，您可以通过多种方式对“更好的匹配”进行分类。

如果您正在寻找一种简单的方法来声明（regex 3<；regex 1<；regex 2）当使用Python或Perl的regex语言与某个字符串匹配时，我认为答案是非常困难（即this problem是NP Complete）

编辑

我上面说的都是真的！但是，这里有一个技巧，可以根据一种形式的“specific”对匹配的正则表达式进行排序：从正则表达式到字符串要进行多少次编辑。编辑次数越多（或Levenshtein距离越大），regex的“特定性”就越小。

如果这样做有效，你将担任法官（我不知道“特定”对你的申请意味着什么）：

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) 

程序正在获取regex的列表并与字符串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. .*（或.*.*或.*?.*等）针对任何sting进行的大量编辑可以得到字符串，实际上等于字符串长度。这是可能的最大编辑、最高得分和最小“特定”正则表达式。
2. 字符串本身对字符串的regex是尽可能具体的。不进行任何编辑以将一个更改为另一个，从而导致0或最低分数。

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

编辑2

我使用Python中的未记录的sre_parse模块使锚解析工作得非常好。键入>>> help(sre_parse)如果您想阅读更多。。。

这是re模块的goto工作模块。自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      =====    ===   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