Backtracking global betrachtet

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

Auf lokaler Ebene ist das Backtracking nichts anderes als das Zurückkehren zu einem Zustand vor einem Matching-Versuch, um eine andere Möglichkeit auszuprobieren. Im größeren Zusammenhang gesehen, ist das nicht so einfach. In diesem Abschnitt betrachten wir genauer, was eigentlich beim Backtracking abläuft, wenn ein Treffer gefunden wird, aber auch, was in den Fällen geschieht, in denen die Regex nicht passt.

Wir beginnen mit einer genauen Analyse der Beispiele aus Regex-Methoden aus der Praxis. Wenn wir das Beispiel aus Probleme durch gieriges Verhalten, ˹".*"˼, auf

Der Name "McDonald’s" wird japanisch "makudonarudo" ausgesprochen

anwenden, kann der Vorgang des Matchings wie in der folgenden Abbildung dargestellt werden.

Abbildung: Erfolgreiches Matching von ˹".*"˼.

Die Regex wird auf jeden Punkt im String neu angesetzt, aber weil schon das erste Anführungszeichen nicht passt, passiert nichts Interessantes, bis beim Punkt A begonnen wird. Hier wird die ganze Regex evaluiert. Trotzdem weiß das »Getriebe« (siehe Das »Getriebe« schaltet zum nächsten Zeichen), dass bei einem erfolglosen Versuch die ganze Regex beim nächsten Zeichen neu getestet werden muss.

Das ˹.*˼ passt bis ans Ende des Strings, aber dort passt der Punkt nicht mehr auf das Zeilenende (das »Nichts« am Ende der Zeile). Keines der 55 gefundenen Zeichen wird durch irgendetwas in der Regex erzwungen, alle sind optional. Bei jedem Zeichen, das durch ˹.*˼ erkannt wird, speichert die Maschine den Zustand, so dass mittels Backtracking zu diesem Punkt zurückgekehrt werden kann, wenn sich die Treffersuche als Fehlschlag erweist.

Jetzt, da das gierige ˹.*˼ am Ende des Strings nichts mehr finden kann, geht die Maschine zum letzten gespeicherten Zustand zurück, zum Zustand »Versuche ˹".*▵"˼ an der Position ...ochen▵«.

Also muss das schließende Anführungszeichen mit dem Ende des Strings verglichen werden. Ein Anführungszeichen passt genauso schlecht wie der Punkt auf das Nichts am Ende, also geht das schief. Die Maschine geht zu einem weiteren Zustand zurück, diesmal wird das schließende Anführungszeichen an der Position ...gesproche▵n geprüft – ebenso ein Fehlschlag.

Die Zustände, die auf dem Weg von A nach B gespeichert wurden, werden nun in umgekehrter Reihenfolge abgeklopft, bis Punkt C erreicht wird. Dieser Zustand entspricht »Versuche ˹".▵*"˼ an der Position ...arudo▵"● ausge...«. Hier passt das Anführungszeichen und damit die ganze Regex, und wir haben bei Punkt D einen Treffer gefunden:

Der Name "McDonald’s" wird japanisch "makudonarudo" ausgesprochen

Wenn die Maschine ein traditioneller NFA ist, hört sie hier auf, vergisst alles über weitere gespeicherte Zustände und gibt ein positives Resultat zurück.

Überstunden für den POSIX-NFA

Ein POSIX-NFA merkt sich den Treffer als »den längsten Treffer, der bisher gefunden wurde«, und macht weiter. Er muss alle restlichen gespeicherten Zustände darauf testen, ob sie eventuell zu einem längeren Treffer führen könnten. Wir sehen, dass dies in diesem Beispiel nicht der Fall ist, aber die Maschine muss blind alle Möglichkeiten durchgehen.

Die meisten Zustände werden nur kurz getestet und sofort verworfen, nur bei zwei anderen Situationen passt das Anführungszeichen am Ende der Regex. Die Sequenzen D-E-F und F-G-H sind der Sequenz B-C-D recht ähnlich, nur sind die Treffer bei F und H eben kürzer als der zunächst bei D gefundene.

Beim Punkt I angekommen, bleibt als einzige Backtracking-Möglichkeit das Weiterschalten zum nächsten Zeichen im String. Da aber ein von A ausgehender Treffer gefunden wurde (drei sogar), ist nun auch der POSIX-NFA fertig und liefert den gleichen Treffer zurück.

