«Жадный» и «ленивый» поиск по регулярным выражениям: почему ваш шаблон охватывает слишком много

Вы пишете <b>.*</b>, чтобы извлечь содержимое тега жирного шрифта, проверяете это на <b>Hello</b> — всё работает отлично. Затем вы запускаете его на реальном HTML-коде с двумя тегами жирного шрифта в одной строке — <b>Hello</b> and <b>World</b> — и вместо двух совпадений получаете одно гигантское совпадение, охватывающее оба тега. Это не ошибка вашего движка регулярных выражений; это стандартное поведение *, + и {n,m}, и исправить это можно одним символом, как только вы поймёте, что происходит.

Почему .* захватывает больше, чем вы ожидаете

По умолчанию квантификаторы в регулярных выражениях являются жадными — .* не означает «найти несколько символов», а означает «найти как можно больше символов, а затем отступить только в том случае, если остальная часть шаблона этого абсолютно требует».

Рассмотрим пошагово, как <b>.*</b> сопоставляется с <b>Hello</b> and <b>World</b>:

1. <b> сопоставляется с первым <b>.
2. .* начинает с потребления всей оставшейся части строки — всего до конца, включая второй <b>World</b>.
3. Затем движок должен найти </b>, чтобы завершить сопоставление, поэтому он начинает отступать от конца .* по одному символу за раз.
4. Первым местом (при сканировании в обратном направлении от конца), где помещается </b>, является самый последний </b> в строке — а не тот, на котором он «логически» должен был бы остановиться.

Таким образом, в результате сопоставление охватывает всю строку <b>Hello</b> and <b>World</b>, поскольку жадное сопоставление всегда сначала пробует найти максимально длинную строку и сокращает её лишь настолько, насколько это необходимо для успешного сопоставления остальной части шаблона.

Исправление: сделать квантификатор ленивым с помощью ?

Добавление ? сразу после квантификатора превращает его из жадного в ленивый (также называемый «нежадным» или «нерешительным»): *?, +?, ??, {n,m}?.

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

<b>.*?</b> при сопоставлении с той же строкой:

1. <b> сопоставляется с первым <b>.
2. .*? сначала сопоставляется с нулем символов.
3. Механизм проверяет: подходит ли </b> именно здесь? Нет (мы находимся в «Hello…», ещё не дошли до </b>) — поэтому он расширяет .*? ровно на один символ и проверяет снова.
4. Это повторяется символ за символом, пока .*? не «поглотит» ровно Hello, после чего </b> соответствует сразу же.

Результат: <b>Hello</b> и <b>World</b> возвращаются как два отдельных совпадения, что почти всегда и является тем, что вам на самом деле нужно при разборе структур, похожих на теги или разделители.

Когда действительно нужен жадный алгоритм (это не просто «неправильное значение по умолчанию»)

Жадный алгоритм — это не ошибка языка; он правилен для другого, столь же распространённого случая: сопоставления самой внешней границы чего-либо, а не самой маленькой единицы внутри неё. Если вы извлекаете «всё, что находится между первым { и последним } » в массиве текста, похожем на JSON (например, чтобы извлечь весь объект независимо от вложенности), жадный подход будет как раз правильным, а ленивый остановится на первом внутреннем }, в результате чего вы получите усечённый, неверный фрагмент.

Практическое правило: lazy — для повторяющихся небольших отдельных фрагментов (теги, строки в кавычках, элементы списка); greedy — для «извлечения всего внешнего диапазона».

Краткое руководство

Шаблон	Поведение	Использовать, когда
.*, .+, {n,m}	«Жадный» — находит максимально длинный вариант	Вам нужен самый внешний диапазон, или в строке есть только одно совпадение
.*?, .+?, {n,m}?	Ленивый — находит кратчайший возможный	У вас есть несколько похожих фрагментов, разделённых разделителями, и вы хотите выделить каждый из них отдельно

Если вы не уверены, какой из этих подходов на самом деле использует шаблон при обработке реального ввода (а не тестовой строки), запустите его на тексте с несколькими совпадениями в тестере регулярных выражений с подсветкой результатов поиска, разница станет сразу заметна — при жадном поиске вы увидите один огромный выделенный блок, а при ленивом — несколько отдельных, что обычно быстрее, чем анализировать всё символ за символом.