Ein ernüchterndes Beispiel

(Auszug aus "Reguläre Ausdrücke" von Jeffrey E. F. Friedl)

Wir beginnen mit einem Beispiel, das drastisch vor Augen führt, wie wichtig Überlegungen zu Effizienz und Backtracking sein können. Unter Geschützte Anführungszeichen in Strings in Anführungszeichen zulassen hatten wir den Ausdruck ˹"(\\.|[^\\"])*"˼ entwickelt, um Text innerhalb von Anführungszeichen zu finden, in dem geschützte Anführungszeichen zugelassen sind. Diese Regex funktioniert. Wenn sie aber mit einem NFA benutzt wird, ist die Alternation, die auf jedes Zeichen angewendet wird, sehr ineffizient. Bei jedem »normalen« Zeichen im String (also bei allen Zeichen außer dem Backslash und Anführungszeichen) muss die Maschine auf ˹\\.˼ testen, was nicht passt. Dann muss sie mittels Backtracking zurückgehen und mit ˹[^\\"]˼ einen lokalen Treffer finden. Wenn bei einer Anwendung die Geschwindigkeit eine Rolle spielt, wäre es sehr angenehm, wenn wir diese Regex schneller machen könnten.

Eine einfache Änderung – die Schokoladenseite zuerst

Weil Strings in Anführungszeichen im Durchschnitt wohl mehr normale als mit Backslash geschützte Zeichen haben, ist das Vertauschen der zwei Alternativen naheliegend: zuerst auf ˹[^\\"]˼ testen und dann erst auf ˹\\..˼ Dadurch wird das Backtracking nur dann gebraucht, wenn wirklich ein durch einen Backslash geschütztes Zeichen auftritt (und zudem, wenn beide Alternativen nicht passen; damit die Alternation als Ganzes fehlschlägt, müssen natürlich alle Alternativen ausprobiert werden). In der folgenden Abbildung ist das grafisch dargestellt. Die geringere Anzahl der Pfeile im unteren Teil entspricht der größeren Anzahl von lokalen Treffern der nunmehr ersten Alternative, anders gesagt: weniger Backtracking.

Abbildung: Die Auswirkungen der unterschiedlichen Reihenfolge (traditioneller NFA).

Bei einer derartigen Änderung sollte man sich zwei Fragen stellen:

• Beeinflusst die Änderung nur traditionelle NFAs, nur POSIX-NFAs oder beide?
• Bringt die Änderung etwas, wenn ein Treffer gefunden wird oder wenn keiner gefunden wird oder in beiden Fällen?

Bitte überlegen Sie sich das genau und versuchen Sie, Lösung 13 zu verstehen, bevor Sie weiterlesen.

Effizient oder korrekt?

Wenn man einen regulären Ausdruck verändert, um ihn effizienter zu machen, muss man natürlich überprüfen, ob die Regex noch korrekt ist. Alternativen darf man nur dann anders anordnen, wenn die Reihenfolge unerheblich ist. Im letzten Abschnitt hatten wir ein Problem mit der inkorrekten Regex ˹"(\\.|[^"])*"˼ (siehe unter Geschützte Anführungszeichen in Strings in Anführungszeichen zulassen). Die negierte Zeichenklasse enthält keinen Backslash und passt deshalb auf Zeichen, die ihr nicht zugedacht sind. Wenn die Regex nur mit Daten getestet wird, die Treffer ergeben, wird man das Problem gar nicht entdecken. Wenn wir die Alternativen vertauschen, weil wir uns dadurch eine effizientere Regex erhoffen, bekommen wir erst recht Probleme. Wenn ˹[^"]˼ die erste Alternative ist, wird bei jedem String mit einem geschützten Anführungszeichen ein Fehltreffer gefunden:

"Ein 3/4\"-Gewinde."

Es ist also wichtig, sich zuerst um die Richtigkeit einer Regex zu kümmern und erst dann um die Effizienz.

Gieriges Verhalten nur lokal zulassen

In der obigen Abbildung wird klar, dass der Stern bei allen angegebenen Beispielen eine Iteration erzeugt. Die Maschine muss bei jedem zu prüfenden Zeichen einen Zyklus, einen Iterationsschritt, ausführen. Dabei wird jedes Mal die Alternation und damit die Klammer »betreten« und wieder verlassen. Damit ist viel Arbeit verbunden, die wir nach Möglichkeit eliminieren wollen.

Bei einem ähnlichen Ausdruck hatte ich einmal entdeckt, dass man die Regex optimieren kann, wenn klar ist, dass ˹[^\\"]˼ der Normalfall ist (weder Backslash noch Anführungszeichen). Mit ˹[^\\"]+˼ werden in einem Iterationsschritt so viele »normale« Zeichen wie möglich gelesen, ohne dass die Klammer verlassen wird. Bei Texten ohne geschützte Zeichen ist das gleich der ganze String. Damit kann fast ohne Backtracking ein Treffer gefunden werden, und die durch den Stern erzeugten Iterationen fallen weg. Ich war sehr zufrieden mit mir.

