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

Antworten:

644

Gierig wird so viel wie möglich konsumieren. Unter 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 eines oder mehrere ) nur mit dem <em>und dem übereinstimmen würde </em>, wenn es in Wirklichkeit sehr gierig sein wird, und vom ersten <zum letzten gehen würde >. Dies bedeutet, dass es <em>Hello World</em>anstelle dessen übereinstimmt, was Sie wollten.

Wenn Sie es faul machen ( <.+?>), wird dies verhindert. Durch das Hinzufügen der ?nach dem +, sagen wir , sie zu wiederholen , wie wenig wie möglich , so dass der erste >kommt es über, wo wir die passende stoppen möchten.

Ich möchte Sie dazu ermutigen , RegExr herunterzuladen , ein großartiges Tool, mit dem Sie reguläre Ausdrücke erkunden können - ich verwende es ständig.

Sampson
quelle
2
Also, wenn Sie gierig verwenden, haben Sie 3 (1 Element + 2 Tags) Übereinstimmungen oder nur 1 Übereinstimmung (1 Element)?
Ajsie
10
Es würde nur einmal übereinstimmen, beginnend mit dem ersten < und endend mit dem letzten > .
Sampson
3
Aber es faul zu machen würde zweimal übereinstimmen, uns sowohl das öffnende als auch das schließende Tag geben und den dazwischen liegenden Text ignorieren (da er nicht zum Ausdruck passt).
Sampson
Ein weiteres großartiges Tool, das ich immer benutze: debuggex.com Es hat auch eine Funktion "In StackOverflow einbetten ".
Ron van der Heijden
8
Nur um hinzuzufügen, dass es auch einen gierigen Weg gibt: <[^>]+> regex101.com/r/lW0cY6/1
Alanbuchanan
302

'Gierig' bedeutet Übereinstimmung mit der längsten möglichen Zeichenfolge.

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

Zum Beispiel sind die gierigen h.+lMatches 'hell'in 'hello'aber die faulen h.+?lStreichhölzer 'hel'.

Slebetman
quelle
97
Genial, so faul wird aufhören, sobald die Bedingung l erfüllt ist, aber gierig bedeutet, dass es nur aufhört, wenn die Bedingung l nicht mehr erfüllt ist?
Andrew S
3
Für alle, die den Beitrag lesen: Gierige oder faule Quantifizierer allein passen nicht zum längsten / kürzesten möglichen Teilstring. Sie müssten entweder ein temperiertes gieriges Token oder Nicht-Regex-Ansätze verwenden.
Wiktor Stribiżew
3
@ Andrews Lassen Sie sich nicht durch das Doppel ll im Beispiel verwirren. Es ist ziemlich faul und passt zum kürzestmöglichen Teilstring, während gierig zum längsten möglichen Teil passt. Greedy h.+lMatches 'helol'in 'helolo'aber die faulen h.+?lStreichhölzer 'hel'.
v.shashenko
3
@FloatingRock: Nein x?bedeutet, xist optional, hat aber +?eine andere Syntax. Es bedeutet, dass Sie aufhören müssen, sich um etwas zu kümmern, das passt - Lazy Matching.
Slebetman
1
@FloatingRock: Wie Sie die verschiedenen Syntax unterscheiden, einfach: ?bedeutet optional und +?bedeutet faul. Daher ist \+?Mittel +optional.
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  |
+-------------------+-----------------+------------------------------+

Füge hinzu ein ? zu einem Quantifizierer, um es ungreedy dh faul zu machen.

Beispiel: Testzeichenfolge
: stackoverflow
gieriger reg-Ausdruck : s.*oAusgabe: stackoverflo w
fauler reg-Ausdruck : s.*?oAusgabe: stacko verflow

Premraj
quelle
2
ist nicht ?? gleichwertig ? . Ist {n} auch nicht? entspricht {n}
Number945
5
@ BreakingBenjamin: nein ?? ist nicht gleichbedeutend mit?, wenn es die Wahl hat, entweder 0 oder 1 Vorkommen zurückzugeben, wählt es die 0 (faul) Alternative. Um den Unterschied zu sehen, vergleichen Sie re.match('(f)?(.*)', 'food').groups()mit re.match('(f)??(.*)', 'food').groups(). In letzterem (f)??wird nicht mit dem führenden 'f' übereinstimmen, obwohl es könnte. Daher wird das 'f' von der zweiten '. *' Erfassungsgruppe abgeglichen. Ich bin sicher, Sie können ein Beispiel mit '{n}?' zu. Zugegeben, diese beiden werden sehr selten verwendet.
smci
55

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

abcdefghijklmc

und dieser Ausdruck:

a.*c

Ein gieriges Match passt zur gesamten Saite, und ein faules Match passt nur zum ersten abc.

