<p>除了对<code>re.match</code>的语法说明之外,我认为我理解您正在努力获取两个或多个未知(用户输入)正则表达式,并对与字符串更“特定”的匹配进行分类。</p>
<p>回想一下,Python正则表达式实际上是一种计算机程序。大多数现代表单,包括Python的regex,都是基于Perl的。Perl的regex具有递归、回溯和其他形式,这些形式都不需要进行简单的检查。实际上,rogue regex可以用作<a href="http://en.wikipedia.org/wiki/ReDoS" rel="noreferrer">denial of service attack</a>的一种形式。</p>
<p>若要在自己的计算机上查看此内容,请尝试:</p>
<pre><code>>>> re.match(r'^(a+)+$','a'*24+'!')
</code></pre>
<p>在我的电脑上大约需要1秒钟。现在把<code>'a'*24</code>中的<code>24</code>增加到一个更大的数字,比如<code>28</code>。那要花很长时间。尝试<code>48</code>。。。现在您可能需要<kbd>CTRL</kbd>+<kbd>C</kbd>。事实上,时间随着a的增加呈指数增长。</p>
<p>你可以在<a href="http://swtch.com/~rsc/" rel="noreferrer">Russ Cox</a>关于<a href="http://swtch.com/~rsc/regexp/regexp1.html" rel="noreferrer">'Regular Expression Matching Can Be Simple And Fast'</a>的精彩论文中阅读更多关于这个问题的内容。罗斯考克斯是2006年建造的护目镜工程师。正如Cox所观察到的,考虑将regex<code>'a?'*33 + 'a'*33</code>与awk和Perl(或Python、PCRE、Java或PHP或……)的字符串<code>'a'*99</code>匹配,awk在200微秒内匹配,但是Perl需要10<sup>15<sup><em>年,因为指数回溯。</p>
<p>所以结论是:<em>这取决于!</em>更具体的匹配是什么意思?看看<a href="http://swtch.com/~rsc/regexp/regexp3.html" rel="noreferrer">RE2</a>中Cox的一些正则表达式简化技术。如果您的项目足够大,可以编写自己的库(或使用RE2),并且您愿意限制所使用的regex语法(即,没有回溯或递归形式),我认为答案是,您可以通过多种方式对“更好的匹配”进行分类。</p>
<p>如果您正在寻找一种简单的方法来声明(regex 3<;regex 1<;regex 2)当使用Python或Perl的regex语言与某个字符串匹配时,我认为答案是非常困难(即<a href="http://perl.plover.com/NPC/NPC-3SAT.html" rel="noreferrer">this problem</a>是<a href="http://en.wikipedia.org/wiki/NP-complete" rel="noreferrer">NP Complete</a>)</p>
<p><strong>编辑</strong></p>
<p><strong>我上面说的都是真的!</strong>但是,这里有一个技巧,可以根据一种形式的“specific”对匹配的正则表达式进行排序:从正则表达式到字符串要进行多少次编辑。编辑次数越多(或Levenshtein距离越大),regex的“特定性”就越小。</p>
<p>如果这样做有效,你将担任法官(我不知道“特定”对你的申请意味着什么):</p>
<pre><code>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)
</code></pre>
<p>程序正在获取regex的列表并与字符串<code>Mary had a little lamb</code>匹配。</p>
<p>下面是从“最具体”到“最不具体”的排序:</p>
<pre><code> ===== 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
</code></pre>
<p>这是基于(也许是简单的)以下假设:a)从正则表达式本身到匹配子字符串的编辑次数(Levenshtein距离)是通配符扩展或替换的结果;b)从匹配子字符串到初始字符串的编辑。(只要一个)</p>
<p>举两个简单的例子:</p>
<ol>
<li><code>.*</code>(或<code>.*.*</code>或<code>.*?.*</code>等)针对任何sting进行的大量编辑可以得到字符串,实际上等于字符串长度。这是可能的最大编辑、最高得分和最小“特定”正则表达式。</li>
<li>字符串本身对字符串的regex是尽可能具体的。不进行任何编辑以将一个更改为另一个,从而导致0或最低分数。</li>
</ol>
<p>如前所述,这很简单。锚定应该增加特异性,但在这种情况下它们不会。很短的刺不起作用,因为通配符可能比字符串长。</p>
<p><strong>编辑2</strong></p>
<p>我使用Python中的未记录的<code>sre_parse</code>模块使锚解析工作得非常好。键入<code>>>> help(sre_parse)</code>如果您想阅读更多。。。</p>
<p>这是<code>re</code>模块的goto工作模块。自2001年以来,它一直出现在每个Python发行版中,包括所有的P3k版本。它可能会消失,但我认为它不太可能。。。</p>
<p>这是修改后的名单婷:</p>
<pre><code>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)
</code></pre>
<p>还有苏特雷格斯的:</p>
<pre><code> ===== 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
</code></pre>