是否可以在 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)。
我承认这有点令人费解(主要是因为我的描述可能不连贯),但如果有人能让我深入了解如何实现这一点,我将不胜感激。谢谢!
最佳答案
除了对 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) 从匹配的子字符串到初始字符串的编辑。 (随便拿一个)
作为两个简单的例子:
.*
(或 .*.*
或 .*?.*
等)对任何字符串进行大量编辑以获取字符串,实际上等于字符串长度。这是最大可能的编辑、最高分和最不“特定”的正则表达式。 如前所述,这很简单。 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
关于python - 在 Python 中匹配 2 个正则表达式,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/7463233/