Wir behandeln dieses Beispiel später genauer. Im Moment sind wir nur an der Statistik interessiert. Die nächste Abbildung zeigt, dass durch die neue Änderung im Falle von ˹"(\\.|[^\\"])*"˼ (das obere Paar in der Abbildung) weniger durch den Stern erzeugte Iterationen und weniger Backtrackings benötigt werden. Das untere Paar in der dieser Abbildung zeigt, dass der Gewinn mit beiden Änderungen noch größer ausfällt.

Abbildung: Auswirkungen eines zusätzlichen Pluszeichens (traditioneller NFA).

Der entscheidende Effekt ergab sich beim Hinzufügen des Pluszeichens. So reduziert sich die Anzahl der benötigten Backtrackings und damit die Anzahl der durch den Stern hervorgerufenen Zyklen. Der Stern quantifiziert einen geklammerten Unterausdruck, und damit erzeugt jede Iteration eine Menge Arbeit für die Maschine: Nicht nur die Position im String und in der Regex muss gespeichert werden, sondern auch die Länge des von den Klammern eingefassten Texts. (Genauer wird das später in diesem Kapitel behandelt.)

Folgende Tabelle ähnelt der Tabelle aus Lösung 13. Sie enthält zwar weniger Testbeispiele, dafür wird aber die Anzahl der durch den Stern erzeugten Wechsel in die und aus der Klammer heraus aufgeführt. In jedem Fall ist die Anzahl der Backtrackings etwas höher, dafür wird die Anzahl der benötigten Zyklen drastisch reduziert. Das ist eine große Einsparung.

