wake-up-neo.com

Was bedeutet "faul" und "gierig" im Zusammenhang mit regulären Ausdrücken?

Könnte jemand diese beiden Begriffe verständlich erklären?

447
ajsie

Gierig wird so viel wie möglich verbrauchen. Ab http://www.regular-expressions.info/repeat.html sehen wir das Beispiel für den Versuch, HTML-Tags mit <.+> Abzugleichen. Angenommen, Sie haben Folgendes:

<em>Hello World</em>

Sie können denken, dass <.+> (. Bedeutet jedes Nicht-Zeilenumbruchzeichen und + Bedeutet ein oder mehrere ) würden nur mit dem <em> und dem </em> übereinstimmen, wenn es in Wirklichkeit sehr gierig wäre und gehen vom ersten < bis zum letzten >. Dies bedeutet, dass es mit <em>Hello World</em> Übereinstimmt, anstatt mit dem, was Sie wollten.

Durch Faulenzen (<.+?>) Wird dies verhindert. Indem wir den ? Nach dem + Einfügen, teilen wir ihm mit, dass er so oft wie möglich wiederholt werden soll, also den ersten > Es kommt rüber, wo wir das Matching stoppen wollen.

Ich möchte Sie ermutigen, RegExr herunterzuladen, ein großartiges Tool, mit dem Sie reguläre Ausdrücke erkunden können - ich benutze es die ganze Zeit.

563
Sampson

'Gierig' bedeutet, dass die längste mögliche Zeichenfolge gefunden wird.

'Lazy' bedeutet, dass die kürzestmögliche Zeichenfolge gefunden wird.

Zum Beispiel die gierige h.+l Streichhölzer 'hell' im 'hello' aber die faul h.+?l Streichhölzer 'hel'.

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

Füge hinzu ein ? zu einem Quantifizierer, um es ungreif zu machen, d. h. faul.

Beispiel:
Teststring: Stackoverflow
gieriger reg Ausdruck: s.*o Ausgabe: stackoverflo w
fauler Ausrichtungsausdruck: s.*?o Ausgabe: stacko verflow

89
Premraj

Gierig bedeutet, dass Ihr Ausdruck einer möglichst großen Gruppe entspricht, faul bedeutet, dass er der kleinstmöglichen Gruppe entspricht. Für diese Zeichenfolge:

abcdefghijklmc

und dieser Ausdruck:

a.*c

Eine gierige Übereinstimmung stimmt mit der gesamten Zeichenfolge überein, und eine faule Übereinstimmung stimmt nur mit dem ersten abc überein.

50
Carl Norum

Soweit ich weiß, ist die meiste Regex-Engine standardmäßig gierig. Fügen Sie am Ende des Quantifizierers ein Fragezeichen hinzu, um einen verzögerten Abgleich zu ermöglichen.

Wie @Andre S im Kommentar erwähnt.

  • Gierig: Suchen Sie so lange, bis die Bedingung nicht mehr erfüllt ist.
  • Lazy: Stoppen Sie die Suche, sobald die Bedingung erfüllt ist.

Im folgenden Beispiel erfahren Sie, was gierig und was faul ist.

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

Ich bin greeedy und ich will 100000000 Dollar. Das ist das Beste, was ich bekommen kann.

Ich bin zu faul, um so viel Geld zu bekommen, nur 100 Dollar sind genug für mich

13
Gearon

Entnommen aus www.regular-expressions.info

Gier : Gierige Quantifizierer versuchen zunächst, das Token so oft wie möglich zu wiederholen, und geben Übereinstimmungen nach und nach auf, während die Engine zurückfährt, um eine Gesamtübereinstimmung zu finden.

Faulheit : Der Lazy Quantifier wiederholt das Token zunächst so oft wie erforderlich und erweitert die Übereinstimmung schrittweise, während die Engine den regulären Ausdruck zurückverfolgt, um eine Gesamtübereinstimmung zu finden.

