DFA und NFA im Vergleich

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

Sowohl DFAs als auch NFAs haben gute und schlechte Seiten, die im Folgenden behandelt werden.

DFA und NFA: Unterschiede bei der Kompilierung

Bevor die Regex wirklich auf den String angewendet wird, kompilieren beide Maschinentypen die Regex in eine interne Form, die ihrem Algorithmus besser entspricht. Diese Kompilierung ist bei NFAs im Allgemeinen schneller und verbraucht weniger Speicherplatz. Zwischen traditionellen NFAs und POSIX-NFAs gibt es diesbezüglich kaum einen Unterschied.

DFA und NFA: Unterschiede in der Geschwindigkeit der Mustererkennung

Bei simplen Tests auf Literale sind unter normalen Umständen beide Maschinen etwa gleich schnell. Die Geschwindigkeit eines DFAs ist in dieser Phase von der Komplexität der Regex unabhängig, bei NFAs ist die Geschwindigkeit direkt davon abhängig.

Ein traditioneller NFA muss alle möglichen Permutationen mit allen Backtrackings durchspielen, bis er herausfindet, dass es keinen Treffer gibt. Deshalb verwende ich das ganze Kapitel Die Kunst, reguläre Ausdrücke zu schreiben für die Erläuterung, wie man schnelle reguläre Ausdrücke für NFAs schreibt. Sie werden sehen, dass ein NFA-Matching ewig (na ja, fast ewig) dauern kann. Der traditionelle NFA hört immerhin auf, wenn ein Treffer gefunden wird.

Ein POSIX-NFA muss dagegen alle Möglichkeiten durchtesten, um den längsten Treffer zu finden; daher dauert es für diese Maschine gleich lang (und manchmal sehr lange), ob nun ein Treffer gleich zu Beginn gefunden wird oder ob es sich herausstellt, dass die Regex gar nicht passt. Aus diesem Grund ist das Formulieren von effizienten Ausdrücken für POSIX-NFAs doppelt wichtig.

In einem Punkt habe ich in dem Abschnitt eben etwas übertrieben: Es gibt durchaus Optimierungsverfahren, die den Suchvorgang bei NFAs abkürzen können. Sie haben eine Art von Optimierung schon gesehen: Bei einer Regex mit einem ˹^˼-Anker brauchen die Positionen nach dem Stringanfang nicht geprüft zu werden (siehe unter Das »Getriebe« schaltet zum nächsten Zeichen). Weitere Optimierungen werden unter Die Kunst, reguläre Ausdrücke zu schreiben behandelt.

Im Allgemeinen brauchen DFAs kaum Optimierungen (da sie von Haus aus schnell sind), und der Aufwand, den DFAs bei der Kompilierung betreiben, ist oft größer als der, den viele NFAs für die Optimierung aufwenden.

Manche modernen DFA-Maschinen versuchen, den Zeit- und Speicheraufwand für die Kompilierung so lange zurückzustellen, bis der Anfang eines möglichen Treffers gefunden wird. Je nach Art der Daten im String kann es sein, dass ein großer Teil der vorher aufgebauten Karte nie gebraucht wird. Wenn es gelingt, die wirklich benötigten Teile der Karte erst dann aufzubauen, wenn sie gebraucht werden, können Zeit und Speicherplatz eingespart werden. Der Fachausdruck für diese Technik heißt lazy evaluation, »aufgeschobene Auswertung«. Sie kann jedoch dazu führen, dass die Geschwindigkeit des Matchings nicht mehr unabhängig von der Komplexität der Regex ist.

DFA und NFA: Unterschiede bei den gefundenen Treffern

Ein DFA (oder POSIX-NFA) findet den »längsten frühesten Treffer«. Ein traditioneller NFA tut das vielleicht auch, oder auch etwas anderes. Eine konkrete NFA-Maschine wird bei einer bestimmten Regex/String-Kombination natürlich immer den gleichen Treffer finden. Es handelt sich also nicht um »Zufallstreffer«, aber bei einer anderen NFA-Implementation kann es anders herauskommen. Praktisch alle NFA-Maschinen, mit denen ich zu tun hatte, funktionieren allerdings auf genau die Art, wie ich sie hier beschrieben habe, aber das ist nichts, was durch den Algorithmus oder durch einen Standard garantiert ist.

DFA und NFA: Unterschiede bei den Fähigkeiten

Eine NFA-Maschine kann viele Merkmale unterstützen, die ein DFA gar nicht haben kann. Darunter fallen:

