Übliche Optimierungen

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

Eine gute Regex-Implementation kennt eine Reihe von Möglichkeiten, um schneller zum gewünschten Resultat zu kommen, sei es nun ein Treffer oder ein Fehlschlag. Es gibt zwei Klassen von Optimierungen:

Eine bestimmte Arbeit schneller erledigen

Manche Arten von Unterausdrücken wie z.B. ˹\d+˼ kommen so häufig vor, dass die Maschine dafür speziellen Code benutzt. Damit kann der Spezialfall schneller behandelt werden, als es die Maschine normalerweise könnte.

Arbeit vermeiden

Wenn die Maschine merkt, dass ein bestimmter Teil der Regex für das Endresultat keine Rolle spielt oder dass ein solcher Teil vielleicht nicht auf den ganzen Suchtext angewendet werden muss, dann kann das Überspringen dieser unnötigen Operationen eine Zeitersparnis bedeuten. So muss beispielsweise eine Regex, die mit ˹\A˼ (Stringanfang) beginnt, nur an einer Position angesetzt werden; wenn dort kein Treffer gefunden wird, braucht das Getriebe nicht Zeichen für Zeichen weiterzuschalten.

Weiter unten untersuchen wir etliche der Optimierungen, die mir bisher begegnet sind. Manche sind sehr ausgeklügelt. In keiner Programmiersprache sind alle diese Optimierungen vereinigt, es gibt auch keine zwei Sprachen, die die gleichen Optimierungen benutzen. Sicher sind auch noch andere Optimierungen denkbar, aber das Kapitel soll Ihnen die Fähigkeit vermitteln, die von einer Sprache angebotenen Optimierungsmethoden auszunutzen.

Umsonst gibt’s nichts!

Mit Optimierungen kann Rechenzeit eingespart werden, aber nicht immer. Die Optimierung lohnt sich nur, wenn damit mehr Zeit gespart werden kann, als für die Anwendung der Optimierung selbst gebraucht wird. Wenn die Maschine überprüft, ob eine Optimierungstechnik angewendet werden kann, und die Antwort negativ ausfällt, dann wird das Resultat langsamer gefunden, weil der zusätzliche Verwaltungsaufwand für die Katz war. Die Maschine muss also abwägen, wie aufwendig eine Optimierungstechnik ist, wie viel sie bringt und ob sie überhaupt angewendet werden kann.

Betrachten wir dazu ein Beispiel. Der Ausdruck ˹\b\B˼ (Wortgrenze an der gleichen Position wie eine Nicht-Wortgrenze) kann auf keinen Fall jemals passen. Wenn eine Regex-Maschine feststellen kann, dass eine Regex für jeden möglichen Trefferkandidaten ˹\b\B˼ enthält, könnte die Maschine wissen, dass die gesamte Regex nie passen kann. Sie müsste überheupt nie auf einen String angewendet werden; die Maschine könnte sofort einen Fehlschlag zurückgeben. Bei langen Suchstrings wäre die Zeitersparnis enorm.

Dennoch erkennt keine der mir bekannten Regex-Implementationen diese Situation. Warum nicht? Es ist nicht ganz einfach festzustellen, ob der Unterausdruck an jedem denkbaren Treffer teilnimmt. Man kann sich unschwer eine Regex vorstellen, die irgendwo ein ˹\b\B˼ enthält, die aber doch auf einen String passen kann; der Optimierer muss also die Regex zuerst genau analysieren, um sicher zu sein.

Die Ersparnis kann aber ganz beträchtlich sein, und wenn ˹\b\B˼ häufig vorkäme, dann würde sich der Aufwand bestimmt lohnen.

Nun, der Unterausdruck ist so selten (und unsinnig!), (Anmerkung: Früher habe ich zum Testen zuweilen ˹\b\B˼ als Teil eines größeren Ausdrucks benutzt, um zu erzwingen, dass eine Alternative fehlschlägt. Wenn der Ausdruck zum Beispiel an der markierten Stelle in ˹...(dies▵|dieses andere)...˼ eingesetzt wird, kann die erste Alternative nie passen. Heute benutze ich für den gleichen Zweck meist ˹(?!)˼. Eine interessante, wenn auch Perl-spezifische Anwendung davon finden Sie unter Mit Codemustern alle möglichen Treffer ausgeben.) dass auch die größte Zeitersparnis nur in den seltensten Fällen verwirklicht werden könnte.

Jeder macht’s ein bisschen anders