Carl Norum
quelle
16

Soweit ich weiß, ist die meiste Regex-Engine standardmäßig gierig. Wenn Sie am Ende des Quantifizierers ein Fragezeichen hinzufügen, wird die verzögerte Übereinstimmung aktiviert.

Wie @Andre S im Kommentar erwähnt.

  • Gierig: Suchen Sie weiter, bis die Bedingung nicht erfüllt ist.
  • Faul: 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");
        }
    }
}


Das Ergebnis ist:

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
quelle
9

Entnommen aus www.regular-expressions.info

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

Faulheit : Der Lazy-Quantifizierer wiederholt den Token zuerst so oft wie erforderlich und erweitert die Übereinstimmung schrittweise, während die Engine durch den regulären Ausdruck zurückkehrt, um eine Gesamtübereinstimmung zu finden.

Suganthan Madhavan Pillai
quelle
6

Aus dem regulären Ausdruck

Die Standardquantifizierer in regulären Ausdrücken sind gierig, was bedeutet, dass sie so gut wie möglich übereinstimmen und nur so viel zurückgeben, wie es für den Rest des regulären Ausdrucks erforderlich ist.

Bei Verwendung eines Lazy-Quantifizierers versucht der Ausdruck zuerst die minimale Übereinstimmung.

Adriaan Stander
quelle
4

Gieriges Matching. 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, selbst 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 '>' abzugleichen, wurde die gesamte Zeichenfolge extrahiert. Dies ist das Standardverhalten von Regex.

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

Beispiel:

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

Wenn Sie nur die erste Übereinstimmung abrufen möchten, verwenden Sie stattdessen die Suchmethode.

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

Quelle: Python Regex-Beispiele

Selva
quelle
3

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

Lazy stoppt, sobald das erste von Ihnen angeforderte Muster angezeigt wird.

Ein häufiges Beispiel, dem ich häufig begegne, ist \s*-\s*?eine Regex([0-9]{2}\s*-\s*?[0-9]{7})

Der erste \s*wird als gierig eingestuft *und sieht nach dem Auffinden der Ziffern so viele Leerzeichen wie möglich aus. Suchen Sie dann nach einem Bindestrich "-". Wobei der zweite \s*?faul ist, weil die Gegenwart *?bedeutet, dass er den ersten Leerraum sieht und genau dort anhält.

stackFan
quelle
3

Am besten anhand eines Beispiels. String. 192.168.1.1und eine gierige Regex \b.+\b Sie könnten denken, dies würde Ihnen das 1. Oktett geben, aber es stimmt tatsächlich mit der gesamten Saite überein. Warum? Weil das. + Gierig ist und eine gierige Übereinstimmung jedem Zeichen entspricht, 192.168.1.1bis es das Ende der Zeichenfolge erreicht. Das ist das Wichtige! Jetzt beginnt es, jeweils ein Zeichen zurückzuverfolgen, bis eine Übereinstimmung mit dem 3. Token ( \b) gefunden wird.

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

Um einen Regex nicht gierig (faul) zu machen, setzen Sie nach Ihrer gierigen Suche ein Fragezeichen, z

*?
??
+?

Was jetzt passiert ist, dass Token 2 ( +?) eine Übereinstimmung findet, Regex sich entlang eines Charakters bewegt und dann das nächste Token ( \b) anstelle von Token 2 ( +?) versucht . Also schleicht es vorsichtig dahin.

Jason Alcock
quelle
0

Gierige Quantifizierer sind wie die IRS / ATO: Sie nehmen so viel wie sie können:

Wenn es da ist, werden sie kommen und es nehmen. Sie werden alles nehmen:

Zum Beispiel stimmt der IRS mit diesem regulären Ausdruck überein: .*

$50,000 - IRS wird alles nehmen. Diese gierigen .*{4}?Leute

Ein Beispiel finden Sie hier: regexr.com/4t27f

Nicht gierige Quantifizierer - sie nehmen so wenig wie möglich

Wenn ich dagegen eine Steuerrückerstattung beantrage, wird der IRS plötzlich nicht mehr gierig und sie verwenden diesen Quantifizierer:

(.{2}?)([0-9]*)gegen diesen Ausdruck: $50,000Die erste Gruppe ist nicht bedürftig und passt nur zusammen $5- also bekomme ich eine $5Rückerstattung. Der Rest wird von Onkel Sam für verschwenderisch ausgegeben.

Siehe hier: Nicht gieriges Beispiel .

Warum die Mühe?

Es wird wichtig, wenn Sie versuchen, bestimmte Teile eines Ausdrucks abzugleichen. Manchmal möchte man nicht alles zusammenbringen.

BKSpurgeon
quelle
-3

Versuchen Sie, das folgende Verhalten zu verstehen:

    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
quelle