Die »Erstes Zeichen«-Optimierung imitieren

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

Wenn das verwendete Programm die »Erstes Zeichen«-Optimierung nicht benutzt, dann kann man diese Optimierung oft mit einem entsprechenden Lookahead-Konstrukt (siehe Lookahead; Lookbehind) am Anfang der Regex nachbilden. Mit dem Lookahead kann man »im Voraus« prüfen, ob das Zeichen nach der aktuellen Position eines ist, das in der späteren, vollständigen Regex benötigt wird.

Zum Beispiel kann man bei ˹Jan|Feb|...|Dez˼ mit ˹(?=[JFMASOND])(?:Jan|Feb|...|Dez)˼ im Voraus überprüfen, ob man bei einem Zeichen aus ˹[JFMASOND]˼ steht (die Anfangsbuchstaben der Monatsnamen). Man muss diese Technik aber mit Bedacht einsetzen, denn nicht zu selten übersteigt der Aufwand dafür den möglichen Gewinn. Dieses Beispiel bringt bei den meisten von mir untersuchten Systemen etwas (Java, Perl, Python, Ruby, die .NET-Sprachen), offenbar erkennt keines davon die Möglichkeit zur Optimierung von sich aus.

PCRE verwendet diese Optimierung normalerweise nicht, aber mit der Funktion pcre_study (in PHP ist das der s-Modifikator) kann sie aktiviert werden. Tcl macht das natürlich von sich aus richtig, mehr dazu im Kasten DFAs, Tcl und das »Tuning« von regulären Ausdrücken.

Wenn die Regex-Maschine selbst mit einer internen Optimierung das erste Zeichen mit ˹[JFMASOND]˼ vergleichen kann, ist das naturgemäß viel schneller als unser explizit ausformuliertes Lookahead-Konstrukt. Können wir die Regex so umformulieren, dass sie diesen Test intern vornimmt? Auf vielen Systemen funktioniert in der Tat diese völlig verdrehte Version:

˹[JFMASOND](?:(?<=J)an|(?<=F)eb|...|(?<=D)ez)˼

Das werden Sie kaum auf den ersten Blick verstehen; lassen Sie sich Zeit, es ist eine gute Übung. Mit der einfachen Zeichenklasse am Anfang der Regex können die meisten Systeme die »Erstes Zeichen«-Optimierung anwenden; schon das Getriebe testet dann auf das erste Zeichen, bevor es die Regex ansetzt.

Wenn im Suchstring nur wenige Zeichen aus dieser Klasse vorkommen, ist das Resultat wesentlich schneller als das ursprüngliche ˹Jan|...|Dez˼ oder die vorherige Variante mit dem Lookahead. Wenn dagegen im Suchstring viele dieser Zeichen vorkommen, kann der zusätzliche Aufwand für die einzelnen Lookbehind-Klammern den Gewinn wieder wettmachen. Außerdem ist diese Variante wesentlich schlechter verständlich. Als Übung ist sie dennoch interessant und instruktiv.

Tun Sie das nicht mit Tcl!

In bestimmten Fällen kann also auch eine von Hand optimierte Regex ineffizienter als die ursprüngliche sein. Im Kasten DFAs, Tcl und das »Tuning« von regulären Ausdrücken wird gesagt, dass die Effizienz von regulären Ausdrücken bei der Regex-Maschine in Tcl weitgehend unabhängig von der Form des Ausdrucks ist. Die meisten Versuche zur Optimierung »von Hand« sind bei Tcl daher wirkungslos. Nun, bei dem Beispiel mit den Monatsnamen spielt die Form der Regex schon eine Rolle. Bei meinen Versuchen war die Regex mit dem Lookahead-Konstrukt ˹(?=[JFMASOND])˼ vorneweg mehr als hundertmal langsamer.

Tun Sie das nicht mit PHP!

Wir bereits erwähnt, kann man in PHP mit dem s-Modifikator die »study«-Option einschalten, worauf diese Optimierung automatisch angewendet wird. In PHP wird dies unter Der S-Modifikator genauer erklärt.

  

<< zurück

vor >>