Соответствие 2 регулярных выражений в Python

Вне разъяснения синтаксиса на re.match , я думаю, что понимаю, что вы re.match с принятием двух или более неизвестных (пользовательских) выражений регулярных выражений и классификации, которая является более «конкретным» совпадением со строкой.

Вспомните на мгновение, что регулярное выражение Python действительно является типом компьютерной программы. Большинство современных форм, включая регулярное выражение Python, основаны на Perl. У регулярных выражений Perl есть рекурсия, откат и другие формы, которые бросают вызов тривиальному контролю. Действительно, regex изгои может использоваться как форма атаки отказа в обслуживании .

Чтобы увидеть это на своем собственном компьютере, попробуйте:

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

Это занимает около 1 секунды на моем компьютере. Теперь увеличьте 24 в 'a'*24 до немного большего числа, скажем 28 . Это займет намного больше времени. Попробуйте 48 … Теперь вам, вероятно, понадобится CTRL + C. Увеличение времени по мере того, как увеличение числа, на самом деле, экспоненциально.

Вы можете больше узнать об этой проблеме в замечательной статье Русса Кокса «Регулярное выражение соответствия может быть простым и быстрым» . Russ Cox – инженер Goggle, который построил Google Code Search в 2006 году. Как замечает Кокс, рассмотрите сопоставление регулярного выражения 'a?'*33 + 'a'*33 с строкой 'a'*99 с awk и Perl (или Python или PCRE или Java или PHP или …) Awk соответствует 200 микросекундам, но Perl потребует ^10-15 лет из-за экспоненциального отслеживания следа.

Итак, вывод: это зависит! Что вы подразумеваете под более конкретным соответствием? Посмотрите на некоторые методы упрощения регулярного выражения Cox в RE2 . Если ваш проект достаточно велик, чтобы писать собственные библиотеки (или использовать RE2), и вы хотите ограничить используемую грамматику регулярных выражений (т. Е. Не возвращать или рекурсивные формы), я думаю, что ответ заключается в том, что вы бы классифицировали «лучшее соответствие», по-разному.

Если вы ищете простой способ заявить, что (regex_3 <regex_1 <regex_2) при сопоставлении с некоторой строкой с использованием языка регулярных выражений Python или Perl, я считаю, что ответ очень тяжелый (т. Е. Эта проблема – NP Complete )

редактировать

Все, что я сказал выше, верно! Тем не менее, здесь приведен пример сортировки совпадающих регулярных выражений, основанных на одной форме «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 

Это основано на (возможно, упрощенном) предположении, что: а) количество изменений (расстояние Левенштейна), чтобы получить от самого регулярного выражения до подстроки соответствия, является результатом разложений или замен по шаблону; б) изменения, которые нужно получить от подстроки соответствия к исходной строке. (просто возьмите)

В качестве двух простых примеров:

1. .* (или .*.* или .*?.* т. д.) против любого sting – это большое количество исправлений, которые можно получить до строки, фактически равной длине строки. Это максимально возможные изменения, наивысший балл и наименьшее «конкретное» регулярное выражение.
2. Регулярное выражение самой строки для строки максимально подробно. Никаких изменений, чтобы изменить один на другой, в результате получился 0 или самый низкий балл.

Как было сказано, это упрощенно. Якорям следует повышать специфичность, но в этом случае они не действуют. Очень короткие жало не работают, потому что дикая карта может быть длиннее строки.

Изменить 2

Я получил синтаксический анализ, чтобы хорошо работать с использованием недокументированного модуля sre_parse в Python. Тип >>> help(sre_parse) если вы хотите узнать больше …

Это модуль рабочего модуля, лежащий в основе модуля 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:

  ===== 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 

Это зависит от того, какие у вас регулярные выражения; как подсказывает @ морковная вершина, если вы на самом деле не имеете дело с «регулярными выражениями» в смысле CS и вместо этого имеете сумасшедшие расширения, то вам определенно не повезло.

Однако, если у вас есть традиционные регулярные выражения, вы можете сделать немного больше прогресса. Во-первых, мы могли бы определить, что означает «более конкретный». Скажем, R является регулярным выражением, а L (R) является языком, порожденным R. Тогда мы можем сказать, что R1 более специфичен, чем R2, если L (R1) является (строгим) подмножеством L (R2) (L (R1) <L (R2)). Это доставляет нам до сих пор: во многих случаях L (R1) не является ни подмножеством, ни надмножеством L (R2), и поэтому мы можем представить себе, что эти два как-то несравнимы. Например, при попытке сопоставить «у мари был маленький ягненок», мы могли бы найти два подходящих выражения:. .*mary и lamb.* .

Одно недвусмысленное решение заключается в определении специфики посредством реализации . Например, преобразуйте свое регулярное выражение в детерминированный (определенный реализацией) способ в DFA и просто считайте состояния. К сожалению, это может быть относительно непрозрачным для пользователя.

Действительно, у вас, похоже, есть интуитивное представление о том, как вы хотите, чтобы два регулярных выражения сравнивались, специфично. Почему бы просто не записать определение специфичности, основанное на синтаксисе регулярных выражений, которое соответствует вашей интуиции достаточно хорошо?

Полностью произвольные правила следуют:

1. Символы = 1 .
2. Диапазоны символов из n символов = n (и, скажем, \b = 5 , потому что я не уверен, как вы могли бы написать его из рук в руки).
3. Якорям по 5 штук.
4. * делит свой аргумент на 2 .
5. + делит свой аргумент на 2 , затем добавляет 1 .
6. . = -10 .

