Reguläre Ausdrücke in Java

Unkritisch habe ich Jahre lang reguläre Ausdrücke (java.util.regex) in Java verwendet. Auf der Universität hatte man ja gelernt, dass reguläre Ausdrücke effizient ausgewertet werden können.

Als ich in einem Projekt in einer großen Menge von Dokumenten (>10.000) eine große Menge von Worten (>1.000) suchen wollte, erinnerte ich mich an die Universität. Anstatt jedes Wort einzeln zu suchen wollte ich den regulären Ausdruck <Wort1>|<Wort2>|...|<Wort1000> suchen. Das müsste theoretisch deutlich effizienter sein, als nacheinander alle Wörter in jedem Dokument zu durchsuchen … Aber regulärer Ausdruck ist nicht regulärer Ausdruck und die schnellen Automaten der Vorlesung sind nicht die, die in Java verwendet werden.

---

Bevor ich meinen Irrtum auflöse und ein paar Hinweise gebe, wie es besser geht möchte ich kurz auf reguläre Ausdrücke und endliche Automaten und ihre Eigenheiten eingehen. Das Verständnis von endlichen Automaten ist wichtig um zu verstehen warum reguläre Ausdrücke in Java so arbeiten wie sie es tun.

Endliche Automaten

Der typische Weg eines Regulären Ausdrucks zu einem Matcher geht über die Umwandlung in einen Automaten. Aus der theoretischen Informatik kennen wir verschiedene Arten von Automaten für reguläre Sprachen, alle gehören entweder zu den nichtdeterministische endliche Automaten (NFA) oder zu den deterministische endliche Automaten (DFA).

Damit in etwa klar wird was der Unterschied zwischen NFA und DFA ist skizziere ich hier einmal einen typischen NFA und einen DFA zu dem Pattern (ab?|ac*)c*d.

NFA

DFA

Der DFA hat aber ein paar zusätzliche Forderungen an die Struktur des Automaten:

• keine Übergänge ohne Zeichen (keine ε-Kanten)
• von jedem Knoten aus gibt es für jedes Zeichen maximal eine Kante

Die Tatsache, dass man überhaupt unterschiedliche Automaten verwendet liegt darin begründet, dass jede konkrete Repräsentation und Interpretation eines Automaten Vor- und Nachteile hat. Werfen wir nun einen Blick auf folgende Varianten:

• Backtracking-NFA
• Bitparallel-NFA
• Thompson-NFA
• Graph-DFA
• Tabled-DFA

Backtracking-NFA

Der am meisten verbreitete Automat ist der Backtracking-NFA. Die Prozessierung eines Textes erfolgt durch Graphtraversierung entlang möglicher Kanten mit Backtracking, falls es nicht mehr weitergeht. Das entspricht im Großen und Ganzen einer Tiefensuche im Automatengraphen.

Die Laufzeit eines solchen Algorithmus ist proportional zur Anzahl der Pfade in dem Graph, da es potentiell möglich ist, dass die Tiefensuche, den korrekten Pfad erst als allerletzte Option findet (> polynomielle Laufzeit). Demgegenüber stehen die zahlreichen Features die ein Backtracking-NFA gegenüber anderen Varianten bietet.

Backtracking-NFAs ermöglichen capturing groups (Submatch Extraction), d.h. ausgezeichnete (geklammerte) Untergruppen eines Patterns können gespeichert werden. Die Theorie (und der POSIX-Standard) favorisiert hier die leftmost longest submatch extraction. D.h. es werden alle Pfade betrachtet, die das Pattern matchen und die Untergruppierung gewählt bei dem Gruppen möglichst früh und möglichst lang auftreten. Das obige Pattern angewand auf accccd speichert als Untergruppe 1 acccc, weil die optimale Gruppierung durch die Zustände 1-3-…-3-4-5 traversiert (1 und 3 gehören zur Gruppe, 4 nicht).

