Regex-gesteuerte und textgesteuerte Maschinen

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

Die zwei Typen von Maschinen stellen zwei fundamental verschiedene Arten dar, wie vorgegangen werden kann, wenn ein regulärer Ausdruck auf einen String angewendet wird. Ich nenne die benzinschluckende NFA-Maschine »Regex-gesteuert« und die elektrische DFA-Maschine »textgesteuert«.

NFA-Maschine: Regex-gesteuert

Betrachten wir ein Verfahren, wie eine NFA-Maschine die Regex ˹to(nite|knight|night)˼ auf den Text ›...tonight...‹ anwendet. Die Maschine geht jedes Element des regulären Ausdrucks durch, beginnend mit dem ˹t˼, und vergleicht dieses Element mit dem »aktuellen Text« aus dem String. Wenn der Vergleich stimmt, geht die Maschine zum nächsten Element der Regex und wiederholt das, bis alle Komponenten passen; damit stimmt der reguläre Ausdruck als Ganzes.

Im ˹to(nite|knight|night)˼-Beispiel ist die erste Komponente ein ˹t˼, das nicht passt, bis im String ein t gefunden wird. Dann wird mit der nächsten Regex-Komponente weitergearbeitet, dem ˹o˼, und wenn für dieses ein Treffer gefunden wird, kommt das nächste Element an die Reihe. In diesem Fall ist das »nächste Element« ˹(nite|knight|night)˼, was einfach »˹nite˼ oder ˹knight˼ oder ˹night˼« bedeutet. Mit drei Alternativen konfrontiert, versucht es die Maschine einfach mit jeder, der Reihe nach. Wir (mit hoch entwickelten neuronalen Netzen zwischen den Ohren) sehen sofort, dass für tonight nur die dritte Alternative in Frage kommt. Die Regex-gesteuerte Maschine – obwohl ihre Ahnen mit Neuronen zu tun hatten (siehe Die Ursprünge regulärer Ausdrücke) – kann das nicht, bevor sie alle Alternativen durchprobiert hat.

Das Durchprobieren der drei Alternativen geht nach dem gleichen Schema vor sich: Jedes Element der Regex wird mit dem String verglichen – »Teste auf ˹n˼, dann auf ˹i˼, dann auf ˹t˼ und schließlich auf ˹e˼.« Wenn einer der Tests fehlschlägt (und er tut dies in diesem Fall), nimmt sich die Maschine die nächste Alternative vor. Die Maschine wird also von der Regex kontrolliert, sie geht die Regex Element für Element durch. Deshalb nenne ich diesen Typ »Regex-gesteuert«.

Vorteile bei NFA-Maschinen: Die Regex hat die Kontrolle

Bei dieser Vorgehensweise wird jeder Unterausdruck fast unabhängig vom anderen durchgespielt. Abgesehen von Rückwärtsreferenzen, ist der einzige Zusammenhang zwischen verschiedenen Unterausdrücken die Tatsache, dass sie nebeneinander stehen und so einen größeren Ausdruck bilden. Es ist also das »Layout« der Regex-Strukturen (Alternationen, Klammern, Quantoren usw.), das bestimmt, wie die Maschine bei der Mustersuche vorgeht.

Weil die NFA-Maschine von der Regex kontrolliert wird, hat der Fahrer (der Autor des regulären Ausdrucks) einige Möglichkeiten, die Regex so zu gestalten, dass genau so gesucht wird, wie er sich das vorstellt (Regex-Methoden aus der Praxis und Die Kunst, reguläre Ausdrücke zu schreiben befassen sich mit diesem Thema). Wie das gehen soll, ist im Moment ziemlich vage, wird aber in Kürze ausformuliert.

DFA-Maschine: Textgesteuert

Im Unterschied zu NFA-Maschinen gehen textgesteuerte Maschinen den String durch und vergleichen jeden Buchstaben mit allen möglichen Treffern, »die gerade in Arbeit sind«. Beim tonight-Beispiel weiß diese Maschine sofort, nachdem sie das t gelesen hat, dass hier ein möglicher Treffer beginnt:

