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

Ответы:

644

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

<em>Hello World</em>

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

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

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

Сэмпсон
источник
2
так что если вы используете жадность, у вас будет 3 (1 элемент + 2 тега) совпадения или только 1 совпадение (1 элемент)?
Ajsie
10
Это будет соответствовать только 1 раз, начиная с первого < и заканчивая последним > .
Сампсон
3
Но ленивость будет соответствовать дважды, давая нам открывающий и закрывающий теги, игнорируя текст между ними (так как он не соответствует выражению).
Сампсон
Еще один замечательный инструмент, который я всегда использую: debuggex.com. Он также имеет функцию «Embed on StackOverflow».
Рон ван дер Хейден
8
Просто добавлю, что есть и жадный способ сделать это: <[^>]+> regex101.com/r/lW0cY6/1
alanbuchanan
302

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

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

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

slebetman
источник
97
Отлично, ленивый остановится, как только условие l будет выполнено, но жадность означает, что он остановится только после того, как условие l больше не будет выполнено?
Эндрю С.
3
Для всех людей, читающих пост: жадные или ленивые квантификаторы сами по себе не будут соответствовать самой длинной / самой короткой из возможных подстрок. Вы должны будете использовать либо жадный жетон с умеренным темпом , либо использовать подходы без регулярных выражений.
Виктор Стрибьев
3
@AndrewS Не смущайтесь двойным лл в примере. Это довольно ленивый, будет соответствовать самой короткой из возможных подстрок, а жадный будет соответствовать самой длинной из возможных. Жадные h.+lматчи 'helol'в 'helolo'но ленивые h.+?lматчи 'hel'.
В.Шашенко
3
@FloatingRock: Нет. x?Означает, что xэто необязательно, но +?другой синтаксис. Это значит перестать смотреть после того, как вы найдете что-то подходящее - ленивое соответствие.
slebetman
1
@FloatingRock: Что касается того, как вы различаете синтаксис, то просто: ?означает необязательный и +?означает ленивый. Поэтому \+?средство +необязательно.
slebetman
114
+-------------------+-----------------+------------------------------+
| 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
выражение жадного выражения : s.*ooutput: stackoverflo w
выражение lazy reg : s.*?ooutput: верфи стека

Premraj
источник
2
не является ?? эквивалентно? , Точно так же, не {n}? эквивалентно {n}
Number945
5
@BreakingBenjamin: нет ?? не эквивалентно?, когда у него есть выбор вернуть 0 или 1 вхождение, он выберет альтернативу 0 (ленивый). Чтобы увидеть разницу, сравните re.match('(f)?(.*)', 'food').groups()с re.match('(f)??(.*)', 'food').groups(). В последнем (f)??случае не будет совпадать с лидирующим 'f', хотя это может быть. Следовательно, 'f' будет соответствовать второй группе захвата '. *'. Я уверен, что вы можете создать пример с помощью '{n}?' тоже. По общему признанию, эти два очень редко используются.
СМС
55

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

abcdefghijklmc

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

a.*c

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

Карл Норум
источник
16

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

Как отметил @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");
        }
    }
}


Результат:

I'm greeedy and I want 100000000 dollars. This is the most I can get.

I'm too lazy to get so much money, only 100 dollars is enough for me
Евгений
источник
9

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

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

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

Suganthan Madhavan Pillai
источник
6

Из регулярного выражения

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

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

Адриан Стандер
источник
4

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

Пример:

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 Примеры

Selva
источник
3

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

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

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

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

stackFan
источник
3

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

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

Чтобы сделать регулярное выражение не жадным (ленивым), поставьте знак вопроса после своего жадного поиска, например

*?
??
+?

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

Джейсон Алкок
источник
0

Жадные квантификаторы похожи на IRS / ATO: они берут столько, сколько могут:

Если он там, они придут и возьмут его. Они возьмут все это

Например, IRS совпадает с этим регулярным выражением: .*

$50,000 - IRS возьмет все это. Этот жадный .*{4}?ERS

Смотрите здесь для примера: regexr.com/4t27f

Нежадные квантификаторы - они берут как можно меньше

С другой стороны, если я запрашиваю возврат налога, IRS внезапно становится не жадным, и они используют этот квантификатор:

(.{2}?)([0-9]*)против этого выражения: $50,000первая группа не нуждающаяся и только соответствует $5- так что я получаю $5возмещение. Остальное забрало дядя Сэм, чтобы потратить их впустую.

Смотрите здесь: Non-жадный пример .

Зачем беспокоиться?

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

BKSpurgeon
источник
-3

попытаться понять следующее поведение:

    var input = "0014.2";

Regex r1 = new Regex("\\d+.{0,1}\\d+");
Regex r2 = new Regex("\\d*.{0,1}\\d*");

Console.WriteLine(r1.Match(input).Value); // "0014.2"
Console.WriteLine(r2.Match(input).Value); // "0014.2"

input = " 0014.2";

Console.WriteLine(r1.Match(input).Value); // "0014.2"
Console.WriteLine(r2.Match(input).Value); // " 0014"

input = "  0014.2";

Console.WriteLine(r1.Match(input).Value); // "0014.2"
Console.WriteLine(r2.Match(input).Value); // ""
FrankyHollywood
источник