In der Praxis (d.h. in Java, C#, Python, Perl, …) relevant ist aber eher die greedy leftmost submatch extraction, diese speichert Untergruppen so wie sie während der Interpretation traversiert wurden. Dies hat gegenüber der POSIX-Variante den Vorteil, dass die Gruppierung bereits dann feststeht, wenn der Ausdruck gematcht wurde (und nicht erst wenn alle möglichen Matchings ermittelt wurden). Das obige Pattern angewandt auf accccd speichert als Untergruppe 1 a, weil der Algorithums die Zustände 1-2-4-4-…-4-5 traversiert (1 und 2 gehören zur Gruppe, 4 nicht).

Ein weiteres Feature von Backtracking-NFAs sind Lookaheads und Lookbehinds (zusammengefasst als Lookarounds). Innerhalb eines regulären Ausdrucks kann damit eine Bedingung (ein Pattern) für zukünftige Zeichen (Lookahead) oder vergangene Zeichen (lookbehind) angegeben werden. Die Wissenschaft ist sich sicher, dass Lookarounds die Mächtigkeit des endlichen Automaten nicht erhöhen (es gibt also keine Sprache, die nur unter Hinzunahme von Lookarounds erkannt würde). In der Praxis ist die Überführung von Lookarounds in einen DFA jedoch nie umgesetzt worden. Der Grund ist vermutlich, dass die Kompilierung eines DFA durch Lookarounds sehr lange dauert und sehr viel Speicher benötigt.

Ein Feature von Backtracking-NFAs, welches strenggenommen jeden NFA zum nicht-endlichen Automaten macht, sind Backreferences. Mit Backreferences kann man einmal gepeicherte Gruppen im späteren Verlauf des Patterns wieder aufnehmen.

Backtracking-NFAs werden in den meisten Programmiersprachen als Engines eingesetzt, z.B. Java, .NET, Perl oder Python.

Thompson-NFA

Durch Epsilon-Übergänge oder Alternativen mit gleichem Übergangsinput kann eine Eingabe zu mehreren Knoten führen. Der Thompson-NFA traversiert den Graphen auf eine Weise, dass er eine Menge aktiver Zuständen hält (initial ist das der Startzustand), und bei einem Eingabezeichen alle möglichen Übergänge von einem aktiven Zustand durchführt (die Ziele werden den neuen aktiven Zuständen hinzugefügt). Das enspricht einer Breitensuche im Automatengraphen.

Die Laufzeit ist durch die Breitensuche deutlich limitiert gegenüber dem Backtracking-NFA. Die Erzeugung und Speicherung der virtuellen Knoten benötigt Laufzeit und Speicher, aber unterm Strich ist die Laufzeit hier nur noch polynomiell.

Tatsächlich bieten solche NFAs noch capturing groups, aber nicht mehr mit der gleichen Semantik wie sie der Backtracking-NFA verlangt.

Tiefergehende Informationen zu Thompson-NFAs findet man auf Russ Cox’ Webseite. Der Thompson-NFA wird insgesamt eher selten eingesetzt, in Java gibt es z.B. die Bibliothek re2j.

Bitparallel-NFA

Noch paralleler geht es mit bitparallelen NFAs (Baeza-Yates, Navarro). Die Idee hierbei ist es jedem NFA-Knoten eine Bitposition zuzuordnen. Der gesamte Zustand eines Automaten kann somit mit der Menge aktiver bits charakterisiert werden. Ein Übergang zu einem nächsten Zustand ist eine “Multiplikation” mit einer Übergangsmatrix. Es gibt mehrere Varianten von bitparallelen Automaton, wir fokussieren im folgenden den bitparallelen Glushkov-Automaten.

Für Bitparallel-NFAs ist eine Vorprozessierung nötig, die aber sehr viel schneller ist als die Umwandlung in einen DFA. Die höchste Effizienz wird erreicht, wenn die Anzahl der Zustände in ein Computerword (64 bits) passt.

Der Bitparallel-NFA ist flexibler als ein traditioneller DFA. Besondere Stärken hat der Bitparallel-NFA bei der Suche nach Patterns, weil man für die Suche nach Patterns in der Regel einen reversen Automaten benötigt, der im Fall eines bitparalllelen NFA einfach abzuleiten ist. Außerdem lässt sich der Speicherverbrauch recht einfach (auf Kosten der Laufzeit) an den verfügbaren Speicher anpassen.

Literatur zum Thema Bitparallel-NFAs findet man hier. Eine Implementierung in Java findet sich bei stringsearchalgorithms (BPGlushkov).

Graph-DFA

Ein DFA lässt sich grundsätzlich wie ein NFA als Graph traversieren. Die Konstruktion des DFA garantiert, dass für jeden Zustand und jede Eingabe maximal eine Kante in Frage kommt (wenn gar keine qualifiziert ist, dann wird nicht akzeptiert). Die Frage ob man Tiefensuche oder Breitensuche durchführt stellt sich nicht, weil es für jeden Input genau einen Pfad durch den Graphen gibt.

Die Laufzeit eines Graph-DFAs ist somit linear. Die Vorprozessierung ist allerdings recht aufwändig, Vorteile gegenüber einer NFA-Prozessierung ergeben sich nur dann, wenn der Automat hinreichend oft benutzt wird. Er ist tendentiell langsamer als ein Tabled-DFA, aber dafür etwas flexibler.

Die Graphdarstellung hat den Vorteil, dass Kanten mit Events/Tags versehen werden können, um zusätzlich zum Zustand noch Ausgaben produzieren zu können. Über solche Mechanismen werden in manchen Implementierungen auch capturing groups abgebildet. Diese sind aber wie schon beim Thompson-NFA anderer Natur als die aus einem Backtracking-NFA und oft nicht so hilfreich.

Eine Implementierung in Java findet man bei brics, Rexlex, patternsearchalgorithms.

Tabled-DFA

Noch etwas schneller als der Graph-DFA is der Tabled-DFA, der ensteht indem man den Graphen in eine Zustandsübergangs-Tabelle überführt.

Die Laufzeit des Tabled-DFAs ist damit immer noch linear, aber die Anzahl der Operationen pro Zustandsübergang sinkt, die Anzahl der Cache-Treffer erhöht sich.

Die Zustandsübergangstabelle macht diese Art Algorithmus etwas unflexibel, sodass es deutlich schwieriger wird hier Übergänge mit zusätzlichen Ausgaben zu koppeln.

Eine Implementierung in Java findet man bei brics, Rexlex, patternsearchalgorithms

Suche mit regulären Ausdrücken

Kommen wir noch einmal zurück auf das Ausgangsproblem: Wir suchen <Wort1>|<Wort2>|...|<Wort1000> in vielen Dokumenten mit java.util.regex. Warum ist das so langsam?

Der Grund ist:
* java.util.regex verwendet zur Auswertung einen Backtracking-NFA. Im konkreten Fall (1000 Alternativen) probiert er jede einzelne Alternative bis zum Match aus. Der Algorithmus ist also genauso schnell wie die naive Lösung (in jedem Dokument jedes Wort suchen)
* die Idee war java.util.regex an jeder Position innerhalb des Dokuments zu suchen. Das bedeutet dass ein Fehlschlag beim Matching lediglich zum Wiederaufsetzen beim nächsten Zeichen führt. Viele Textsuchalgorithmen sind in der Lage Zeichen nur ein einziges Mal zu lesen und somit am letzten gelesenen Zeichen wieder aufzusetzen.
* die Anzahl der Dokumente ist letztlich nur deswegen entscheidend, weil sich in Gegenwart vieler Dokumente herausstellt, dass die Laufzeit selbst offline im Batch-Betrieb inakzeptabel ist

Was könnten wir also verbessern?

Zunächst könnten wir den Automaten verbessern, sodass er nicht alle 1000 Alternativen prüft, sondern vielmehr nur die Eingabe (das Dokument) prozessiert und nach Auffinden eines Treffers, diesen meldet. Dafür eignen sich die Ansätze mit Thompson-NFA, Bitparallel-NFA, Tabled-DFA. Dabei ist der Thompson-NFA am robustesten (langsam in der Suche, aber komplexe Patterns führen nicht zu unproportional hohen Vorprozessierungsaufwänden). Im Mittel am schnellsten sind Suchen mit Tabled-DFAs, diese sind aber besonders zeitaufwändig bei der Vorprozessierung komplexer Patterns (manchmal dominiert das selbst die Suchen bei großen Dokumentenmengen). Dazwischen positioniert sich der Bitparallel-NFA.

Weiterhin muss der Suchalgorithmus verbessert werden. Der naive Algorithmus startet an jeder Position im Dokument ein Matching. Sinnvoller wäre es, wenn der Automat alle Zeichen überliest, die nicht zum pattern gehört und nach einem Treffer auch hinter dem Treffer wieder neu aufsetzt. Das geht z.b. durch eine Modifikation des Automaten zu .*(<Wort1>|<Wort2>|...|<Wort1000>) (das such das erste Auftreten des Patterns, nicht notwendigerweise an der Position wo die Suche startete). Diese Suche hat eine Laufzeit, die linear von der Textlänge abhängig (und gar nicht von der Komplexität des Patterns). Leider ist der modifizierte Automat deutlich komplexer als der originale (was sich besonders schädlich für den Tabled-DFA auswirkt)..
Nachdem eine Lösungsskizze für die Suche mit Automaten da war, habe ich noch einmal recherchiert wie andere das Problem lösen. Es stellte sich heraus, dass ich viel Zeit mit der Optimierung einer bekannten Lösung verbracht hatte, statt eine angemessene Lösung zu finden. Die Suche nach mehreren Wörtern ist nämlich effizienter lösbar mit Multi-String-Suche. Leider fehlten auch dafür die geeigneten Bibliotheken in Java, hieraus entstand die Idee zu stringsearchalgorithms, welches sogar mehrere Algorithmen anbietet.t

Reguläre Ausdrücke in Java

Suche nach Alternativen ist wohl keine Aufgabe, die man mit regulären Ausdrücken lösen sollte. Aber es gibt Situationen in denen wir dennoch auf effiziente reguläre Ausdrücke angewiesen sind. Es wäre interessant zu wissen welchen Automat (bzw. welche Bibliothek) man für welches Problem nutzen sollte. Zunächst ist es wichtig die Parameter zu bestimmen:

• Sind die Patterns User-Eingaben oder Konstanten?
• Soll das Pattern gesucht oder gematcht werden?
• Wie lang ist das Pattern?
• Wie oft suchen wir das Pattern?
• Benötigen wir die volle Mächtigkeit der regulären Ausdrücke?
• Benötigen wir Nondeterminismus (Capturing Groups, Lookarounds)?

Wenn Patterns aus Benutzereingaben zusammengebaut werden, dann ist oft keine Möglichkeit mehr gegeben sie per Hand zu optimieren. Hier ist der nächste Optimierungsschritt tatsächlich nur die Transformation in einen schnelleren Automaten (Thompson-NFA, Bitparallel-NFA oder DFA). Bei konstanten regulären Ausdrücken kann man die Effizienz der Prozessierung selbst noch optimieren, oft kann man damit große Effizienzgewinne erreichen und (wenn alles andere stimmt) auf eine Transformation verzichten.

Die Entscheidung für Suche oder Matching ist insofern wichtig, weil Suche oft deutlich komplexere Automaten benötigt. Der Backtracking-NFA ist für die Suche extrem schlecht. Bei hinreichend simplen Ausdrücken ist der Bitparallel-NFA-Ansatz hier ziemlich effizient (die anderen benötigen deutlich längere Vorprozessierung).

Für kurze, wenig komplexe Patterns wirkt sich die Optimierung Richtung DFA nicht stark aus, bei langen komplexen Patterns hingegen schon. Besonders tückische reguläre Ausdrücke enthalten Alternativen, die in Schleifen ausgeführt werden. Recht harmlos sind hingegen flache Ausdrücke (ohne Alternativen) die nur von Wildcards, Zeichenklassen und optionalen Zeichen Gebrauch machen.

Je häufiger ein Pattern angewendet wird, desto wichtiger wird eine Optimierung Richtung DFA. Werden Patterns nur selten genutzt, dann kann die Generierung des Automaten zeitlich domininant werden.

Oft benötigen die verwendeten Patterns gar nicht die volle Mächtigkeit von regulären Ausdrücken. Manchmal lässt sich das Problem auf eine Multi-String-Suche (kein Kleene-Star (*)) oder Wildcardsuche (keine Alternativen) reduzieren, welche deutlich effizienter ohne reguläre Ausdrücke lösbar ist.

Es gibt Features von Nichtdeterministischen Regulären Ausdrücken, die nicht einfach anderweitig nachbildbar sind: Capturing Groups und Backreferences. Hier benötigt man einen NFA. Im Fall einer Suche kann es aber sinnvoll sein die Treffer zunächst mit einem DFA zu suchen und die Validierung/Gruppierung in einem zweiten Schritt auf die Treffer anzuwenden.

Es gibt auch Features, die man oft vermeiden sollte: Lookarounds. Für den täglichen Gebrauch sind sie gelegentlich bequemer (wir gehen ja auch nicht mit Milliarden von bytes um). Normalerweise findet man einen äquivalenten regulären Ausdruck ohne Lookarounds. Dieser ist dann nicht nur effizienter (egal welchen Automaten man verwendet), sondern oft sogar einfacher zu verstehen. Selbst wenn die regulären Ausdrücken aus Benutzereingaben stammen, sollte man überlegen ob man dem Benutzer diese Flexibilität zugestehen möchte.