im String	in der Regex
nach ...t▵onight...	mögliche Treffer: ˹t▵o(nite|knight|night)˼

Nach jedem weiteren gelesenen Buchstaben wird die Liste der möglichen Treffer neu formuliert. Nach ein paar Schritten ist die Maschine in der Situation, dass nur noch zwei mögliche Treffer verfolgt werden müssen (die Alternative knight ist nicht mehr möglich):

im String	in der Regex
nach ...toni▵ght...	mögliche Treffer: ˹to(ni▵te|knight|ni▵ght)˼

Nach dem g muss sogar nur noch ein möglicher Treffer verfolgt werden. Wenn schließlich h und t eingelesen sind, weiß die Maschine, dass ein Treffer gefunden wurde, und beendet die Suche, in diesem Fall mit Erfolg.

Ich nenne dieses Vorgehen »textgesteuert«, weil jedes vom String gelesene Zeichen die Maschine kontrolliert. Wie im Beispiel oben kann ein partieller Treffer der Anfang von einer ganzen Anzahl von möglichen Treffern sein. Von diesen Kandidaten scheiden immer mehr aus, wenn die Maschine neue Zeichen aus dem String einliest. Es gibt auch die Situation, dass von einem solchen Kandidaten schon bekannt ist, dass er auf den ganzen Ausdruck passt. Würde die Regex ˹to(...)?˼ lauten, wäre der geklammerte Unterausdruck also optional, dann würde immer noch versucht, so viel Text wie möglich zu erkennen. Was immer mit dem Unterausdruck in der Klammer aber ausprobiert wird – die Regex als Ganzes hat bereits den Treffer ›to‹ gefunden.

Wenn ein Zeichen gelesen wird, das auf keinen der möglichen Treffer passt, die »in Arbeit sind«, dann muss auf einen der abgespeicherten kurzen, aber vollständigen Treffer zurückgegriffen werden. Wenn es solche nicht gibt, gibt es zum aktuellen Startpunkt keinen Treffer, und die Maschine muss bei einem späteren Zeichen von vorne beginnen.

Ein erster Vergleich von NFA- und DFA-Maschinen

Wenn Sie die zwei Maschinentypen aufgrund dessen vergleichen, was ich bisher erläutert habe, dann vermuten Sie wahrscheinlich, dass die DFA-Maschine im Allgemeinen schneller ist. Die Regex-gesteuerte NFA verbraucht viel zu viel Zeit, wenn sie alle die verschiedenen Alternativen in der Regex (drei in unserem Beispiel) mit dem gleichen Text vergleicht.

Diese Vermutung ist richtig. Während eines NFA-Matchings wird ein und dasselbe Zeichen aus dem Suchstring von vielen verschiedenen Teilen der Maschine getestet, oft sogar vom gleichen Teil mehrmals. Auch wenn ein Unterausdruck einmal gepasst hat, muss er wieder und wieder angewendet werden, weil er nur als Teil der gesamten Suchstrategie auftritt. Ein lokaler Unterausdruck kann passen oder auch nicht, die Maschine kann dieses Wissen erst auswerten, wenn sie ganz am Ende der Regex angekommen ist. (Wenn ich wüsste, wie ich in diesem Abschnitt den Satz »Das Spiel ist erst nach 90 Minuten vorbei« unterbrächte, würde ich es tun.) Umgekehrt ist die DFA-Maschine deterministisch – jedes Zeichen aus dem Suchstring wird maximal einmal untersucht. Wenn es auf einen Teil der Regex passt, dann ist zwar noch nicht bekannt, ob es zum endgültigen Treffer gehört (es kann auch zu einem Kandidaten gehören, der später rausfliegt); weil aber die Maschine alle provisorischen Treffer abspeichert, muss sie sich später nie mehr mit diesem Zeichen befassen.

