Gierige Regex und wo sie zu finden sind
Pythons Standard-Rgex-Library kennt greedy (gierige) und nicht-gierige reguläre Ausdrücke.
Dieser Artikel soll kurz darstellen unter welchen Umständen es dadurch zu Problemen kommen kann und wie man sie vermeidet.
Häufig ist einem gar nicht bewusst ob man einen gierigen oder nicht-gierigen regulären Ausdruck verwendet…
Man möchte zum Beispiel vereinfachtes HTML prfüen, sowas hier:
<a>Link-Text</a><b>Peter der Große</b>Eine einfache Überprüfung ob in der Zeile ein HTML-Element ist, könnte dann so aussehen:
import re
if re.match("<.+>.*<\/.+>", "<a>Link-Text</a><b>Peter der Große</b>"):
print("Ist ein Tag")Das würde "Ist ein Tag" zurückgeben, weil der Ausdruck match.
Zur Follständigkeit die Bestandteile:
* "." → ein beliebiges Zeichen
* "" -> das vorhergehende Zeichen mindestens einmal, bis beliebig oft -> . → ein beliebiges Zeichen, mindestens einmal, bis zu beliebig oft
* "" → das vorhergehende Zeichen beliebig oft (inkl. gar nicht) → . → ein beliebiges Zeichen, beliebig oft (inkl. gar nicht)
import re
result = re.match("<.+>.*<\/.+>", "<a>Link-Text</a><b>Peter der Große</b>"):
print(result.group())
'<a>Link-Text</a><b>Peter der Große</b>'Wie man sieht wird also nicht etwa - wie man erwarten könnte - <a>Link-Test</a> gematcht, also jeweils nur ein Element gematcht, sondern in diesem Fall der gesamte String.
Häufig nutzt man in Python regular-Expressions ganz selbstverständlich ".*" oder "a+" und meistens führt es auch zum erwünschten Ergebnis.
Aber manchmal ist es zum Haare raufen, da wird dann plötzlich viel mehr erfasst als man eigentlich wollte.
Definition
Pythons re (regular-Expression)-Bibliothek kennt greedy (gierige) und lazy (faule) und possessive (besitzergreifende) Quantifizierer (Mengenangaben).
Das betrifft die folgenden Quantifier:
-
* → das vorhergehende Zeichen beliebig oft (inkl. 0 mal)
-
+ → das vorhergehende Zeichen mind. 1 mal, ansonsten beliebig oft
-
? → das vorhergehende Zeichen ein oder kein-mal
Es gibt noch mehr, aber von der Regel sind nur die oben stehenden betroffen.
Die einfache Form - also zum Beispiel * - ist greedy/gierig, das heißt es wird versucht ein möglichst lange zusammenhängende Zeichenkette zu erfassen die dem Ausdruck entspricht.
Die Form mit ? am Ende - also zum Beispiel *? oder ?? - ist lazy/faul, das heiß sie wird sich mit der kürzesten Zeichenkette zufrieden geben die dem Ausdruck entspricht.
Die Form mit + am Ende - also zum Beispiel *+ oder ++ - ist possessive/besitzergreifend, das ist eine Spezialform von greedy, bei der kein Backtracking zum Einsatz kommt.
Diese ist erst mit Python 3.11 verfügbar.
Erläuterung
Vorweg
In den Beispielen wird die Funktion re.findall verwendet.
Diese durchläuft die Zeichenkette mit dem regulären Ausdruck, matcht ein Teil der Zeichenkette wird dieser Teil zur Ergebnisliste hinzugefügt, anschließend dahinter nach weiteren matches gesucht.
Man bekommt also eine Liste aller Vorkommen des regulären Ausdrucks in der Zeichenkette.
Greedy/Gierig
import re
result = re.findall('.*,', "Eins,Zwei,Drei")
print(result)
["Eins,Zwei,Drei"]Das Ergebnis ist also ["Eins,Zwei,"], also nur ein Eintrag in der Liste.
"Drei" ist nicht in der Liste, weil hinter "Drei" kein "," kommt.
Aber "Eins" und "Zwei" sollten doch getrennte Einträge sein, oder?
Woran liegt das?
Schauen wir uns den regulären Ausdruck an und was damit passiert wenn er auf die Zeichenkette angewendet wird.
-
. → ein beliebiges Zeichen
-
* → beliebig oft → also zwischen 0 und X mal - gierig/greedy
-
, → Komma, so wie es da steht Es wird also nach einer Zeichenkette gesucht die beliebige Zeichen beinhalten kann (aber auch keine Zeichen haben darf) und mit einem "," endet.
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
E |
i |
n |
s |
, |
Z |
w |
e |
i |
, |
D |
r |
e |
i |
Der Algorithmus führt zuerst .* aus, also prüft er jedes Zeichen darauf ob es einem beliebigen Zeichen (".") entspricht und das tut er beliebig oft (*) - letztendlich bis zum Ende der Zeichenkette, da ja jedes Zeichen ein beliebiges Zeichen ist.
Das Auftreten des ersten passenden Zeichens setzt den Start-Index der Gruppe - hier also 0
Das letzte Auftreten eines passenden Zeichens setzt den End-Index der Gruppe - hier also 13
Anschließend wird nach "," gesucht, da sich nach dem bisherigen Ende der Gruppe (Index 13) keins finden lässt (da sie bis zum Ende der Zeichenkette reicht), wird sogenanntes Backtracking gemacht, die bisher gefundene Gruppe wird rückwärts durchlaufen auf der Suche nach ",".
"," befindet sich von hinten an Position 9, das neue Ende der Gruppe wird also auf 9 gesetzt - die Gruppe und damit das Ergebnis geht von 0-9 aka. "Eins,Zwei,"
Lazy/ Faul
import re
result = re.findall('.*?,', "Eins,Zwei,Drei")
print(result)
["Eins,Zwei"]Das Ergebnis ist also ["Eins", "Zwei,"], also 2 separate Einträge/Funde. "Drei" ist nicht in der Liste, weil hinter "Drei" kein "," kommt.
Der Unterschied zur greedy-Version ist das "?" hinter dem Quantifier → "*?"
Schauen wir uns den regulären Ausdruck an und was damit passiert wenn er auf die Zeichenkette angewendet wird.
-
. → ein beliebiges Zeichen
-
*? → beliebig oft → also zwischen 0 und X mal - lazy/faul
-
, → Komma, so wie es da steht Es wird also nach einer Zeichenkette gesucht die beliebige Zeichen beinhalten kann und die mit dem ersten auftreten eines "," endet.
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
E |
i |
n |
s |
, |
Z |
w |
e |
i |
, |
D |
r |
e |
i |
Im folgenden der Algorithmus wie er vom Prinzip funktioniert, die echte Implementierung kann davon abweichend sein.
Ein Zeichen wird eingelesen und darauf geprüft ob es ein beliebiges Zeichen ist (.), anschließend wird sofort geprüft ob es sich um ein "," handelt.
Handelt es sich um ein "," wird die Position als End-Index für die Match-Gruppe gesetzt. Gibt es eine Start-Position für die Gruppe ist die Gruppe hier abgeschlossen, ansonsten wird die Endposition verworfen.
Handelt es sich nicht um ein "," wird die Position als Start-Index gesetzt → es handelt sich nicht um das Ende eines regulären Ausdrucks, aber um ein beliebiges Zeichen.
Der Vorgang wird wiederholt bis das Ende der Zeichenkette erreicht ist.
Der Unterschied zwischen lazy und greedy ist, dass bei lazy das erste Auftreten eines Zeichens im regulären Ausdruck nach dem lazy-Quantifier (hier ",") die Gruppe beendet - es wird jedes eingelesene Zeichen auf dieses Zeichen/Ausdruck hin geprüft.
Beim greedy-Vorgehen hingegen wird der greedy-Ausdruck so lange wiederholt angewendet wie die dadurch definierte Bedingung erfüllt ist, erst wenn die Bedingung nicht mehr erfüllt ist oder die zu untersuchende Zeichenkette aufgebraucht ist, wird das darauffolgende Zeichen in der Zeichenkette gegen das Zeichen/Ausdruck nach dem greedy-Quantifier geprüft. Matcht das dann nicht, wird der bis dahin durch den greedy-Ausdruck ermittelte String rückwärts durchforstet um darin das darauffolgende Zeichen zu finden. Wird es nicht gefunden trifft der reguläre Ausdruck nicht zu, wird es gefunden, wird der aufgezeichnete String bis zum ersten Auftreten des Zeichens (von hinten) gekürzt.
Man könnte auch sagen, dass im Falle von lazy-Quantifiers das Zeichen nach dem Quantifier vorwärts (look-ahead) gesucht wird, während bei greedy-Quantifiers das Zeichen nach dem Quantifier rückwirkend (look-back) gesucht wird.
Warum es meist kein Problem ist
In den meisten Fällen will man eigentlich keinen greedy-Quantifier benutzen, obwohl es die kürzeste Version ist und wohl auch die die einem am ehesten geläufig ist.
Es ist also sinnvoll immer standardmäßig erstmal die "?"-Variante zu benutzen und die ohne eher in Ausnahmefällen.
Witzigerweise hat man meist troztdem kein Problem, obwohl man (unbewusst) die greedy-Variante benutzt - woran liegt das?
import re
if re.match("<.*>", '<a href="whaterver.de">Das ist <b>fett</b></a>')
print("Tag gefunden")In obigem Fall soll geprüft werden ob in der Zeichenkette ein (beliebiger) Tag vorkommt und dann eine Aktion ausgeführt werden.
Praktisch matcht hier die gesamte Zeichenkette "<a href="whaterver.de">Das ist <b>fett</b></a>" - weil der Ausdruck (.*) greedy ist - statt einfach nur das erste Tag '<a href="whaterver.de">'.
Es hat aber keine Auswirkung, da es egal ob ein Tag oder 500 vorhanden sind, immer True zurückliefert, nur die Länge des gematchten Strings ändert sich, da hier aber nur True oder False relevant sind hat das keine Auswirkung.
import re
result = re.search(".*"', '<a href="whaterver.de">Das ist <b>fett</b></a>')
print(result.group())
"whaterver.de"In obigem Beispiel wird nach '"."' gesucht, das heißt etwas soll mit " beginnen, dann wird greedy alles bis zum letzten Auftreten eines " eingesammelt.
Da " nur 2 mal, einmal als Beginn und einmal als Ende vorkommt, gibt es hier kein "Über"-Matching und das ganze funktioniert genauso als hätte man .? geschrieben.
Das Ergebnis hier wäre "whatever.de" .