Die Herausforderung des Backtrackers: gierig, genügsam, possessiv

Am Morgen steckt ein schwarzer Umschlag im Türspalt der Detektei. Darin eine einzige Karte. Die Direktorin hält sie gegen das Licht und legt sie dann auf den Schreibtisch. „Er stellt sich also endlich vor. Mit einer Signatur statt mit einem Gesicht.“

^(a|aa)+$

이 패턴은 정답을 맞힌다. 그런데 왜 이렇게 느린가?
답은 패턴으로 보내라.
                                        (a+)+$

Die Karte ist auf Koreanisch geschrieben: „Dieses Muster liefert die richtige Antwort. Aber warum ist es so langsam? Antworte mit einem Muster.“

„Das kann man nur lösen, wenn man weiß, wie eine Regex-Engine denkt“, sagt die Direktorin. „Heute schauen wir der Engine in den Kopf.“

8-1. Die Engine probiert von vorn und geht zurück, wenn es hakt (10 Min.)

Eine Regex-Engine legt das Muster Stück für Stück von links an den String an. Passt etwas nicht, gibt sie nicht sofort auf, sondern nimmt die letzte Entscheidung zurück und probiert einen anderen Weg. Das nennt man Backtracking.

In Lektion 3 hieß es, Quantoren fressen standardmäßig „so viel wie möglich“ (sie sind gierig). Sehen wir uns an einem Beispiel an, was passiert, wenn man Tags aus HTML herausziehen will.

html = "<b>bold</b> and <i>it</i>"
re.findall(r"<.+>", html)   # ['<b>bold</b> and <i>it</i>']

Statt vier Tags kommt die ganze Zeile als ein einziger Treffer heraus. Verfolgen wir, was die Engine getan hat:

1. < passt auf das erste <.
2. .+ ist gierig und frisst alles bis zum Zeilenende.
3. Jetzt muss das > im Muster passen, aber es ist kein Zeichen mehr übrig. Fehlschlag.
4. .+ gibt die gefressenen Zeichen eins nach dem anderen zurück und versucht es erneut. Sobald es das allerletzte > zurückgegeben hat, klappt es.

Das Ergebnis reicht „vom äußersten < bis zum allerletzten >“. Falsch liegt nicht die Engine, sondern das Muster.

8-2. Genügsame Quantoren: *? +? ?? {m,n}? (8 Min.)

Hängst du an einen Quantor ein ? an, wird er zu einem genügsamen (lazy) Quantor, der so wenig wie möglich frisst. Er nimmt zuerst nur das Minimum und frisst erst dann Zeichen für Zeichen mehr, wenn der Rest des Musters nicht passt.

re.findall(r"<.+?>", html)          # ['<b>', '</b>', '<i>', '</i>']
re.findall(r"a+?", "aaa")           # ['a', 'a', 'a']
re.findall(r"a??", "a")             # ['', 'a', '']
re.search(r"\d{2,4}?", "12345").group()   # '12'

Genügsame Quantoren ändern, „wo die Engine anhält“. Deshalb sind sie praktisch, um Dinge mit einem klaren Endzeichen wie Tags kurz zu fangen.

8-3. Ein Problem, drei Antworten (4 Min.)

Hier die Möglichkeiten, Tags herauszuziehen, nebeneinander:

<[^>]+> nutzt die negierte Klasse aus Lektion 2 und frisst nur „Zeichen, die kein > sind“. Zurückgehen muss es kaum, deshalb ist es am schnellsten und sagt auch am klarsten, was gemeint ist. Die Direktorin bringt es auf den Punkt: „Genauigkeit schlägt Genügsamkeit.“

8-4. Die Antwort auf die Herausforderung: zu viele Wege zurück (8 Min.)

Jetzt zum Muster auf der Karte, ^(a|aa)+$. Es findet „einen ganzen String aus einem oder mehreren a“. Es bedeutet also dasselbe wie ^a+$.

bool(re.fullmatch(r"^(a|aa)+$", "aaaa"))   # True
bool(re.fullmatch(r"^a+$", "aaaa"))        # True

