Python Regex не жадный матч

Question

Этот вопрос из книги "Автоматизируйте скучные вещи с помощью Python".

 atRegex1 = re.compile(r'\w{1,2}at')
 atRegex2 = re.compile(r'\w{1,2}?at')

 atRegex1.findall('The cat in the hat sat on the flat mat.')
 atRegex2.findall('The cat in the hat sat on the flat mat.')

я думал вопрос рынка? следует проводить не жадное совпадение, так что \ w {1,2}? должен возвращать только 1 символ. Но для обеих этих функций я получаю одинаковый вывод:

['cat', 'hat', 'sat', 'flat', 'mat']

В книге

nongreedyHaRegex = re.compile(r'(Ha){3,5}?')
mo2 = nongreedyHaRegex.search('HaHaHaHaHa')
mo2.group()
'HaHaHa'

Кто-нибудь может помочь мне понять, почему есть разница? Спасибо!

Answer 1

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

Ключевое слово здесь backtracks . Я думаю, документация Microsoft отлично справляется с определением этого термина (я выделил важный раздел):

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

Движок регулярных выражений возвращает в предыдущее сохраненное состояние . Он не может переместить трек в сохраненное в будущем состояние , хотя это было бы довольно аккуратно! Поскольку вы указали, что ваше совпадение должно заканчиваться at (ленивый квантификатор предшествует ему), оно будет исчерпывать каждую опцию регулярного выражения, пока \w{1,2}, заканчивающийся at, не подтвердится.

Как вы можете обойти это? Ну, возможно, самый простой способ - использовать группу захвата:

Смотрите здесь регулярное выражение

\w*(\w{1,2}?at)
\w*(\w{1,2}at)    # yields same results as above (but in more steps)
\w*(\wat)         # yields same results as above (faster method)
\wat              # yields same results as above (fastest method)
\b\w{1,2}at\b     # perhaps this is what OP is after?

• \w* Соответствует любому символу слова любое количество раз. Это исправление, позволяющее нам моделировать прямое отслеживание (это неправильный термин, он используется в контексте остальной части моего ответа выше). Он будет соответствовать как можно большему количеству символов и будет работать в обратном направлении, пока не будет найдено совпадение.
• Остальная часть шаблона уже была у ОП. Фактически, \w{2} никогда не будет выполнено, поскольку \w будет всегда встречаться только один раз (поскольку жетон \w* является жадным), поэтому вместо него \w*(\wat) можно использовать \wat. Возможно, OP намеревался использовать такие якоря, как \b в регулярном выражении: \b\w{1,2}at\b? Это также не отличается от первоначальной природы регулярного выражения OP, так как из-за ленивости квантификатора теоретически дает те же результаты в контексте отслеживания вперед (одно совпадение * 1056) * удовлетворил бы \w{1,2}?, поэтому \w{2} никогда бы не был достигнут).

Answer 2

Второму регулярному выражению соответствует известный шаблон: Ha минимум 3 раза и максимум 5, но как можно меньше. Так что в этом случае он никогда не выходит за пределы 3, так же, как (Ha){3}. Двигатель доволен как можно скорее.

(Ha){3,5}? совпадает с приведенным ниже (рассмотрим группы как одну):

(Ha){3}|(Ha){4}|(Ha){5}

и (Ha){3,5} совпадают с:

(Ha){5}|(Ha){4}|(Ha){3}

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

А как насчет \w{1,2}?at? Давайте переведем это:

(?:\w{1}|\w{2})at

Первая сторона чередования имеет приоритет - когда найден соответствующий процесс. Это верно и для \w{1,2}at:

(?:\w{2}|\w{1})at

Примечание: если первая сторона не совпадает, двигатель работает с другими сторонами в порядке.