Ответ 1
Вне разъяснения синтаксиса на re.match, я думаю, что понимаю, что вы боретесь с принятием двух или более неизвестных (пользовательских) выражений регулярных выражений и классификации, которая является более "конкретным" совпадением со строкой.
Вспомните, что регулярное выражение Python действительно является типом компьютерной программы. Большинство современных форм, в том числе Python regex, основаны на Perl. Регулярное регулярное выражение имеет рекурсию, обратное отслеживание и другие формы, которые бросают вызов тривиальному контролю. Действительно, regex-мошенник может использоваться как форма атаки отказа в обслуживании.
Чтобы увидеть это на своем собственном компьютере, попробуйте:
>>> re.match(r'^(a+)+$','a'*24+'!')
Это занимает около 1 секунды на моем компьютере. Теперь увеличьте 24 в 'a'*24 до более большого числа, скажем 28. Это займет намного больше времени. Попробуйте 48... Теперь вам, возможно, понадобится CTRL + C. Увеличение времени по мере того, как число увеличения, по сути, экспоненциально.
Подробнее об этой проблеме вы можете прочитать в Russ Cox замечательная статья на "Регулярное соответствие выражению может быть простым и быстрым" . Russ Cox - инженер Goggle, который построил Поиск кода Google в 2006 году. Как отмечает Кокс, рассмотрите сопоставление регулярного выражения 'a?'*33 + 'a'*33 со строкой 'a'*99 с awk и Perl (или Python или PCRE или Java или PHP или...) Awk соответствует 200 микросекундам, но Perl потребует 10 15 лет из-за экспоненциального отслеживания следа.
Итак, вывод: это зависит! Что вы подразумеваете под более конкретным соответствием? Посмотрите на некоторые методы упрощения регулярного выражения Cox в RE2. Если ваш проект достаточно велик, чтобы писать собственные библиотеки (или использовать RE2), и вы хотите ограничить используемую грамматику регулярных выражений (т.е. Не возвращать или рекурсивные формы), я думаю, что ответ заключается в том, что вы бы классифицировали "лучшее соответствие", по-разному.
Если вы ищете простой способ заявить, что (regex_3 <ge regex_1 <ge regex_2), когда сопоставляется с некоторой строкой с использованием языка регулярных выражений Python или Perl, я считаю, что ответ очень тяжелый (т.е. эта проблема является NP Complete)
Edit
Все, что я сказал выше, истинно!. Однако, это удар по сортировке совпадающих регулярных выражений, основанных на одной форме "specific": сколько изменений нужно получить из регулярного выражения в строку. Чем больше количество редактирований (или, тем выше расстояние Левенштейна), тем меньше "конкретное" регулярное выражение.
Вы будете судьей, если это сработает (я не знаю, что означает "конкретный" для вашего приложения):
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
Это основано на (возможно, упрощенном) предположении, что: а) количество изменений (расстояние Левенштейна), чтобы получить от самого регулярного выражения до подстроки соответствия, является результатом разложений или замен по шаблону; б) изменения, которые нужно получить от подстроки соответствия к исходной строке. (просто возьмите один)
В качестве двух простых примеров:
-
.*(или.*.*или.*?.*и т.д.) против любого sting - это большое количество исправлений, которые можно получить до строки, фактически равной длине строки. Это максимально возможные изменения, наивысший балл и наименьшее "конкретное" регулярное выражение. - Регулярное выражение самой строки для строки максимально подробно. Нет изменений, чтобы изменить один на другой, что приводит к 0 или самому низкому результату.
Как указано, это упрощенно. Якорям следует повышать специфичность, но в этом случае они не действуют. Очень короткие жало не работают, потому что дикая карта может быть длиннее строки.
Изменить 2
Я получил синтаксический анализ для корректной работы с использованием недокументированного модуля sre_parse в Python. Введите >>> help(sre_parse), если вы хотите прочитать больше...
Это рабочий модуль goto, лежащий в основе модуля re. Он был в каждом дистрибутиве Python с 2001 года, включая все версии 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's:
===== 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