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

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

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

Это может быть полезным применением 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'

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

Петля 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

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

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

Нет, в двигателе регулярных экспрессии 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))

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

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

Для вашего Regex:

a.*?b.*?c

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

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

Это сложно получить это правильно, и я не вижу большего или более четко правильного способа сделать это. (Редактирование ранее я предложил отрицательному утверждению Lookahead, но я не вижу способ сделать эту работу.)