Co oznaczają „leniwy” i „chciwy” w kontekście wyrażeń regularnych?

Odpowiedzi:

643

Chciwi pochłoną jak najwięcej. Na stronie http://www.regular-expressions.info/repeat.html widzimy przykład próby dopasowania tagów HTML <.+>. Załóżmy, że masz:

<em>Hello World</em>

Możesz myśleć, że <.+>( .środki jakikolwiek zakaz znak nowej linii i +środki jedna lub więcej ) będzie pasować tylko <em>a </em>, podczas gdy w rzeczywistości będzie bardzo chciwy i przejść od pierwszego <do ostatniego >. Oznacza to, że będzie pasować <em>Hello World</em>zamiast tego, co chcesz.

Lazy ( <.+?>) zapobiegnie temu. Dodając ?po +, mówimy, aby powtarzał się tak mało, jak to możliwe , więc po raz pierwszy >pojawia się, gdy chcemy zatrzymać dopasowanie.

Zachęcam do pobrania RegExr , świetnego narzędzia, które pomoże ci odkrywać wyrażenia regularne - używam go cały czas.

Sampson
źródło
2
więc jeśli użyjesz chciwości, będziesz mieć 3 (1 element + 2 tagi) dopasowania, czy tylko 1 mecz (1 element)?
ajsie
10
Pasowałby tylko raz, zaczynając od pierwszego < i kończąc na ostatnim > .
Sampson,
3
Ale uczynienie go leniwym pasowałby dwukrotnie, dając nam zarówno znacznik otwierający, jak i zamykający, ignorując tekst pomiędzy (ponieważ nie pasuje do wyrażenia).
Sampson,
Kolejne świetne narzędzie, którego zawsze używam: debuggex.com Posiada również funkcję „Osadź na StackOverflow”.
Ron van der Heijden
8
Wystarczy dodać, że istnieje również chciwy sposób na <[^>]+> obejście tego
alanbuchanan
301

„Chciwy” oznacza dopasowanie najdłuższego możliwego ciągu.

„Leniwy” oznacza dopasowanie możliwie najkrótszego ciągu.

Na przykład, chciwych h.+lmecze 'hell'w 'hello'ale leniwe h.+?lmecze 'hel'.

Slebetman
źródło
96
Genialne, więc leniwe przestanie, gdy tylko warunek l zostanie spełniony, ale chciwość oznacza, że ​​przestanie, gdy warunek l nie będzie już spełniony?
Andrew S,
3
Dla wszystkich osób czytających post: chciwi lub leniwi kwantyfikatorzy nie będą pasować do najdłuższego / najkrótszego możliwego podciągu. Będziesz musiał użyć temperowanego chciwego tokena lub podejść innych niż wyrażenia regularne.
Wiktor Stribiżew
3
@AndrewS Nie daj się pomylić podwójnemu ll w tym przykładzie. Jest raczej leniwy, że pasuje do najkrótszego możliwego podciągu, podczas gdy zachłanny pasuje do najdłuższego z możliwych. Chciwych h.+lmecze 'helol'w 'helolo'ale leniwe h.+?lmecze 'hel'.
v.shashenko
3
@ FloatingRock: Nie. x?Oznacza, że xjest opcjonalny, ale +?ma inną składnię. Oznacza to, że przestaniesz szukać czegoś, co pasuje - leniwe dopasowanie.
slebetman
1
@ FloatingRock: Jeśli chodzi o różnicowanie składni, proste: ?oznacza opcjonalne i +?oznacza leniwe. Dlatego \+?środki +są opcjonalne.
slebetman
113
+-------------------+-----------------+------------------------------+
| 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  |
+-------------------+-----------------+------------------------------+

Dodać ? do kwantyfikatora, aby uczynić go nierealnym, tj. leniwym.

Przykład:
łańcuch testowy: stackoverflow
greedy reg expression : s.*ooutput: stackoverflo w
lazy reg expression : s.*?ooutput: stacko verflow

Premraj
źródło
2
nie jest ?? równoważny ? . Podobnie nie jest {n}? odpowiednik {n}
Number945
5
@BreakingBenjamin: no ?? nie jest równoważne?, gdy ma możliwość zwrócenia wystąpienia 0 lub 1, wybierze alternatywę 0 (leniwy). Aby zobaczyć różnicę, porównaj re.match('(f)?(.*)', 'food').groups()z re.match('(f)??(.*)', 'food').groups(). W tym drugim (f)??przypadku nie będzie pasować do wiodącego „f”, chociaż może. Dlatego „f” zostanie dopasowane do drugiej grupy przechwytywania „. *”. Jestem pewien, że możesz skonstruować przykład za pomocą „{n}?” też. Trzeba przyznać, że te dwa są bardzo rzadko używane.
smci
55

Chciwy oznacza, że ​​twoje wyrażenie będzie pasować do jak największej grupy, leniwy oznacza, że ​​pasuje do najmniejszej możliwej grupy. Dla tego ciągu:

abcdefghijklmc

i to wyrażenie:

a.*c

Chciwy mecz pasuje do całego ciągu, a leniwy mecz pasuje tylko do pierwszego abc.

Carl Norum
źródło
16

O ile mi wiadomo, większość silników wyrażeń regularnych jest domyślnie zachłanna. Dodaj znak zapytania na końcu kwantyfikatora umożliwi leniwe dopasowanie.