From regulärer Ausdruck

Die Standardquantifikatoren in regulären Ausdrücken sind gierig, das heißt, sie stimmen so gut wie möglich überein und geben nur so viel zurück, wie für den Rest des regulären Ausdrucks erforderlich ist.

Bei Verwendung eines verzögerten Quantifizierers versucht der Ausdruck zuerst die minimale Übereinstimmung.

6
Adriaan Stander

Gierig bedeutet, dass es Ihr Muster verbraucht, bis keines mehr übrig ist und es nicht weiter suchen kann.

Lazy stoppt, sobald es auf das erste von Ihnen angeforderte Muster stößt.

Ein häufig anzutreffendes Beispiel ist \s*-\s*? eines Regex ([0-9]{2}\s*-\s*?[0-9]{7})

Der Erste \s* wird als gierig eingestuft wegen * und suchen so viele Leerzeichen wie möglich, nachdem die Ziffern gefunden wurden, und suchen dann nach einem Bindestrich "-". Wo als zweites \s*? ist faul wegen der Gegenwart von *? was bedeutet, dass es das erste Leerzeichen sieht und genau dort anhält.

3
Girish Pandey

Bestes Beispiel. String. 192.168.1.1 und ein gieriger regulärer Ausdruck\b. +\B Sie könnten denken, dies würde Ihnen das 1. Oktett geben, aber es stimmt tatsächlich mit der gesamten Zeichenfolge überein. WARUM!!! Weil das. + Gierig ist und eine gierige Übereinstimmung mit jedem Zeichen in '192.168.1.1' übereinstimmt, bis es das Ende der Zeichenfolge erreicht. Das ist das Wichtige !!! Jetzt beginnt es, ein Zeichen nach dem anderen zurückzuverfolgen, bis es eine Übereinstimmung mit dem 3. Token (\ b) findet.

Wenn die Zeichenfolge eine 4 GB-Textdatei und 192.168.1.1 am Anfang wäre, könnten Sie leicht sehen, wie dieses Zurückverfolgen ein Problem verursachen würde.

Um eine Regex nicht gierig (faul) zu machen, setzen Sie nach Ihrer gierigen Suche ein Fragezeichen, z. B. *? ?? +? Was jetzt passiert ist, dass Token 2 (+?) Eine Übereinstimmung findet, Regex sich entlang eines Zeichens bewegt und dann das nächste Token (\ b) anstelle von Token 2 (+?) Versucht. Also schleicht es sich behutsam an.

2
Jason Alcock

Gieriger Abgleich Das Standardverhalten von regulären Ausdrücken ist "gierig". Das heißt, es wird versucht, so viel wie möglich zu extrahieren, bis es einem Muster entspricht, auch wenn ein kleinerer Teil syntaktisch ausreichend gewesen wäre.

Beispiel:

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

Anstatt bis zum ersten Auftreten von ">" zu passen, wurde die gesamte Zeichenfolge extrahiert. Dies ist das Standardverhalten von Regex.

Lazy Matching hingegen "benötigt so wenig wie möglich". Dies kann durch Hinzufügen eines ? am Ende des Musters.

Beispiel:

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

Wenn Sie möchten, dass nur die erste Übereinstimmung abgerufen wird, verwenden Sie stattdessen die Suchmethode.

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

Quelle: Python Regex-Beispiele

2
Selva

Wenn jemand hier auf der Suche ist, was beim Parsen schneller ist:

Ein weit verbreitetes Missverständnis über die Leistung regulärer Ausdrücke ist, dass träge Quantifizierer (auch als nicht gierig, widerstrebend, minimal oder nicht gierig bezeichnet) schneller sind als ihre gierigen Entsprechungen. Das ist im Allgemeinen nicht wahr, aber mit einem wichtigen Qualifikator: In der Praxis sind träge Quantifikatoren oft schneller.

Auszug aus Flagrant Badassery

1
User_coder