Paralleler Regex, der mit NFA vs DFA übereinstimmt? Welcher ist schneller?

Question

Ich habe über NFA und DFA gelesen und es scheint, dass die populärste und schnellste Art der Implementierung von Regex Matcher darin besteht, NFA aus Regex zu erstellen, es in DFA zu konvertieren, dieses DFA zu minimieren, es in jeder Sprache zu implementieren und zu verwenden.

DFA ist eine bessere Wahl als NFA, weil es nur einen Übergang für eine Eingabe gibt, während NFA viele haben kann. Daher hat DFA nur einen Pfad zu verfolgen, während NFA - viele.

Aber das ist, wo ich nicht verstehe. Warum müssen wir NFA-Zustände im Auge behalten und zu ihnen zurückgehen, die uns verlangsamen? Können wir uns in verschiedene Threads aufteilen, wenn wir in mehr als einen Zustand kommen und jeden Pfad parallel berechnen? Wäre nicht schneller über DFA? Oder ich vermisse etwas?

Answer 1

Im Allgemeinen ist DFA schneller, aber NFA ist kompakter. Der NFA ist proportional zur Größe des regulären Ausdrucks. (Informeller Beweis: Jeder Operatorknoten in der Syntax eines regulären Ausdrucks fügt dem NFA-Diagramm einfach einen neuen Knoten hinzu.) Da das DFA aus Teilmengen von Sätzen der NFA-Zustände gebildet wird, gibt es Fälle, in denen es ziemlich groß sein kann. Im schlimmsten Fall ist ein DFA exponentiell mit dem regulären Ausdruck gewichtet. Ein Beispiel hierfür ist der Ausdruck der Form (a|b)(a|b)(a|b)(a|b)...(a|b), wo es N (a|b) Einheiten gibt, die zu einem DFA übersetzt werden, dessen Größe O (2 ** N) ist. Es enthält Übergänge durch eindeutige Zustände für alle Kombinationen für a und b. Ein degenerierter DFA könnte die Größe des CPU-Caches in Fällen überschreiten, in denen die Datenstrukturen, die zum Simulieren des äquivalenten NFA erforderlich sind, in den Cache passen.

Es gibt etwas höhere Kosten für ein DFA, aufgrund der zusätzlichen Schritte. Es gibt also Kompromisse: Werden genügend Daten vom NFA-Simulator verarbeitet, um den Aufbau eines DFA zu rechtfertigen?

Eine NFA-Simulation kann vollständig vermeiden, Teile des regulären Ausdrucks zu berühren, die überhaupt nicht auf einen Eingang zutreffen. Angenommen, ein Regex hat die Form R1 | R2, wobei R1 sehr einfach und klein ist und R2 ein riesiges, kompliziertes Biest ist. Angenommen, die Eingaben stimmen normalerweise nur mit R1 überein, und R2 trifft fast nie zu (z. B. aufgrund eines nicht übereinstimmenden Präfixes überhaupt kein Teil davon). Dies beeinflusst den Kompromiss: Kompilieren nach DFA bedeutet, dass alles kompiliert ist, der einfache R1-Teil und der monströse R2-Teil.

Schließlich muss eine Implementierung nicht unbedingt NFA oder DFA sein. Ein NFA-Simulator can cache the state setzt, was er berechnet. Diese zwischengespeicherten Status entsprechen den DFA-Zuständen und bieten einen ähnlichen Vorteil wie die Kompilierung für DFA. Sie können sich das vorstellen "JIT für die NFA". Der Cache kann auf eine bestimmte Größe getrimmt werden und unterliegt einer Ersetzungsrichtlinie, sodass Ausdrücke, deren vollständige DFAs groß sind, in weniger Speicher verarbeitet werden können (und fast genauso schnell, wenn die Daten eine gute Fundstelle im Cache anzeigen) .