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

Ответ 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 ¹⁵ лет из-за экспоненциального отслеживания следа.

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

Если вы ищете простой способ заявить, что (regex_3 &ltge regex_1 &ltge 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

Ответ 2

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

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

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

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

Выполняются абсолютно произвольные правила:

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

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

Ответ 3

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

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

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

Ответ 4

Вариант 1:

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

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

Вариант 2:

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

Но если он соответствует строгому супермножеству мутаций, то он ", вероятно, менее конкретный", чем другой.

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

Вариант 3:

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

Ответ 5

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

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

Ответ 6

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'

Ответ 7

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

Это, безусловно, возможно. Используйте скользящие группы сопоставления, связанные с | для изменения. Если вы упорядочиваете скользящие группы сопоставлений по определенному регулярному выражению до наименьшего значения, ранжирование в возвращаемом кортеже из m.groups() покажет, насколько конкретным является ваше совпадение. Вы также можете использовать именованные группы, чтобы указать, насколько конкретным является ваше соответствие, например s10 для очень специфических и 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[a-z]+)',s1)
>>> m2=re.match(r'(^google\.com\/maps\dtext$)|(.*go[a-z]+)',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[a-z]+)|(?P<s0>[a-z]+)')
>>> m3=patt.match(s3)
>>> m3.groups()
(None, None, 'blah')
>>> m3.groupdict()
{'s10': None, 's0': 'blah', 's5': None}

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

Ответ 8

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