Что означают «ленивый» и «жадный» в контексте регулярных выражений?

Question

Может ли кто-нибудь объяснить эти два термина понятным образом?

Answer 1

Жадность будет потреблять как можно больше. Из http://www.regular -expressions.info / repeat.html мы видим пример попытки сопоставить теги HTML с <.+>. Предположим, у вас есть следующее:

<em>Hello World</em>

Вы можете подумать, что <.+> (. означает любой не символ новой строки и + означает один или несколько ) будет соответствовать только <em> и </em>, когда на самом деле он будет очень жадным и перейдет от первого < к последнему >. Это означает, что он будет соответствовать <em>Hello World</em> вместо того, что вы хотели.

Лень (<.+?>) предотвратит это. Добавляя ? после +, мы говорим ему повторять как можно меньшее число раз , поэтому первый >, с которым мы сталкиваемся, - это место, где мы хотим остановить сопоставление.

Я бы посоветовал вам загрузить RegExr , отличный инструмент, который поможет вам изучать регулярные выражения - я использую его постоянно.

Answer 2

«Жадный» означает соответствие самой длинной возможной строки.

'Ленивый' означает совпадение самой короткой возможной строки.

Например, жадный h.+l соответствует 'hell' в 'hello', а ленивый h.+?l соответствует 'hel'.

Answer 3

+-------------------+-----------------+------------------------------+
| Greedy quantifier | Lazy quantifier |        Description           |
+-------------------+-----------------+------------------------------+
| *                 | *?              | Star Quantifier: 0 or more   |
| +                 | +?              | Plus Quantifier: 1 or more   |
| ?                 | ??              | Optional Quantifier: 0 or 1  |
| {n}               | {n}?            | Quantifier: exactly n        |
| {n,}              | {n,}?           | Quantifier: n or more        |
| {n,m}             | {n,m}?          | Quantifier: between n and m  |
+-------------------+-----------------+------------------------------+

Добавить? в квантификатор, чтобы сделать его несвязным, т. е. ленивым.

Пример:
тестовая строка: stackoverflow
жадное выражение reg : s.*o вывод: stackoverflo w
выражение ленивых рег : s.*?o вывод: stacko verflow

Answer 4

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

abcdefghijklmc

и это выражение:

a.*c

Жадное совпадение будет соответствовать всей строке, а ленивое совпадение будет соответствовать только первому abc.

Answer 5

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

Как отметил @Andre S в комментарии.

• Жадность: продолжайте поиск, пока условие не будет выполнено.
• Ленивый: прекращать поиск, когда условие выполнено.

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

import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class Test {
    public static void main(String args[]){
        String money = "100000000999";
        String greedyRegex = "100(0*)";
        Pattern pattern = Pattern.compile(greedyRegex);
        Matcher matcher = pattern.matcher(money);
        while(matcher.find()){
            System.out.println("I'm greeedy and I want " + matcher.group() + " dollars. This is the most I can get.");
        }

        String lazyRegex = "100(0*?)";
        pattern = Pattern.compile(lazyRegex);
        matcher = pattern.matcher(money);
        while(matcher.find()){
            System.out.println("I'm too lazy to get so much money, only " + matcher.group() + " dollars is enough for me");
        }
    }
}

---

Результат:

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

Я слишком ленив, чтобы получить столько денег, мне достаточно всего 100 долларов

Answer 6

взято с www.regular-expressions.info

Жадность : Жадные квантификаторы сначала пытаются повторить токен столько раз насколько это возможно, и постепенно отказывается от спичек, как двигатель возвращается назад, чтобы найти общий матч.

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

Answer 7

С Регулярное выражение

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

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

Answer 8

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

Ленивый остановится, как только встретит первый запрошенный вами шаблон.

Один распространенный пример, с которым я часто сталкиваюсь, это \s*-\s*? регулярного выражения ([0-9]{2}\s*-\s*?[0-9]{7})

Первый \s* классифицируется как жадный из-за * и будет искать столько пробелов, сколько возможно, после того, как встретятся цифры, а затем будет искать тире "-". Где, поскольку второй \s*? ленив из-за присутствия *?, что означает, что он будет смотреть первый символ пробела и остановится прямо там.

Answer 9

Лучше всего показывает пример. Строка. 192.168.1.1 и жадное регулярное выражение \ b. + \ B Вы можете подумать, что это даст вам 1-й октет, но на самом деле он совпадает со всей строкой. ЗАЧЕМ!!! Потому что. + Является жадным, и жадное совпадение соответствует каждому символу в '192.168.1.1', пока не достигнет конца строки. Это важный бит !!! Теперь он начинает возвращать по одному символу за раз, пока не найдет соответствие для 3-го токена (\ b).

Если в начале находилась строка с текстовым файлом 4 ГБ и 192.168.1.1, вы могли легко увидеть, как этот откат может вызвать проблему.

Чтобы сделать регулярное выражение не жадным (ленивым), поставьте знак вопроса после своего жадного поиска, например *? ?? +? Что происходит сейчас, токен 2 (+?) Находит совпадение, регулярное выражение перемещается вдоль символа и затем пытается использовать следующий токен (\ b) вместо токена 2 (+?). Так что ползет осторожно.

Answer 10

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

Пример:

import re
text = "<body>Regex Greedy Matching Example </body>"
re.findall('<.*>', text)
#> ['<body>Regex Greedy Matching Example </body>']

Вместо сопоставления до первого вхождения «>» он извлекал всю строку. Это стандартное жадное поведение или поведение regex «возьми все».

Ленивое сопоставление , с другой стороны, «занимает как можно меньше». Это может быть достигнуто путем добавления ? в конце шаблона.

Пример:

re.findall('<.*?>', text)
#> ['<body>', '</body>']

Если вы хотите получить только первое совпадение, используйте вместо этого метод поиска.

re.search('<.*?>', text).group()
#> '<body>'

Источник: Примеры Python Regex