Tabelle: Effizienz bei einem traditionellen NFA.

	˹"([^\\"]|\\.)*"˼			˹"([^\\"]+|\\.)*"˼
Beispieltext	Tests	BT	*-Zyklen	Tests	BT	*-Zyklen
"makudonarudo"	16	2	13	17	3	2
"2\"x3\" likeness"	22	4	15	25	7	6
"sehr...99 Zeichen...lang"	111	2	108	112	3	2

---

Zurück zur Realität

Ja, ich war mit dieser Entdeckung sehr zufrieden. Leider ist diese »Verbesserung« – so gut sie zunächst scheint – ein veritabler Wolf im Schafspelz. Als ich ihre Qualitäten gepriesen habe, habe ich wohlweislich keine Zahlen für einen POSIX-NFA angegeben. Sie wären wohl etwas erstaunt gewesen, für das Beispiel "sehr●...●lang" dreihunderttausend Millionen Milliarden Billionen (um genau zu sein: 324 518 553 658 426 726 783 156 020 576 256 oder etwa 325 Quintillionen) Backtrackings vorzufinden. Milde ausgedrückt, bedeutet das VIEL Arbeit. Auf meinem Rechner würde das etwa 50 Quintillionen Jahre dauern, plus/minus ein paar hundert Billionen Jahrtausende. (Anmerkung: Die angegebene Zeit ist aufgrund der Zahlen von anderen Benchmarks hochgerechnet; ich habe die Tests nicht wirklich so lange laufen lassen.)

Wirklich erstaunlich! Wie und warum kann das passieren? Kurz gesagt liegt es daran, dass etwas in der Regex unmittelbar von einem Plus quantifiziert wird und dazu in einem Unterausdruck vorkommt, der von einem Stern quantifiziert ist, ohne dass festgelegt ist, welcher der beiden Quantoren für ein bestimmtes Zeichen im Suchstring zuständig ist. Der daraus resultierende Nicht-Determinismus (also das »Nicht-Bestimmtsein«) löst die Katastrophe aus. Ich versuche, das näher zu erläutern.

»Exponentielle« Mustersuche

Ohne das Plus wurde ˹[^\\"]˼ nur vom Stern quantifiziert, und die Anzahl der Möglichkeiten für das Matching von ˹[^\\"]*˼ hielt sich im Rahmen. Es erkannte ein Zeichen, ein zweites, noch eins usw., in den meisten Fällen eine ganze Reihe von Zeichen im Suchstring. Vielleicht wurde nicht der ganze Suchstring durchquert, aber im schlechtesten Fall war die Anzahl der erkannten Zeichen direkt proportional zur Länge des Suchstrings. Auch die Menge der zu erledigenden Arbeit stieg linear mit der Länge des Strings.

Mit der neuen Regex ˹([^\\"]+)*˼ steigt die Anzahl der Möglichkeiten, wie sich Stern und Plus den String aufteilen können, exponentiell mit der Länge des Strings. Wenn der String makudonarudo lautet, können das zwölf durch den Stern hervorgerufene Iterationen sein, wobei jedes ˹[^\\"]+˼ innerhalb der Klammern auf nur ein Zeichen passt (hier dargestellt als ›m a k u d o n a r u d o‹). Oder ist es nur eine Iteration des Sterns, und das innere ˹[^\\"]+˼ passt auf den ganzen String (›makudonarudo‹)? Oder vielleicht handelt es sich um drei Iterationen des Sterns, und die inneren ˹[^\\"]+˼ passen auf 5, 3 und 4 Zeichen (›makud ona rudo‹). Vielleicht passen sie auf 2, 7 und 3 Zeichen (›ma kudonar udo‹). Oder auch ...

Sie sehen, es gibt hier einige Möglichkeiten (bei diesem zwölfbuchstabigen String 4096). Bei jedem zusätzlichen Zeichen verdoppelt sich die Zahl, und eine POSIX-NFA-Maschine muss sie alle durchprobieren, bevor sie eine Antwort geben kann. Dieses Verhalten nennt man »exponentiell« oder auch super-linear.

Wie auch immer man es nennt, es bedeutet Backtracking, und zwar viel (Anmerkung: Für Leute, die so etwas interessiert: Die Anzahl der Backtracking-Operationen bei einem String der Länge n beträgt 2ⁿ⁺¹, die Anzahl der dafür aufzuwendenden Vergleiche (Tests) ist 2ⁿ⁺¹+2ⁿ.) Backtracking! 4096 Kombinationen bei zwölf Zeichen dauern nicht lange, aber bei 20 Zeichen sind es schon Millionen, und das dauert ein paar Sekunden; bei 30 Zeichen geht es um Milliarden und Stunden, und bei 40 Zeichen dauert es über ein Jahr. Das ist offensichtlich unakzeptabel.

Nun mögen Sie denken: »Ah, POSIX-NFAs sind ja noch ziemlich selten, und mein Programm benutzt einen traditionellen NFA – alles in Butter.« Der wesentliche Unterschied zwischen einem POSIX- und einem traditionellen NFA ist der, dass der traditionelle NFA stoppt, sobald er einen Treffer für die ganze Regex gefunden hat. Wenn es aber gar keinen Treffer gibt, muss auch ein traditioneller NFA alle Möglichkeiten durchprobieren, bevor er ein – negatives – Resultat liefern kann. Sogar bei dem kurzen Beispiel "No●\"match\"●here aus Lösung 13 sind das 8192 Kombinationen, die geprüft werden müssen, bevor eine NFA-Maschine endgültig feststellt, dass es keinen Treffer gibt.

Ich war so überzeugt von meiner Entdeckung, dass ich durchaus glaubte, dass mein Werkzeug einen Bug hätte, weil es manchmal »einfror«. Wie sich herausstellte, bearbeitete es schlicht eines dieser ewigen Matchings. Jetzt, da ich die Situation verstehe, benutze ich diese Art von regulären Ausdrücken in meiner Benchmark-Serie; sie dient zum Ermitteln des verwendeten Maschinentyps:

• Wenn die Regex schnell ist, auch wenn kein Treffer gefunden wird, ist es wahrscheinlich ein DFA.
• Wenn die Regex nur schnell ist, wenn sie passt, handelt es sich um einen traditionellen NFA.
• Wenn sie immer langsam ist, handelt es sich um einen POSIX-NFA.

Ich habe beim ersten Punkt »wahrscheinlich« geschrieben, weil es bereits optimierende NFAs gibt, die solche exponentiellen Muster erkennen und die damit möglichen unendlichen Matchings vermeiden. (Mehr dazu später im Abschnitt Erkennung von »übermäßigem« Backtracking.) Sie werden außerdem mehrere Möglichkeiten kennenlernen, wie man einen solchen Ausdruck so umschreiben kann, dass er sowohl Treffer als auch einen Fehlschlag sehr schnell erkennt.

Die Liste legt nahe, dass man dieses Verhalten dazu benutzen kann, um aus der relativen Leistung der regulären Ausdrücke auf den verwendeten Maschinentyp zu schließen. Genau das haben wir mit einer ähnlichen Regex im Abschnitt Den Typ der Regex-Maschine bestimmen unter Wie Regex-Maschinen arbeiten getan.

Sicher, nicht jede kleine Änderung hat derart katastrophale Auswirkungen wie in diesem Beispiel. Wenn Sie aber nicht wissen, was hinter den Kulissen abläuft, tappen Sie im Dunkeln, bis Sie auf das Ausnahmebeispiel stoßen, das eben diesen Effekt hat. Gegen Ende des Kapitels nehmen wir die Effizienz und deren Auswirkungen in einer Reihe von Beispielen unter die Lupe. Auch hier müssen Sie die Grundlagen verstanden haben, bevor Sie sich mit den übergeordneten Problemen befassen können. Bevor ich Auswege aus der Falle des »ewigen Matchings« bespreche, muss ich noch einmal im Detail auf das Backtracking zurückkommen.

  

<< zurück

vor >>