Mehr Arbeit bei einem Fehlschlag

Wir müssen auch untersuchen, was abläuft, wenn kein Treffer gefunden wird. Nehmen wir als Regex ˹".*"!˼, von der wir wissen, dass sie nie ganz auf unseren Beispieltext passen kann. Die »Beinahe-Treffer« erzeugen aber zusätzliche Arbeit für die Maschine.

Die nächste Abbildung veranschaulicht das. Die Sequenz A-I ähnelt der in der vorigen Abbildung, allerdings wird hier bei Punkt D kein Treffer gefunden (weil kein Ausrufezeichen im String vorkommt). Außerdem gilt diese Sequenz sowohl für POSIX- als auch für traditionelle NFAs: Wenn kein Treffer gefunden wird, muss auch ein traditioneller NFA alle Möglichkeiten durchprobieren.

Abbildung: Fehlschlag mit ˹".*"!˼.

Weil es keinen Treffer ausgehend von Punkt A gibt, muss das Getriebe weiterschalten. Die Versuche, die von den Punkten J, Q und V ausgehen, sehen zunächst vielversprechend aus, erweisen sich aber auf die gleiche Art wie bei A als Sackgassen. Bei Y gibt es für das Getriebe keine Position mehr, wohin es weiterschalten könnte. Damit hat sich das ganze Matching als Fehlschlag erwiesen. Die Abbildung zeigt, dass mit dieser Erkenntnis viel Arbeit verbunden war.

Einschränkendere Formulierung

Zum Vergleich ersetzen wir den Punkt durch ˹[^"]˼. Wie unter Wie Regex-Maschinen arbeiten erwähnt wurde, führt das zu besser voraussagbaren Resultaten, weil die Regex nun stärker eingeschränkt formuliert ist. Sie ist auch effizienter; mit ˹"[^"]*"!˼ reicht ˹[^"]*˼ nicht mehr über das nächste Anführungszeichen hinaus, und dadurch werden viele Backtrackings vermieden.

Die nächste Abbildung zeigt den mit der vorigen Abbildung vergleichbaren Versuch, der natürlich auch fehlschlägt. Wie man sieht, wird tatsächlich viel weniger Backtracking benötigt. Wenn das unterschiedliche Resultat das ist, woran Sie interessiert sind, dann ist die verbesserte Effizienz ein angenehmer Nebeneffekt.

Abbildung: Fehlschlag mit ˹"[^"]*"!˼.

Alternationen können teuer sein

Alternationen können wesentlich zum Backtracking beitragen. Als einfaches Beispiel nehmen wir wieder unseren makudonarudo-String und vergleichen den Vorgang, wie die Ausdrücke ˹u|v|w|x|y|z˼ und ˹[uvwxyz]˼ darauf passen. Der Vergleich einer Zeichenklasse mit einem Zeichen ist eine sehr einfache Operation, (Anmerkung: Manche Implementationen sind effizienter als andere, aber in jedem Fall ist eine Zeichenklasse schneller als die äquivalente Alternation.) daher gibt es bei ˹[uvwxyz]˼ nur die Backtrackings, die durch das Getriebe bedingt sind (41 davon), bis der Treffer gefunden wird:

Der Name "McDonald’s" wird japanisch "makudonarudo" ausgesprochen

Bei ˹u|v|w|x|y|z˼ dagegen gibt es bei jeder neuen Startposition sechs Backtrackings, bis klar ist, dass keine der Alternativen passt. Erst dann kann das Getriebe weiterschalten. Insgesamt gibt es also 246 Backtracking-Operationen, bis der gleiche Treffer gefunden wird. Natürlich lässt sich nicht jede Alternation durch etwas anderes ersetzen, und auch wenn, ist es nicht immer so einfach wie in diesem Beispiel. Für bestimmte Fälle werden wir aber Methoden kennenlernen, die die Anzahl der durch Alternation hervorgerufenen Backtrackings erheblich reduzieren.

Den Backtracking-Vorgang zu verstehen ist das Wichtigste bei Effizienzüberlegungen bei einem NFA, aber es ist dennoch nur ein Aspekt. Die internen Optimierungen einer Regex-Maschine können die Mustersuche enorm beschleunigen. Später in diesem Kapitel betrachten wir die Aufgabe der Regex-Maschine genauer und werden sehen, welche Optimierungen die Maschine selbst vornehmen kann.

  

<< zurück

vor >>