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

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

除了上的语法说明外

re.match

，我想我理解您正在努力采用两个或多个未知（用户输入）正则表达式，并对字符串进行更“特定”的匹配分类。

回想一下，Python正则表达式确实是一种计算机程序。大多数现代形式（包括Python的正则表达式）都基于Perl。Perl的正则表达式具有递归，回溯和其他形式的琐碎检查。确实，流氓正则表达式可以用作拒绝服务攻击的一种形式。

要在自己的计算机上查看此消息，请尝试：

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

在我的计算机上大约需要1秒钟。现在增加了

24

在

'a'*24

一个位数量较多，说

28

。那需要更长的时间。尝试

48

…您可能现在需要

CTRL

+

C

。时间随着a的增加而增加，实际上是指数的。

您可以在Russ
Cox的精彩论文“正则表达式匹配可以简单而快速”中阅读有关此问题的更多信息。Russ
Cox是Goggle工程师，于2006年建立了Google Code
Search。正如Cox所言，请考虑将正则表达式

'a?'*33 +'a'*33

与

'a'*99

带有awk和Perl（或Python或PCRE或Java或PHP或…）的字符串匹配。Awk的匹配时间为200微秒，但Perl由于需要进行指数追溯，因此需要10到15
年的时间 。

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

如果您正在寻找一种简单的方法来声明（regex_3 <regex_1
<regex_2）当使用Python或Perl的regex语言与某些字符串匹配时，我认为答案是非常困难的（即，此问题是NP
Complete）

编辑

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

您可以判断这是否可行（我不知道“特定”对您的申请意味着什么）：

import redef 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'bw+mb',        r'Mary.*little lamb',r'.*[lL]ittle [Ll]amb',r'blittleb',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 lamb11   little lamb11      .*[lL]ittle [Ll]amb15    blittleb16        little16          Mary18       bw+mb18          lamb18 .*22

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

作为两个简单的示例：

1. .*

   （或

   .*.*

   or

   .*?.*

   等）对字符串的大量修改，实际上等于字符串的长度。这是最大可能的编辑次数，最高的得分和最少的“特定”正则表达式。
2. 字符串本身相对于字符串的正则表达式尽可能具体。没有修改将一个更改为另一个，结果为0或最低分数。

如上所述，这很简单。锚应增加特异性，但在这种情况下则不可以。短字符串不起作用，因为通配符可能比字符串长。

编辑2

使用

sre_parse

Python中未记录的模块，我得到了锚点解析，可以很好地工作。类型

>>>help(sre_parse)

，如果你想了解更多…

这是该模块下面的goto worker

re

模块。自2001年以来，它已出现在每个Python发行版中，包括所有P3k版本。它 可能
会消失，但我认为这不太可能…

这是修改后的清单：

import reimport sre_parsedef 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'bw+mb',        r'Mary.*little lamb',r'.*[lL]ittle [Ll]amb',r'blittleb',s,r'little',        r'^.*lamb',r'.*.*.*b',r'.*?.*',r'.*b[lL]ittleb b[Ll]amb',        r'.*blittleb 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)printprint "   ===== %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          .*blittleb blamb$ 6  Mary.*little lamb 7     .*b[lL]ittleb b[Ll]amb10         blittleb10      .*little lamb11        little lamb11.*[lL]ittle [Ll]amb15 bw+mb15  little16 ^.*lamb17    Mary18    lamb18 .*.*.*b21      .*22   .*?.*22