Комбинаторный продукт замен регулярных выражений

Я пытаюсь создать варианты строк, опционально применяя замены.

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

>>> re.sub(r'\s+', '', 'a b c')
'abc'

– Вместо этого мне нужно создать два варианта для каждого вхождения, поскольку замена выполняется в одном варианте, а не в другом. Для строки 'a b c' я хочу иметь варианты

['a b c', 'a bc', 'ab c', 'abc']

т.е. перекрестное произведение всех бинарных решений (результат, очевидно, включает исходную строку).

В этом случае варианты могут быть получены с использованием re.finditer и itertools.product:

def vary(target, pattern, subst):
    occurrences = [m.span() for m in pattern.finditer(target)]
    for path in itertools.product((True, False), repeat=len(occurrences)):
        variant = ''
        anchor = 0
        for (start, end), apply_this in zip(occurrences, path):
            if apply_this:
                variant += target[anchor:start] + subst
                anchor = end
        variant += target[anchor:]
        yield variant

Это дает желаемый результат для приведенного выше примера:

>>> list(vary('a b c', re.compile(r'\s+'), ''))
['abc', 'ab c', 'a bc', 'a b c']

Однако это решение работает только для замены фиксированной строки. Расширенные функции из re.sub, такие как групповые ссылки, не могут быть выполнены таким образом, как в следующем примере для вставки пробела после последовательности цифр внутри слова:

re.sub(r'\B(\d+)\B'), r'\1 ', 'abc123def')

Как можно расширить или изменить подход, чтобы он принимал любой допустимый аргумент в re.sub (без написания синтаксического анализатора для интерпретации групповых ссылок)?


python regex cross-product
person lenz    schedule 06.01.2016    source источник

Ответы (2)


arrow_upward
1
arrow_downward

Мысли о том, чтобы сделать subst вызываемым объектом, который получает доступ к данным сопоставления, наконец, заставили меня узнать о MatchObject.expand. Итак, в качестве приближения, если subst остается строкой r,

def vary(target, pattern, subst):
    matches = [m for m in pattern.finditer(target)]
    occurrences = [m.span() for m in matches]
    for path in itertools.product((True, False), repeat=len(occurrences)):
        variant = ''
        anchor = 0
        for match, (start, end), apply_this in zip(matches, occurrences, path):
            if apply_this:
                variant += target[anchor:start] + match.expand(subst)
                anchor = end
        variant += target[anchor:]
        yield variant

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

person B98    schedule 06.01.2016
comment
Спасибо, это очень хороший совет! Ограничения для вызываемого аргумента можно легко снять, сделав его общим: во внутреннем цикле замените ... + match.expand(subst) на ... + subst(match). Если аргумент не является вызываемым с самого начала, просто оберните его функцией (в начале кода): if not callable(subst): static_subst = subst; subst = lambda m: m.expand(static_subst) - person lenz; 07.01.2016

arrow_upward
1
arrow_downward

Как насчет этого:

def vary(target, pattern, subst):
  numOccurences = len (pattern.findall (target))

  for path in itertools.product((True, False), repeat=numOccurences):

    variant       = ''
    remainingStr = target

    for currentFlag in path:

      if currentFlag: 
        remainingStr = pattern.sub (subst, remainingStr, 1)
      else:
        currentMatch = pattern.search (remainingStr);
        variant += remainingStr[:currentMatch.end ()]
        remainingStr = remainingStr[currentMatch.end ():]

    variant += remainingStr

    yield variant

Для каждого совпадения мы либо позволяем re.sub() выполнять свою работу (со счетчиком 1, чтобы остановить после одной подстановки), либо выхватываем неизмененную часть строки.

Попробуйте это с вашими примерами, как это

target = 'a b c'
pattern = re.compile(r'\s+')
subst = ''

print list (vary(target, pattern, subst))

target = 'abc123def'
pattern = re.compile(r'\B(\d+)\B')
subst = r'\1 '

print list (vary(target, pattern, subst))

я получил

['abc', 'ab c', 'a bc', 'a b c']
['abc123 def', 'abc123def']
person ThorngardSO    schedule 06.01.2016
comment
Спасибо за ваше предложение. Проблема с обрезкой целевой строки перед применением re.sub заключается в том, что в некоторых крайних случаях удаляется необходимый контекст. Например, шаблон r'\B(\d+|[A-Z]+)\B' будет соответствовать 'A' в строке 'abc1Adef', но не в усеченной версии 'Adef'. Я знаю, что выбираю здесь редкие случаи, но это именно те ситуации, которые вызывают трудно отслеживаемые ошибки. - person lenz; 07.01.2016
comment
Да, вы правы - такой подход был слишком наивен, чтобы охватить все неприятные краеугольные случаи... - person ThorngardSO; 07.01.2016