Optimierungen vor der eigentlichen Suche

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

Bei einer guten Regex-Implementation kann unter Umständen schon vor dem Ansetzen der Regex auf den Suchstring Arbeit eingespart werden. In bestimmten Fällen wird festgestellt, dass die Regex niemals passen kann, sie braucht dann überheupt nicht angewendet zu werden.

Kompilations-Caching

In unserem kleinen Mail-Programm aus Erweiterte einführende Beispiele (siehe unter Ein kleines Mail-Programm) besteht der Hauptteil aus einer Schleife, in der jede Kopfzeile verarbeitet wird:

Zuerst muss jeder dieser regulären Ausdrücke auf Korrektheit geprüft und in eine interne Form übersetzt werden. Diese interne Form kann dann auf viele Strings angewendet werden. In diesem Fall wäre es sicher sehr geschickt, die interne Form in einem Cache aufzubewahren und diese abgespeicherte Form bei jedem Schleifendurchgang anzuwenden. Das braucht etwas Speicherplatz, ist aber dafür effizienter.

Inwieweit das tatsächlich möglich ist, hängt davon ab, nach welchem Modell eine Programmiersprache die regulären Ausdrücke unterstützt. Unter Wartung und Pflege von regulären Ausdrücken hatten wir drei Ansätze unterschieden: integriert, prozedural und objektorientiert.

Kompilations-Caching beim integrierten Ansatz

Beim integrierten Ansatz wie in Perl oder awk kann das Kompilations-Caching sehr einfach implementiert werden. Intern wird jede Regex mit einem bestimmten Stück Code verbunden, und bei mehrfachem Gebrauch der gleichen Regex wird immer auf den Code zurückgegriffen, der beim ersten Mal erzeugt wurde. Das ist sehr effizient, geht aber auf Kosten des Speicherplatzes, der für die kompilierten regulären Ausdrücke benötigt wird.

Die Tatsache, dass in einer Regex Variablen interpoliert werden (d.h., in einer Regex vorkommende Variablen werden durch deren Werte ersetzt), legt dem Kompilations-Caching Knüppel in den Weg. Wenn wie in m/^Subject:●\Q$GesuchterBetreff\E\s*$/ Variablen interpoliert werden, dann kann die eigentliche Regex in jedem Schleifendurchgang eine andere sein. Wenn sich die Regex jedes Mal ändert, muss sie auch jedes Mal neu übersetzt werden und kann nicht wiederverwendet werden.

Nun kann sich die Regex zwar bei jeder Iteration ändern, aber sie muss es nicht tun. Wenn zu der kompilierten Form auch die ursprüngliche Regex nach der Variableninterpolation aufbewahrt wird, kann die Maschine diese in einem Zwischenschritt vergleichen und braucht die Regex nur bei einer Änderung neu zu kompilieren. Wenn sich die Regex tatsächlich jedes Mal ändert, wird nichts eingespart; wenn sie nur selten oder gar nicht verändert wird, wird entsprechend mehr gespart.

Kompilations-Caching beim prozeduralen Ansatz

Beim integrierten Ansatz ist die Regex mit einer bestimmten Stelle im Programm gekoppelt und kann relativ einfach wiederverwendet werden, wenn das Programm diese Stelle erneut abarbeitet. Beim prozeduralen Ansatz wird dagegen einfach eine Funktion mit dem Auftrag »benutze diese Regex« aufgerufen. Die Funktion hat im Prinzip keinerlei Wissen über den Zusammenhang oder darüber, von welcher Stelle im Programm sie aufgerufen wird, und muss daher die Regex jedes Mal neu kompilieren. In der Praxis ist das nicht effizient genug; die Funktion legt sich daher eine Tabelle mit den zuletzt benutzten regulären Ausdrücken und deren Kompilaten an und verwendet diese, wenn eine Regex wiederholt verwendet wird.

Wenn die »Benutze diese Regex«-Funktion aufgerufen wird, wird das Regex-Argument mit den Einträgen in der Tabelle verglichen. Wenn es darin bereits vorhanden ist, wird die zuvor kompilierte Form verwendet. Wenn nicht, wird die Regex kompiliert, und sowohl die Regex als auch das Kompilat werden in der Tabelle abgelegt. Wenn die Größe des Caches begrenzt ist, wird zuvor der älteste Eintrag gelöscht.