Во всяком случае, просто пища для размышлений, так как другие ответы хорошо отражают некоторые проблемы, с которыми вы сталкиваетесь; Надеюсь, поможет.

Я не думаю, что это возможно.

Альтернативой было бы попытаться вычислить количество строк длины n, также соответствующее регулярному выражению. Регулярное выражение, которое соответствует 1 000 000 000 строк длиной 15 символов, менее специфично, чем та, которая соответствует только 10 строкам длиной 15 символов.

Конечно, вычисление количества возможных совпадений не является тривиальным, если регулярные выражения не являются простыми.

Опция 1:

Поскольку пользователи поставляют регулярные выражения, возможно, попросите их также представить некоторые тестовые строки, которые, по их мнению, являются иллюстрацией их специфичности регулярного выражения. (т. е. отображение своего регулярного выражения более конкретное, чем регулярное выражение конкурента). Соберите все тестовые строки пользователя, а затем проверьте все регулярные выражения на весь набор тестовых строк.

Чтобы создать хорошее регулярное выражение, автор должен был подумать о том, какие строки совпадают и не соответствуют их регулярному выражению, поэтому им должно быть легко предоставить хорошие тестовые строки.

Вариант 2:

Вы можете попробовать подход Монте-Карло: начиная с строки, с которой совпадают оба регулярных выражения, напишите генератор, который генерирует мутации этой строки (переставляйте символы, добавляйте / удаляйте символы и т. Д.). Если оба регулярных выражения совпадают или не совпадают друг с другом для каждой мутации, тогда регулярные выражения « вероятно, связаны ». Если кто-то соответствует мутациям, который другой не делает, и наоборот, то они « абсолютно связаны ».

Но если один соответствует строгому набору мутаций, то он « скорее менее конкретный », чем другой.

Приговор после большого количества мутаций может быть не всегда правильным, но может быть разумным.

Вариант 3:

Используйте инверсию ipermute или pyParsing для генерации строк, которые соответствуют каждому регулярному выражению. Это будет работать только с регулярными выражениями, использующими ограниченное подмножество синтаксиса регулярных выражений.

Я думаю, вы могли бы сделать это, посмотрев результат согласования с самым длинным результатом

 >>> m = re.match(r'google\.com\/maps','google.com/maps/hello') >>> len(m.group(0)) 15 >>> m = re.match(r'google\.com\/maps2','google.com/maps/hello') >>> print (m) None >>> m = re.match(r'google\.com\/maps','google.com/maps2/hello') >>> len(m.group(0)) 15 >>> m = re.match(r'google\.com\/maps2','google.com/maps2/hello') >>> len(m.group(0)) 16 

 re.match('google\.com\/maps', 'google\.com\/maps2', re.IGNORECASE) 

Второй элемент для re.match() выше – строка – поэтому он не работает: регулярное выражение говорит, что оно соответствует периоду после Google, но вместо этого находит обратную косую черту. Вам нужно удвоить обратную косую черту в регулярном выражении, которое используется как регулярное выражение:

 def compare_regexes(regex1, regex2): """returns regex2 if regex1 is 'smaller' than regex2 returns regex1 if they are the same returns regex1 if regex1 is 'bigger' than regex2 otherwise returns None""" regex1_mod = regex1.replace('\\', '\\\\') regex2_mod = regex2.replace('\\', '\\\\') if regex1 == regex2: return regex1 if re.match(regex1_mod, regex2): return regex2 if re.match(regex2_mod, regex1): return regex1 

Вы можете изменить возврат к тому, что вам больше подходит. О, и убедитесь, что вы используете необработанные строки с re. r'like this, for example'

Возможно ли совместить 2 регулярных выражения в Python?

Это, безусловно, возможно. Используйте скользящие группы совпадений, соединенные | для изменения. Если вы упорядочиваете скобковые группы сопоставлений по определенному регулярному выражению до наименьшего значения, ранжирование в возвращаемом кортеже из m.groups() покажет, насколько конкретным является ваше соответствие. Вы также можете использовать именованные группы для определения того, насколько конкретным является ваше соответствие, например s10 для очень специфического и s0 для s0 соответствия.

 >>> s1='google.com/maps2text' >>> s2='I forgot my goggles at the house' >>> s3='blah blah blah' >>> m1=re.match(r'(^google\.com\/maps\dtext$)|(.*go[az]+)',s1) >>> m2=re.match(r'(^google\.com\/maps\dtext$)|(.*go[az]+)',s2) >>> m1.groups() ('google.com/maps2text', None) >>> m2.groups() (None, 'I forgot my goggles') >>> patt=re.compile(r'(?P<s10>^google\.com\/maps\dtext$)| ... (?P<s5>.*go[az]+)|(?P<s0>[az]+)') >>> m3=patt.match(s3) >>> m3.groups() (None, None, 'blah') >>> m3.groupdict() {'s10': None, 's0': 'blah', 's5': None} 

Если вы не знаете заранее, какое регулярное выражение является более конкретным, это гораздо труднее решить. Вы хотите взглянуть на эту статью, защищая регулярные выражения от имен файловой системы.

Я понимаю, что это не решение, но поскольку нет однозначного способа определить, что является «самым конкретным соответствием», конечно, когда это зависит от того, что означают ваши пользователи », проще всего было бы спросить их для обеспечения их собственного приоритета. Например, просто разместив регулярные выражения в правильном порядке. Тогда вы можете просто взять первый, который соответствует. Если вы ожидаете, что пользователи будут довольны регулярными выражениями, это может быть не слишком много, чтобы спросить?