Jak wspomniano w komentarzu @Andre S.

  • Chciwy: szukaj dalej, dopóki warunek nie zostanie spełniony.
  • Leniwy: Zatrzymaj wyszukiwanie, gdy warunek zostanie spełniony.

Poniższy przykład pokazuje, co jest chciwe, a co leniwe.

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");
        }
    }
}


Wynik to:

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
Eugene
źródło
9

Zaczerpnięte z www.regular-expressions.info

Greediness : Greedy kwantyfikatorów próbuje najpierw powtórzyć token tyle razy, ile to możliwe, i stopniowo rezygnuje mecze jako cofa silników znaleźć ogólną mecz.

Lenistwo : Leniwy kwantyfikator najpierw powtarza token tyle razy, ile potrzeba, i stopniowo rozszerza dopasowanie, gdy silnik cofa się przez wyrażenie regularne, aby znaleźć ogólne dopasowanie.

Suganthan Madhavan Pillai
źródło
6

Z wyrażenia regularnego

Standardowe kwantyfikatory w wyrażeniach regularnych są zachłanne, co oznacza, że ​​pasują tak dużo, jak mogą, zwracając tylko tyle, ile jest konieczne, aby dopasować resztę wyrażenia regularnego.

Używając leniwego kwantyfikatora, wyrażenie próbuje najpierw dopasowania minimalnego.

Adriaan Stander
źródło
4

Chciwe dopasowanie. Domyślne zachowanie wyrażeń regularnych jest zachłanne. Oznacza to, że próbuje wyodrębnić jak najwięcej, dopóki nie dopasuje się do wzoru, nawet jeśli mniejsza część byłaby wystarczająca składniowo.

Przykład:

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

Zamiast dopasowywać do pierwszego wystąpienia „>”, wyodrębnił cały ciąg. Jest to domyślne zachowanie wyrażenia chciwego lub „bierz wszystko”.

Z drugiej strony, leniwe dopasowywanie „zajmuje jak najmniej”. Można tego dokonać dodając? na końcu wzoru.

Przykład:

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

Jeśli chcesz pobrać tylko pierwsze dopasowanie, użyj metody wyszukiwania.

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

Źródło: Przykłady Python Regex

Selva
źródło
3

Chciwy oznacza, że ​​pochłonie twój wzór, dopóki nie pozostanie żaden z nich i nie będzie mógł szukać dalej.

Leniwy zatrzyma się, gdy tylko napotka pierwszy żądany wzór.

Jednym z często spotykanych przykładów jest \s*-\s*?regex([0-9]{2}\s*-\s*?[0-9]{7})

Pierwszy \s*jest klasyfikowany jako zachłanny, ponieważ *po napotkaniu cyfr będzie wyglądał jak najwięcej białych znaków, a następnie będzie szukał znaku myślnika „-”. Gdzie jako drugi \s*?jest leniwy z powodu teraźniejszości, *?co oznacza, że ​​będzie wyglądał pierwszy biały znak i zatrzyma się właśnie tam.

stackFan
źródło
3

Najlepiej pokazuje to przykład. Strunowy. 192.168.1.1i zachłanna regex \b.+\b Możesz pomyśleć, że to da ci pierwszy oktet, ale w rzeczywistości pasuje do całego łańcucha. Dlaczego? Ponieważ. + Jest zachłanny, a zachłanne dopasowanie pasuje do każdego znaku, 192.168.1.1dopóki nie osiągnie końca łańcucha. To jest ważny kawałek! Teraz zaczyna cofać się jedna postać na raz, dopóki nie znajdzie dopasowania dla 3. tokena ( \b).

Jeśli na początku był plik tekstowy o wielkości 4 GB i 192.168.1.1, można łatwo zobaczyć, w jaki sposób to cofnięcie spowodowałoby problem.

Aby regex nie był chciwy (leniwy), po wyszukiwaniu chciwego umieść znak zapytania, np

*?
??
+?

To, co się teraz dzieje, to +?znalezienie tokena 2 ( ), wyrażenie regularne przesuwa się wzdłuż znaku, a następnie wypróbowuje następny token ( \b) zamiast tokena 2 ( +?). Więc ostrożnie się skrada.

Jason Alcock
źródło
0

Chciwi kwantyfikatory są jak IRS / ATO: biorą tyle, ile mogą:

Jeśli tam jest, przyjdą i zabiorą go. Zabiorą to wszystko:

Na przykład IRS pasuje do tego wyrażenia regularnego: .*

$50,000 - IRS to wszystko. Ci chciwi .*{4}?ludzie

Zobacz tutaj przykład: regexr.com/4t27f

Nie chciwi kwantyfikatory - zabierają tak mało, jak to możliwe

Z drugiej strony, jeśli poproszę o zwrot podatku, IRS nagle staje się niechciany i używają tego kwantyfikatora:

(.{2}?)([0-9]*)przeciw temu wyrażeniu: $50,000Pierwsza grupa jest niepotrzebna i pasuje tylko $5- więc dostaję$5 zwrot pieniędzy. Resztę zabiera wujek Sam na marnotrawstwo.

Zobacz tutaj: Nie-chciwy przykład .

Po co się męczyć?

Staje się to ważne, jeśli próbujesz dopasować pewne części wyrażenia. Czasami nie chcesz dopasować wszystkiego.

BKSpurgeon
źródło
-3

spróbuj zrozumieć następujące zachowanie:

    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
źródło