Bei GNU Emacs beispielsweise umfasst diese Cache-Tabelle 20 Einträge, bei Tcl 30, bei PHP sind es mehr als 4000. Bei den .NET-Sprachen enthält der Cache normalerweise nur 15 Einträge, er lässt sich aber vergrößern oder ganz ausschalten (siehe unter Caching von regulären Ausdrücken).

Die Größe der Cache-Tabelle spielt dann eine Rolle, wenn in einer Schleife (wie bei unserem E-Mail-Beispiel) mehrere reguläre Ausdrücke benutzt werden. Dann sollten nach Möglichkeit alle in der Tabelle Platz haben, sonst ist bei der nächsten Iteration die erste Regex aus dem Cache verschwunden.

Kompilations-Caching beim objektorientierten Ansatz

Beim objektorientierten Ansatz entscheidet der Programmierer und nicht die Maschine, wann eine Regex kompiliert werden soll. Ihm stehen dafür Konstruktoren und Methoden wie New Regex (.NET), re.compile (Python) und Pattern.compile (java.util.regex) zur Verfügung.

Bei den einführenden, einfachen Beispielen unter Features und Dialekte wurde immer direkt vor dem Gebrauch der Regex kompiliert, aber man hätte das genauso gut früher erledigen können (zum Beispiel vor einer Schleife oder im Initialisierungsteil des Programms). Bei den Benchmark-Beispielen Benchmarks mit Java, Benchmarks mit VB.NET und Benchmarks mit Python wurde das so gemacht.

Beim objektorientierten Ansatz hat der Programmierer mit dem Destruktor auch die Kontrolle darüber, wann eine kompilierte Form weggeworfen werden kann. Damit kann Speicherplatz gespart werden.

Suche nach einzelnen Zeichen oder festen Substrings

Es ist viel »billiger«, einen String nach bestimmten Zeichen oder nach einem bestimmten Substring abzusuchen, als eine ausgewachsene NFA-Regex darauf loszulassen. Bei manchen Systemen wird daher eine Regex daraufhin überprüft, ob im Treffer ein solches Zeichen oder ein Substring vorkommen muss. Nach diesem wird gesucht, bevor die eigentliche Regex angewendet wird.

Bei ˹^Subject:●(.*)˼ zum Beispiel muss in jedem möglichen Treffer der String ›Subject:●‹ vorkommen. Das Programm sucht mit einem schnellen Algorithmus wie Boyer-Moore nach diesem String (dieser ist umso schneller, je länger der Suchstring ist). Auch wenn ein Programm den Boyer-Moore-Algorithmus nicht implementiert, kann es dennoch mit einem einfacheren Verfahren nach allen im festen String vorkommenden Zeichen suchen. Wenn zuerst nach seltenen Zeichen gesucht wird (in normalen Texten ist das ›t‹ aus dem ›Subject:●‹-Beispiel viel häufiger als ›:‹), gewinnt man möglicherweise noch etwas Zeit.

Eine Regex-Maschine kann sehr einfach feststellen, welche Teile der Regex ˹^Subject:●(.*)˼ Strings fester Länge sind, die in jedem möglichen Treffer vorkommen müssen, aber es ist wesentlich schwieriger herauszufinden, dass bei ˹klipp|klar|eklig˼ in jeder Alternative der Substring ›kl‹ vorkommt. Die meisten Implementationen erkennen das nicht, aber manche stellen immerhin fest, dass einzelne Zeichen wie ›l‹ und ›k‹ in jedem Fall vorkommen müssen.

Die einzelnen Systeme implementieren diese »Feste String«-Optimierung auf ganz unterschiedliche Weise. Bei den meisten wird die Optimierung durch eine Alternation vereitelt. Bei diesen Systemen hilft es, wenn man ˹klipp|klar˼ von Hand zu ˹kl(ipp|ar)˼ umformt. Beachten Sie auch den Abschnitt mit der verwandten »Erstes Zeichen«-Optimierung.

Optimierung »Test auf Mindestlänge«

Die Regex ˹^Subject:●(.*)˼ kann potenziell beliebig viele Zeichen erkennen, aber jeder mögliche Treffer muss mindestens neun Zeichen lang sein. Die Regex-Maschine muss also kürzere Strings gar nicht erst prüfen. Natürlich ist diese Optimierung umso wirkungsvoller, je länger der minimale Treffer sein muss; bei ˹:\d{79}:˼ muss ein Treffer beispielsweise bereits 81 Zeichen lang sein. Siehe auch die Optimierung Längenerkennung beim Getriebe.