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

Czy ktoś mógłby wyjaśnić te dwa pojęcia w zrozumiały sposób?

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.

„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'.

+-------------------+-----------------+------------------------------+
| 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

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.

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

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

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.

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.

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

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.

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.

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.

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