Das Problem zeigt sich bei einem String, der nicht passt. Hängt am Ende ein b, wie in aaaa…ab, probiert die Engine jede Möglichkeit durch, die a in a und aa aufzuteilen, bevor sie den Fehlschlag zugibt. Und die Zahl dieser Aufteilungen explodiert, je mehr a es werden.

Gemessen auf dem Rechner der Detektei (Python 3.14):

Mit jeweils 4 a mehr wird es etwa 7-mal langsamer. Bei gleichem Verhältnis wären es bei 40 a weit über 10 Sekunden. Solche Wiederholungen mit überlappenden Alternativen sind die typische Form, die das Backtracking explodieren lässt. Wiederholungen in Wiederholungen wie (a+)+ gehören zur selben Sorte.

8-5. Quantoren, die nichts zurückgeben: *+ ++ ?+ {m,n}+ (6 Min.)

Seit Python 3.11 wird ein Quantor mit angehängtem + zu einem possessiven Quantor. Was er einmal gefressen hat, gibt er nicht mehr her, auch wenn der Rest scheitert. Damit verschwindet der Weg zurück ganz.

re.fullmatch(r"a*a", "aaa")    # <re.Match object; span=(0, 3), match='aaa'>
re.fullmatch(r"a*+a", "aaa")   # None

a*+a passt auf überhaupt keinen String. a*+ schnappt sich alle a und gibt keins zurück, also bleibt für das a dahinter nichts übrig. Genau diese Eigenschaft hilft aber, das Muster auf der Karte zu reparieren.

re.search(r"^(?:a|aa)++$", "a" * 28 + "b")   # None (sofort fertig)

++ macht die Wiederholung der Gruppe possessiv. Scheitert sie, probiert die Engine keine andere Aufteilung, sondern gibt sofort auf.

8-6. Gruppen, die als Ganzes nichts zurückgeben: (?>...) (4 Min.)

Die atomare Gruppe (atomic group) (?>...) gibt es ebenfalls seit 3.11. Hat der Inhalt der Gruppe einmal gepasst, wird das Ergebnis als Ganzes festgeschrieben, und die Engine kehrt nicht mehr in die Gruppe zurück. Possessive Quantoren sind eigentlich eine Kurzschreibweise für atomare Gruppen: a++ ist dasselbe wie (?>a+).

re.fullmatch(r"(?>a+)b", "aab")   # <re.Match object; span=(0, 3), match='aab'>
re.fullmatch(r"(?>a+)a", "aaa")   # None

Den Fall lösen (10 Min.)

Zusammen mit der Direktorin formulierst du die Antwort. Es gibt drei Wege, ein langsames Muster zu reparieren:

1. Ohne Überlappung neu schreiben. Dafür sorgen, dass sich dieselben Zeichen nicht auf mehrere Arten aufteilen lassen. ^a+$ statt ^(a|aa)+$.
2. Den Weg zurück abschneiden. Der possessive Quantor ^(?:a|aa)++$ oder die atomare Gruppe ^(?>(?:a|aa)+)$.
3. Von außen absichern. Die Eingabelänge begrenzen und fremde Muster nur dort ausführen, wo es ein Zeitlimit gibt. Dass dieses Labor Muster in einem eigenen Prozess ausführt und nach 0,3 Sekunden abbricht, ist genau so eine Sicherung. (Das Drittanbieter-Paket regex hat ein timeout-Argument.)

import time
text = "a" * 40 + "b"
start = time.perf_counter()
print(re.search(r"^a+$", text))             # None
print(time.perf_counter() - start < 0.01)   # True

Du schreibst ^a+$ auf die Rückseite der Karte und steckst sie in den Umschlag. Die Direktorin nickt. „Kurz, lesbar, schnell. Eine gute Antwort.“

Übungen

1. Was liefert re.findall(r'".+"', 'say "hi" and "yo"')? Rate zuerst, dann repariere es auf zwei Arten (genügsamer Quantor, negierte Klasse), sodass jedes Anführungszeichenpaar einzeln gefangen wird.
2. Erkläre, warum (\d+)+$ eine gefährliche Form ist, und schreib ein sicheres Muster mit derselben Bedeutung.
3. Was kommt jeweils heraus, wenn du a{2,4}? und a{2,4}+ mit findall auf "aaaaa" loslässt? Prüf es im Labor.