Что означают "ленивый" и "жадный" в контексте регулярных выражений?
Может ли кто-нибудь объяснить эти два термина понятным способом?
13 ответов
Жадный будет потреблять как можно больше. Из http://www.regular-expressions.info/repeat.html мы видим пример попытки сопоставить теги HTML с <.+>, Предположим, у вас есть следующее:
<em>Hello World</em>
Вы можете думать, что <.+> (. означает любой не символ новой строки и + означает один или несколько) будет соответствовать только <em> и </em>, когда на самом деле он будет очень жадным, и пойдет с первого раза < до конца >, Это означает, что это будет соответствовать <em>Hello World</em> вместо того, что вы хотели.
Делать это ленивым (<.+?>) предотвратит это. Добавляя ? после +, мы говорим, чтобы повторить как можно меньше раз, поэтому первый > это сталкивается, где мы хотим остановить сопоставление.
Я рекомендую вам скачать RegExr, отличный инструмент, который поможет вам изучить регулярные выражения - я использую его постоянно.
"Жадность" означает соответствие самой длинной строки.
"Ленивый" означает соответствие самой короткой возможной строки.
Например, жадный h.+l Матчи 'hell' в 'hello' но ленивый h.+?l Матчи 'hel',
+-------------------+-----------------+------------------------------+
| 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 |
+-------------------+-----------------+------------------------------+
Добавить? в квантификатор, чтобы сделать его несвязным, т.е. ленивым.
Пример:
тестовая строка: stackru
жадное выражение: s.*o вывод: stackoverflo w
ленивый рег выражение: s.*?o вывод: верстак стека
Жадный означает, что ваше выражение будет соответствовать как можно большей группе, ленивый означает, что оно будет соответствовать наименьшей возможной группе. Для этой строки:
abcdefghijklmc
и это выражение:
a.*c
Жадное совпадение будет соответствовать всей строке, а ленивое совпадение - только первой abc,
Насколько я знаю, большинство движков регулярных выражений по умолчанию жадные. Добавление знака вопроса в конце квантификатора позволит включить ленивое совпадение.
Как отметил @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 долларов
Взято с http://www.regular-expressions.info/possessive.html
Жадность: Жадные квантификаторы сначала пытаются повторить токен столько раз, сколько это возможно, и постепенно отказываются от совпадений, когда двигатель возвращается, чтобы найти общее совпадение.
Ленивость: Ленивый квантификатор сначала повторяет токен столько раз, сколько требуется, и постепенно расширяет совпадение, когда двигатель возвращается через регулярное выражение, чтобы найти общее совпадение.
Стандартные квантификаторы в регулярных выражениях являются жадными, что означает, что они совпадают настолько, насколько они могут, и возвращают только по мере необходимости, чтобы соответствовать остатку регулярного выражения.
Используя ленивый квантификатор, выражение сначала пробует минимальное совпадение.
Жадное совпадение. Поведение регулярных выражений по умолчанию должно быть жадным. Это означает, что он пытается извлечь как можно больше, пока не будет соответствовать шаблону, даже если меньшая часть была бы синтаксически достаточной.
Пример:
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 Примеры
Жадные квантификаторы похожи на IRS/ATO
Если оно там есть, они все заберут.
IRS соответствует этому регулярному выражению: .*
$50,000
Это будет соответствовать всему!
См. Пример здесь: Жадный пример
Нежадные квантификаторы - они берут как можно меньше
Если я прошу возврат налога, IRS внезапно перестает жадничать и использует этот количественный показатель:
(.{2,5}?)([0-9]*) против этого ввода: $50,000
Первая группа не является нуждающейся и соответствует только $5 â € “так что я получаю $5возмещение в размере 50000 долларов США. Они не жадные. Берут как можно меньше.
См. Здесь: Нежадный пример.
Зачем беспокоиться?
Это становится важным, если вы пытаетесь сопоставить определенные части выражения. Иногда не хочется сочетать все.
Надеюсь, эта аналогия поможет вам вспомнить!
Лучше всего показывает пример. Строка. 192.168.1.1 и жадное регулярное выражение \b.+\ B Вы можете подумать, что это даст вам 1-й октет, но на самом деле совпадает со всей строкой. ЗАЧЕМ!!! Потому что. + Является жадным, и жадное совпадение соответствует каждому символу в '192.168.1.1', пока не достигнет конца строки. Это важный бит!!! Теперь он начинает возвращать по одному символу за раз, пока не найдет совпадение для 3-го токена (\b).
Если в начале строки был текстовый файл объемом 4 ГБ и 192.168.1.1, вы могли легко увидеть, как этот откат может вызвать проблему.
Чтобы сделать регулярное выражение не жадным (ленивым), поставьте знак вопроса после своего жадного поиска, например *??? +? Что происходит сейчас - токен 2 (+?) Находит совпадение, регулярное выражение перемещается вдоль символа и затем пытается использовать следующий токен (\ b) вместо токена 2 (+?). Так что ползет осторожно.
Жадность означает, что она будет поглощать ваш паттерн до тех пор, пока не останется ни одного из них, и она не сможет смотреть дальше.
Ленивый остановится, как только встретит первый шаблон, который вы запросили.
Один общий пример, с которым я часто сталкиваюсь, \s*-\s*? регулярного выражения ([0-9]{2}\s*-\s*?[0-9]{7})
Первый \s* классифицируется как жадный из-за * и после того, как встретятся цифры, будет искать как можно больше пробелов, а затем искать символ тире "-". Где второй \s*? ленивый из-за настоящего *? Это означает, что он будет выглядеть первым пробелом и остановится прямо там.
Чтобы дать дополнительное разъяснение по поводу лени, вот один пример, который, возможно, не интуитивно понятен на первый взгляд, но объясняет идею «постепенного расширения соответствия» из ответа Сугантана Мадхавана Пиллаи.
input -> some.email@domain.com@
regex -> ^.*?@$
Регулярное выражение для этого ввода будет иметь совпадение. На первый взгляд кто-то может сказать, что LAZY match(".* [email protected] ") сначала остановится на @, после чего проверит, заканчивается ли входная строка("$"). Следуя этой логике, кто-то мог бы сделать вывод, что совпадений нет, потому что входная строка не заканчивается после первого символа @.
Но, как вы можете видеть, это не так, регулярное выражение будет продолжаться, даже если мы используем нежадный (ленивый режим) поиск, пока он не наткнется на второй @ и не получит МИНИМАЛЬНОЕ совпадение.
Попытаться понять следующее поведение:
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); // ""