Die zwei grundlegenden Typen von Regex-Maschinen haben die etwas hochtrabenden Namen Nicht-deterministischer Finiter Automat (Anmerkung: In der deutschen Literatur auch »endlicher Automat« und von daher DEA und NEA. (Anm. d. Ü.)) (NFA) und Deterministischer Finiter Automat (DFA). Ich nehme an, Sie verstehen, warum ich bei »NFA« und »DFA« bleibe – Sie werden diese Ausdrücke nie mehr in ausgeschriebener Form antreffen. (Anmerkung: Ich nehme an, ich sollte hier etwas Theorie einfließen lassen, wie es zu diesen Namen kommt ... wenn ich das könnte! Wie angedeutet, ist das Wort deterministisch sehr wichtig, aber die Theorie ist es nicht besonders, solange wir die praktischen Auswirkungen verstehen. Am Ende des Kapitels werden Sie das verstehen.)

Auswirkungen für uns als Benutzer

Weil NFAs von der Regex her gesteuert werden, sind die Details darüber sehr wichtig, wie genau nach Treffern gesucht wird. Wie ich gesagt habe, kann der Autor des regulären Ausdrucks den Suchvorgang durch die Art, wie die Regex formuliert wird, beeinflussen. Beim tonight-Beispiel wäre vielleicht weniger Arbeit vertan worden, wenn die Regex anders, vielleicht auf eine der folgende Arten geschrieben worden wäre:

• ˹to(ni(ght|te)|knight)˼
• ˹tonite|toknight|tonight˼
• ˹to(k?night|nite)˼

Zu jedem gegebenen String werden diese alle auf exakt den gleichen Text passen, aber die Maschine wird diesen Treffer auf ganz verschiedene Arten finden. Zu diesem Zeitpunkt wissen wir noch zu wenig, um diese Formulierungen gegeneinander abzuwägen, aber das wird sich ändern.

Mit DFAs ist es genau umgekehrt – weil die Maschine alle möglichen Treffer gleichzeitig verfolgt, spielen diese unterschiedlichen Formulierungen keine Rolle, solange sie alle auf die gleichen Texte passen. Es kann Hunderte von Wegen zum gleichen Ziel geben. Weil die DFA alle diese Wege speichert und sie gleichzeitig (auf fast magische Art) verfolgt, spielt es keine Rolle, welcher der Ausdrücke nun genau benutzt wird. Sogar so unterschiedlich aussehende reguläre Ausdrücke wie ˹abc˼ und ˹[aa-a](b|b{1}|b)c˼ sind für eine reine DFA nicht zu unterscheiden.

Drei Dinge fallen mir ein, wenn ich DFA-Maschinen (Anmerkung: »DFA-Maschine« ist eigentlich ein Pleonasmus, wie ISBN-Nummer, da ja das »A« für »Automat« steht, und das ist schon so etwas wie eine Maschine. Wir lösen das Dilemma, indem wir postulieren, dass sich »Automat« auf das abstrakte mathematische Modell bezieht und »DFA-Maschine« auf die Implementation dieses Modells in einem realen Werkzeug wie egrep. (Anm. d. Ü.)) beschreiben soll:

• DFAs sind sehr schnell.
• Die Mustererkennung nach DFA-Art ist sehr konsistent.
• Darüber zu reden, wie DFAs ihr Matching erzielen, ist sehr langweilig.

Ich werde gelegentlich alle drei Punkte näher erläutern.

Im Gegensatz dazu gibt es zum Regex-gesteuerten Vorgang der Mustererkennung bei NFAs sehr viel zu sagen. Bei NFAs kann man seine künstlerischen Neigungen viel mehr ausleben. Wenn eine Regex geschickt zusammengestellt ist, kann der Automat sehr effizient arbeiten; umgekehrt kann man durch ungeschickte Formulierung einer Regex die Maschine auch in große Schwierigkeiten bringen. Verbrennungsmotoren sind nicht die einzigen Maschinen, die absterben können. Um das zu verstehen, müssen wir zum zentralen Punkt von NFAs vorstoßen – zum Backtracking.

  

<< zurück

vor >>