Die Regex-Maschine zum Treffer hinführen

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

Ein Programmierprinzip, das bei NFA-Maschinen viel ausmacht, besteht darin, die »kontrollierenden« Teile der Regex so weit wie möglich nach rechts zu verschieben. Ein Beispiel hatten wir schon kennengelernt: ˹kl(?:ipp|ar)˼ statt ˹klipp|klar˼. Im zweiten Fall umfasst die Alternation die ganze Regex, im ersten wird die relativ teure Kontrollstruktur »Alternation« erst dann überhaupt benutzt, wenn ein ˹kl˼ gefunden wurde.

Unter Die Schleife aufbrechen werden wir eine weiter verfeinerte Form dieses Prinzips kennenlernen, doch betrachten wir zunächst ein paar einfachere Fälle.

Die wahrscheinlichste Alternative zuerst

In diesem Buch finden Sie eine Anzahl von Situationen, in denen die Reihenfolge der Alternativen für die Funktion der Regex eine große Rolle spielt (siehe unter Metazeichen, Fallen bei geordneter Alternation, Die Umgebung richtig einschätzen, Das Getriebe ausschalten). In diesen Fällen kann man die Reihenfolge natürlich nicht ändern – zuerst muss eine Regex richtig sein, erst dann kann man optimieren. Es gibt aber Fälle, in denen die Reihenfolge keine Rolle spielt, und in solchen Fällen kann man etwas an Effizienz gewinnen, wenn man die wahrscheinlich am häufigsten passenden Alternativen zuerst nimmt.

Bei der Hostname-Regex (siehe unter Einen Hostnamen auf syntaktische Korrektheit prüfen) wurden im letzten Teil die Top-Level-Domains in einer Alternation aufgezählt. Man könnte diese einfach in alphabetischer Reihenfolge angeben, also ˹(?:aero|biz|com|coop|...)˼. Nun sind aber manche der Domains vorne im Alphabet ziemlich ungebräuchlich. Es könnte wesentlich effizienter sein, die häufigen Domains nach ganz vorne zu verschieben: ˹(?:com|edu|org|net|...)˼. (Anmerkung: Im deutschen Sprachraum ist es außerdem von Vorteil, die Ländercodes für Deutschland, Österreich und die Schweiz explizit ganz vorn in der Alternation aufzuführen, also ˹(?:com|de|at|ch|edu|...|[a-z][a-z])˼, sonst würden sie erst mit den zwei Zeichenklassen ganz am Ende erkannt. (Anm. d. Ü.))

Das spielt natürlich nur bei einem traditionellen NFA eine Rolle, und auch da nur, wenn wirklich ein Treffer gefunden wird. Bei einem POSIX-NFA oder bei einem Fehlschlag müssen ohnehin alle Alternativen ausprobiert werden; die Reihenfolge ist dann irrelevant.

Am Ende der Alternation nicht ausklammern

Wir verfolgen das Hostname-Beispiel weiter und vergleichen ˹(?:com|edu|...|[a-z][a-z])\b˼ mit ˹com\b|edu\b|...\b|[a-z][a-z]\b˼. Im zweiten Fall wurde das ˹\b˼ nach der Alternation auf alle Alternativen verteilt. Wenn eine Alternative ohne die Wortgrenze passen würde, kann so unter Umständen schneller, ohne die Alternation zu verlassen, herausgefunden werden, dass die ganze Regex doch nicht passen kann; die Regex-Maschine bleibt innerhalb der Alternation und probiert die nächste Alternative aus. Der Aufwand für das Verlassen der Klammer und für die Wiederaufnahme der Alternation nach einem späteren Fehlschlag wird eingespart.

Dies ist vielleicht nicht die beste Illustration für diesen Sachverhalt, weil hier nur etwas erreicht wird, wenn die Alternative passt, aber die Teile der Regex, die nach der Alternation kommen, zu einem Fehlschlag führen. Gegen Ende des Kapitels werden wir dem Verfahren wieder begegnen – achten Sie auf die Überlegungen zu $SONST* unter Eine gut geführte Regex ist eine schnelle Regex.

Diese Optimierung kann gefährlich sein

Bei dieser Optimierung »von Hand« besteht die Gefahr, dass man damit eine bessere, interne, automatische Optimierung der Regex-Maschine zunichte macht. Wenn der Unterausdruck, der auf die Alternativen verteilt wird, literaler Text ist, beispielsweise der Doppelpunkt in ˹(?:klipp|klar):)˼, das wir zu ˹klipp:|klar:˼ umformen, dann widerspricht das der Technik, die wir im Abschnitt Literalen Text herausstellen empfohlen hatten. Die dort beschriebenen Optimierungen sind im Allgemeinen wirkungsvoller. Achten Sie also darauf, dass Sie diese nicht unmöglich machen.

Eine ganz ähnliche Warnung gilt für den Anker für das Zeilenende ˹$˼ bei Systemen, die dafür eine Optimierung kennen (siehe $ am Ende des Ausdrucks ausklammern). Bei solchen Systemen ist ˹(?:com|edu|...)$˼ viel schneller als ˹com$|edu$|...$˼, bei dem das Dollarzeichen auf alle Alternativen verteilt ist. (Allerdings verwendet von den getesteten Systemen nur Perl diese Optimierung.)

  

<< zurück

vor >>