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

Question

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

import re
string = "A|B|A|B|C|D|E|F|G"
my_pattern = 'a.*?b.*?c'

my_regex = re.compile(my_pattern, re.DOTALL|re.IGNORECASE)
matches = my_regex.findall(string)

for match in matches:
    print match

отпечатков:

A|B|A|B|C

но я бы хотел, чтобы он вернулся:

A|B|C

Есть ли способ сделать это без необходимости перебирать каждое совпадение, чтобы увидеть, содержит ли оно подстроку, которая соответствует?

Answer 1

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

>>> my_pattern = '(?=(a.*?b.*?c))'
>>> my_regex = re.compile(my_pattern, re.DOTALL|re.IGNORECASE)
>>> matches = my_regex.findall(string)
>>> print min(matches, key=len)
A|B|C

findall() вернет все возможные совпадения, поэтому вам нужно min(), чтобы получить самый короткий.

Как это работает:

• Мы не сопоставляем текст в этом регулярном выражении, просто позиции в строке (через которые движок регулярных выражений переходит во время попытки сопоставления).
• В каждой позиции движок регулярных выражений смотрит вперед, чтобы увидеть, будет ли совпадать регулярное выражение в этой позиции.
• Если это так, он будет захвачен группой захвата.
• Если нет, то не будет.
• В любом случае движок регулярных выражений затем переходит на один символ вперед и повторяет процесс до конца строки.
• Так как утверждение lookahead не использует никаких символов, будут найдены все совпадающие совпадения.

Answer 2

Другое решение регулярных выражений; он находит только последний случай. * a. * b. * c:

my_pattern = 'a(?!.*a.*b.*c).*b[^c]*c'

a(?!.*a.*?b.*?c) гарантирует отсутствие 'a.*?b.*?c' после первого «A» строки типа A | A | B | C или A | B | A | B | C или A | B | C | A | B | C в результатах исключаются

b[^c]*c гарантирует, что после «B» есть только один «C» строки типа A | B | C | B | C или A | B | C | C в результатах исключаются

Итак, у вас есть наименьшее соответствие 'a.*?b.*?c'

Answer 3

Нет. Perl возвращает самое длинное, самое левое совпадение, подчиняясь не жадным квантификаторам. Боюсь, тебе придется зацикливаться.

Редактировать: Да, я понимаю, что сказал Perl выше, но я верю, что это верно для Python.

Answer 4

Нет, в движке регулярных выражений Python нет.

Мой выбор для пользовательской функции, хотя:

import re, itertools

# directly from itertools recipes
def pairwise(iterable):
    "s -> (s0,s1), (s1,s2), (s2, s3), ..."
    a, b = itertools.tee(iterable)
    for elem in b:
        break
    return itertools.izip(a, b)

def find_matches(rex, text):
    "Find all matches, even overlapping ones"
    matches= list(rex.finditer(text))

    # first produce typical matches
    for match in matches:
        yield match.group(0)

    # next, run it for any patterns included in matches
    for match1, match2 in pairwise(matches):
        subtext= text[match1.start()+1:match2.end()+1]
        for result in find_matches(rex, subtext):
            yield result

    # also test the last match, if there was at least one
    if matches:
        subtext= text[matches[-1].start()+1:matches[-1].end()+1]
        # perhaps the previous "matches[-1].end()+1" can be omitted
        for result in find_matches(rex, subtext):
            yield result

def shortest_match(rex, text):
    "Find the shortest match"
    return min(find_matches(rex, text), key=len)

if __name__ == "__main__":
    pattern= re.compile('a.*?b.*?c', re.I)
    searched_text= "A|B|A|B|C|D|E|F|G"
    print (shortest_match(pattern, searched_text))

Answer 5

Цикл Python для поиска кратчайшего совпадения путем грубой силы, проверяющей каждую подстроку слева направо, выбирая самое короткое:

shortest = None
for i in range(len(string)):
    m = my_regex.match(string[i:])
    if m: 
        mstr = m.group()
        if shortest is None or len(mstr) < len(shortest):
            shortest = mstr

print shortest

Еще один цикл, на этот раз позволяющий re.findall выполнить тяжелую работу по поиску всех возможных совпадений, а затем методом грубой силы проверять каждое совпадение справа налево в поисках более короткой подстроки:

# find all matches using findall
matches = my_regex.findall(string)

# for each match, try to match right-hand substrings
shortest = None
for m in matches:
    for i in range(-1,-len(m),-1):
        mstr = m[i:]        
        if my_regex.match(mstr):
            break
    else:
        mstr = m

    if shortest is None or len(mstr) < len(shortest):
        shortest = mstr

print shortest

Answer 6

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

Для вашего регулярного выражения:

a.*?b.*?c

Я думаю, вы можете написать это:

a[^ab]*b[^c]*c

Трудно сделать это правильно, и я не вижу более общего или более очевидно правильного способа сделать это. (Изменить & ndash; ранее я предлагал отрицательное прогнозное утверждение, но я не вижу способа заставить это работать)

Answer 7

Это может быть полезным приложением sexegers . Соответствие регулярного выражения смещено в сторону самого длинного, самого левого выбора. Использование не жадных квантификаторов, таких как в .*?, обходит самую длинную часть, и обращение как входных данных, так и шаблона может обойти семантику с самым левым соответствием.

Рассмотрим следующую программу, которая выводит A|B|C по желанию:

#! /usr/bin/env python

import re

string = "A|B|A|B|C|D|E|F|G"
my_pattern = 'c.*?b.*?a'

my_regex = re.compile(my_pattern, re.DOTALL|re.IGNORECASE)
matches = my_regex.findall(string[::-1])

for match in matches:
    print match[::-1]

Другой способ - сделать строчку более строгой. Скажем, вы не хотите разрешать повторение символов, которые уже видели:

my_pattern = 'a[^a]*?b[^ab]*?c'

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

Answer 8

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

Answer 9

Механизм регулярных выражений начинает поиск с начала строки, пока не находит совпадение, а затем завершает работу. Таким образом, если он находит совпадение еще до того, как он рассматривает меньшее, вы не сможете заставить его рассмотреть более поздние совпадения в том же цикле - вам придется повторно выполнить регулярное выражение для подстрок.

Установка глобального флага и выбор самой короткой совпадающей строки не помогут, как видно из вашего примера - более короткое совпадение может быть подстрокой другого совпадения (или частично включено в него). Я полагаю, что вам придется начинать последующие поиски с (1 + индекс предыдущего совпадения) и продолжать в том же духе.