Optimierungen mit dem Getriebe

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

Wenn die Regex-Maschine im Voraus nichts über die zu erwartenden Treffer an sich feststellen kann, ist es vielleicht doch möglich, die Anzahl der Positionen zu reduzieren, an denen die Regex angesetzt werden muss.

Optimierungen mit Zeilen- und String-Ankern

Wenn eine Regex mit einem ˹^˼ beginnt, braucht die ganze Regex offensichtlich nur ausgehend von den Positionen getestet zu werden, an denen ˹^˼ passt.

Die entsprechenden Bemerkungen im Abschnitt Suche nach einzelnen Zeichen oder festen Substrings, in welchen Fällen die Maschine die Optimierung anwenden kann, gelten auch hier. Eine Implementation, die diese Optimierung verwendet, sollte erfassen können, dass ˹^(klipp|klar)˼ nur an Positionen passen kann, an denen auch ˹^˼ passt, aber die meisten Systeme sind mit dem an sich äquivalenten ˹^klipp|^klar˼ überfordert. In einem solchen Fall kann man der Maschine mit ˹^(klipp|klar)˼ oder – noch besser – mit ˹^(?:klipp|klar)˼ auf die Sprünge helfen.

Ähnliche Optimierungen gibt es mit dem Anker ˹\A˼ und (bei wiederholten Mustersuchen) mit ˹\G˼.

»Implizite Zeilenanker«-Optimierung

Eine Regex-Maschine mit dieser Optimierung erkennt, dass eine Regex, die mit ˹.*˼ oder ˹.+˼ beginnt und die keine globale Alternation enthält, genauso gut ein ˹^˼ am Anfang enthalten könnte. Dann kann die Zeilenanker-Optimierung aus dem vorherigen Abschnitt angewandt und viel unnötige Arbeit eingespart werden.

Noch raffiniertere Systeme können diese Optimierung auch dann anwenden, wenn das ˹.*˼ oder ˹.+˼ am Anfang der Regex in einer Klammer enthalten ist. Mit einfangenden Klammern muss aber vorsichtig umgegangen werden: Wenn zum Beispiel bei ˹(.+)X\1˼ ein impliziter Anker an den Anfang der Regex gesetzt wird, wird der Treffer ›1234X2345‹ nicht gefunden. (Anmerkung: Perl benutzte diese Über-Optimierung mehr als zehn Jahre lang, bis der Perl-Mitentwickler Jeff Pinyan den Bug Anfang 2002 fand und korrigierte. Offenbar werden reguläre Ausdrücke der Art ˹(.*)X\1˼ nicht sehr häufig verwendet, sonst wäre der Fehler früher entdeckt worden.)

Optimierung mit dem Anker für das String- bzw. Zeilenende

Bei dieser Optimierung geht es um reguläre Ausdrücke, die auf ˹$˼ oder einen anderen Zeilenanker enden (siehe dazu den Abschnitt Zeilenende, Stringende). Bei einer solchen Regex sind Treffer nur an Positionen bis zu einer gewissen Entfernung vom Stringende möglich. Zum Beispiel muss jeder mögliche Treffer für ˹regex(es)?$˼ an einer Position beginnen, die acht (Anmerkung: Ich schreibe hier acht und nicht sieben, weil das ˹$˼ in manchen Dialekten auch auf die Position direkt vor einem Newline am Ende des Strings passen kann.) oder weniger Zeichen vom Stringende entfernt ist. Das Getriebe kann alle Positionen bis dahin einfach auslassen.

»Erstes Zeichen«-Optimierung

Dies ist eine allgemeinere Form der Optimierung »Suche nach einzelnen Zeichen oder festen Substrings«. Es wird die gleiche Information benutzt (jeder mögliche Treffer muss bei einem bestimmten Zeichen oder bei einem bestimmten literalen Substring beginnen) und damit das Getriebe so gesteuert, dass es direkt an der betreffenden Stelle beginnt. Zum Beispiel kann ˹klipp|klar|˼ genau nur ab einer Position unmittelbar vor einem ›k‹ oder einem ›g‹ passen, bei allen anderen Zeichen braucht das Getriebe die Regex gar nicht erst anzusetzen. Je länger der literale Substring ist, desto weniger »falsche« Startpositionen werden benutzt.

Optimierung mit literalen Strings mitten im Text

Das ist fast dasselbe wie die »Erstes Zeichen«-Optimierung, aber hier wird die Distanz bis zu einem literalen Substring im Suchtext benutzt. Bei einem Treffer für den Ausdruck ˹\b(perl|java)\.regex\.info\b˼ beispielsweise kommt nach genau vier Zeichen der literale String ›.regex.info‹, das Getriebe kann also mit einer schnellen Boyer-Moore-Suche den Substring ›.regex.info‹ suchen und die eigentliche Regex-Maschine vier Zeichen davor ansetzen.

Das funktioniert im Allgemeinen nur, wenn der literale String einen festen Offset hat. Bei ˹\b(vb|java)\.regex\.info\b˼ gibt es wohl einen literalen String, dieser kann aber irgendwo im Treffer auftreten.

Längenerkennung beim Getriebe

Diese Optimierung ist eng mit der Optimierung »Test auf Mindestlänge« verwandt. Damit kann das Getriebe feststellen, dass gegen Ende des Suchstrings kein Treffer mehr möglich ist, und muss keine neuen Versuche mehr starten.

  

<< zurück

vor >>