• Text mittels geklammerten Unterausdrücken einfangen. Verwandt damit sind die Unterstützung von Rückwärtsreferenzen und die Möglichkeit, nach dem Matching herauszufinden, wo im String diese Unterausdrücke aufgetreten sind.
• Lookaround und andere zusammengesetzte Zusicherungen der Länge null (siehe unter Lookahead; Lookbehind). (Anmerkung: lex hat ein Feature namens trailing context, das exakt das Gleiche wie eine positive Lookahead-Zusicherung der Länge null ist; es kann aber nur am Ende der Regex verwendet werden und nicht generell.)
• Nicht-gierige Quantoren und geordnete Alternation. Bei einem DFA könnte ganz einfach der kürzeste Gesamttreffer ermittelt werden (aus irgendwelchen Gründen unterstützt das aber kein DFA-Werkzeug direkt), aber lokale nicht-gierige Konstrukte oder eine Alternation, die die Reihenfolge der Alternativen berücksichtigt, lassen sich mit einem DFA nicht implementieren.
• Possessive Quantoren (siehe unter Possessive Quantoren) und atomare Gruppen (siehe unter Atomare Klammern).

Geschwindigkeit von DFAs mit Features von NFAs: Regex-Nirwana? Ich habe mehrfach wiederholt, dass ein DFA weder einfangende Klammern noch Rückwärtsreferenzen unterstützen kann. Das stimmt, aber es gibt Hybrid-Ansätze, die die zwei Techniken vereinen, um so dem »Regex-Nirwana« näherzukommen. Im Kasten NFA: Theorie und Praxis wird erläutert, wie NFAs im Laufe der Entwicklung von der theoretischen Ideallinie abgekommen sind, und es wäre nur natürlich, wenn das Gleiche bei DFAs passierte. Der Grundaufbau eines DFAs macht das schwieriger, aber schwierig bedeutet nicht unmöglich. GNU grep verfolgt einen einfachen, aber wirkungsvollen Ansatz: Es benutzt einen DFA, wenn dies möglich ist, und einen NFA, wenn Rückwärtsreferenzen benutzt werden. GNU awk macht es ähnlich – es benutzt für einfache »Passt das?«-Tests den sehr schnellen DFA aus GNU grep, der nur den »kürzesten frühesten Treffer« findet. Bei größeren Anforderungen wird eine NFA-Maschine benutzt. Damit kann GNU awk mittels seiner zusätzlichen gensub-Funktion Rückwärtsreferenzen unterstützen. Die Regex-Maschine in Tcl von Henry Spencer (Sie erinnern sich: Henry hat schon früh Wichtiges für die Verbreitung von regulären Ausdrücken geleistet, siehe Henry Spencers Regex-Paket) ist eine echte eierlegende Wollmilchsau: Unter manchen Aspekten ist sie ganz klar ein NFA – sie unterstützt Lookaround, einfangende Klammern und nicht-gierige Quantoren. Dann wiederum findet sie den »längsten frühesten Treffer« nach POSIX (siehe unter NFA, DFA und POSIX) und leidet nicht an bestimmten NFA-Problemen, die Sie unter Die Kunst, reguläre Ausdrücke zu schreiben kennenlernen werden. Es ist wirklich ganz erstaunlich.

DFA und NFA: Unterschiede bei der Schwierigkeit der Implementation

Einfache Versionen von sowohl DFA- wie auch NFA-Maschinen sind nicht allzu schwierig zu verstehen und zu programmieren, haben aber ihre Grenzen. Aus dem Wunsch nach Effizienz (in Bezug auf Speicherbedarf und auch auf Geschwindigkeit) und nach zusätzlichen Features entstehen aber automatisch sehr komplexe Programme.

Wenn wir die Länge des Quelltextes als Richtschnur nehmen, war der NFA-Teil von ed aus Unix Version 7 (Januar 1979) weniger als 350 Zeilen lang. (Zum Vergleich: Für das ganze grep-Programm genügten 478 Zeilen.) Die 1986er Version der frei verfügbaren Version-8-Regex-Routinen von Henry Spencer umfasst schon 1900 Zeilen, und Tom Lords rx-Paket, ein NFA von 1992, ist bereits 9700 Zeilen lang (rx wird unter anderem in GNU sed benutzt).

Bei DFA-Implementationen war die von Version 7 etwas mehr als 400 Zeilen lang; Henry Spencers voll ausgebautes POSIX-DFA-Paket von 1992 umfasste bereits 4500 Zeilen.

GNU egrep Version 2.4.2 hat beide Maschinen und versucht, von jeder die besten Features zu benutzen; der Text umfasst etwa 8300 Zeilen. Die hybride DFA/NFA-Implementation von Tcl (siehe den obigen Kasten) umfasst etwa 9500 Zeilen.

Eine »einfache« Implementation muss nicht zwingend eine mit »wenigen Features« sein. Einmal benötigte ich für ein Textverarbeitungsproblem in Pascal reguläre Ausdrücke. Ich hatte Pascal seit der College-Zeit nicht mehr benutzt, ich brauchte aber nicht allzu lange, um eine simple NFA-Regex-Maschine zu programmieren. Sie hat kaum Extras und ist nicht besonders schnell, aber der Dialekt ist der einer ausgewachsenen NFA-Maschine, und so ist dieses kleine Paket absolut brauchbar.

  

<< zurück

vor >>