Bei den folgenden Optimierungen sollten Sie etwas im Auge behalten: Ich habe versucht, allen Optimierungstechniken einen einfachen, klaren Namen zu geben, aber hinter den Kulissen ist jede der Methoden ein bisschen anders implementiert. Auch eine scheinbar harmlose, kleine Änderung in einer Regex kann zu dramatischen Verbesserungen bei der einen Implementation führen und kann umgekehrt die Regex bei einer anderen Maschine verlangsamen.

Wie ein regulärer Ausdruck angewendet wird

Bevor wir uns weiteren Optimierungstechniken zuwenden, sollten wir die einzelnen Schritte bei der Mustersuche genauer verstehen. Über den Backtracking-Mechanismus haben wir schon viel gelernt, hier treten wir einen Schritt zurück und besehen uns den ganzen Vorgang in einem größeren Zusammenhang.

Wenn ein regulärer Ausdruck auf einen Suchstring angewendet wird, werden folgende Schritte ausgeführt:

  1. Kompilierung der Regex

    Der reguläre Ausdruck wird auf syntaktische Fehler geprüft und, falls korrekt, in eine interne Form kompiliert.

  2. Das Getriebe setzt ein

    Das Getriebe wird in Gang gesetzt; es setzt die Regex-Maschine auf die erste Position im Suchstring an, also auf den Stringanfang.

  3. Die Komponenten werden getestet

    Die Maschine arbeitet sich Komponente für Komponente durch die Regex und durch den Suchstring hindurch, wie unter Wie Regex-Maschinen arbeiten beschrieben wurde. Das Backtracking haben wir schon im Detail beschrieben, zusätzlich sind dazu noch folgende Punkte erwähnenswert:

    • Nebeneinanderstehende Komponenten wie etwa ˹S˼, ˹u˼, ˹b˼, ˹j˼, ˹e˼ ... werden nacheinander geprüft, und bei der ersten Nicht-Übereinstimmung wird angehalten.
    • Bei Quantoren wird zwischen dem Quantor (soll nach weiteren gleichartigen Komponenten gesucht werden?) und der zugehörigen Komponente (haben wir eine Übereinstimmung?) hin- und hergewechselt.
    • Bei einfangenden Klammern entsteht einige Verwaltungsarbeit. Der eingefangene Text wird abgespeichert, damit er nachher in den Variablen $1 usw. zur Verfügung steht. Da auch Klammern dem Backtracking unterworfen sind, muss auch beim Eintritt in eine Klammer und beim Verlassen der Klammer der Zustand der Regex-Maschine abgespeichert werden.
  4. Treffer finden

    Wenn ein traditioneller NFA einen Treffer findet, ist die Suche erfolgreich beendet. Bei einem POSIX-NFA wird dieser Treffer nur als bisher längster Treffer abgespeichert, aber die Maschine muss gleichwohl alle abgespeicherten Zustände auf mögliche längere Treffer überprüfen. Wenn die Liste der abgespeicherten Zustände erschöpft ist, wird der längste gefundene Treffer als Antwort zurückgegeben.

  5. Weiterschalten des Getriebes

    Wenn ausgehend von der aktuellen Position kein Treffer gefunden wird, schaltet das Getriebe weiter; es setzt die Regex-Maschine an der nächsten Position im String an. Die Maschine beginnt dort wieder bei Punkt 3.

  6. Fehlschlag

    Wenn an keiner der möglichen Positionen im String ein Treffer gefunden wurde, wird ein Fehlschlag für die gesamte Regex zurückgegeben.

In den nächsten Abschnitten werden die verschiedenen Möglichkeiten untersucht, wie die Arbeit bei all diesen Schritten durch Optimierungen reduziert werden kann.

  

  

<< zurück vor >>

 

 

 

Tipp der data2type-Redaktion:
Zum Thema Reguläre Ausdrücke bieten wir auch folgende Schulungen zur Vertiefung und professionellen Fortbildung an:
   

Copyright der deutschen Ausgabe © 2008 by O’Reilly Verlag GmbH & Co. KG
Für Ihren privaten Gebrauch dürfen Sie die Online-Version ausdrucken.
Ansonsten unterliegt dieses Kapitel aus dem Buch "Reguläre Ausdrücke" denselben Bestimmungen, wie die gebundene Ausgabe: Das Werk einschließlich aller seiner Teile ist urheberrechtlich geschützt. Alle Rechte vorbehalten einschließlich der Vervielfältigung, Übersetzung, Mikroverfilmung sowie Einspeicherung und Verarbeitung in elektronischen Systemen.

O’Reilly Verlag GmbH & Co. KG, Balthasarstr. 81, 50670 Köln