Automat für den Teilstring-Abgleich

Gegeben als String über einig Alphabet, was ist der beste bekannte Algorithmus einen entsprechenden deterministischen endlichen Automaten (DFA) , die ein beliebige Zeichenfolge akzeptiert zu berechnen, enthält ?$s$$s$

Ich bin hauptsächlich an der geringsten zeitlichen Komplexität interessiert. Wenn Sie mir also sagen, welche Komplexität in der O-Notation am bekanntesten ist, um einen Automaten für eine Zeichenfolge zu erstellen, die genauso gut wäre.

Hendrik Jan hat Recht mit dem Knuth-Morris-Pratt-Algorithmus (Warnung, Wikipedia erklärt ihn nicht besonders gut, ein Text über Algorithmen ist wahrscheinlich die bessere Wahl). Die Fehlerfunktion kann verwendet werden, um einen DFA zu extrahieren, der den String-Abgleich durchführen kann. Es ist nicht sofort offensichtlich, dass die Fehlertabelle ein DFA ist, aber mit sehr wenig Arbeit kann die Übergangstabelle für den DFA erstellt werden. Wenn die Musterzeichenfolge ist, mit der Sie übereinstimmen möchten, beträgt die Zeit zum Erstellen der Tabelle (und damit zum Erstellen des DFA) .$W$$O(|W|)$

Die zentrale Idee ist, dass die Fehlertabelle (ich werde versuchen, die gleichen Namen wie Wikipedia zu verwenden, nur um ein fertiges Beispiel zu erhalten) Ihnen sagt, wo Sie in der Zeichenfolge sein könnten, wenn die aktuelle Übereinstimmung nicht funktioniert Wenn Sie also den nächsten Charakter, den Sie erwarten, nicht sehen, ist der Beginn des gewünschten Spiels möglicherweise bereits zu sehen. Sie sind nur fälschlicherweise weiter vorne, sodass Sie nur ein wenig "zurückverfolgen" möchten (Beachten Sie, dass es kein echtes Backtracking im üblichen algorithmischen Sinne gibt).$T$

Wenn wir also schamlos das Beispiel aus Wikipedia stehlen, sagen wir, wir haben die Fehlertabelle :$T$

$$\begin{array}{c|cccccc} i & 0 & 1 & 2 & 3 & 4 & 5 & 6 \\\hline W[i] & A & B & C & D & A & B & D \\ T[i] & -1 & 0 & 0 & 0 & 0 & 1 & 2 \end{array}$$

Wir können den DFA wie folgt konstruieren: Wir haben Zustände mit einem Rückgrat von Übergängen, die dem gesamten Muster entsprechen. Um mit der Tabelle übereinzustimmen, nennen wir den Startzustand und den Endzustand (also im Beispiel ). Das Rückgrat sind dann die Übergänge , also gehen wir im Beispiel vom Startzustand zum Zustand weiter ein und bis auf einem .$|W|+1$$q_{-1}$$q_{|W|}$$q_{6}$$\delta(q_{i-1},W[i]) = q_{i}$$q_{-1}$$q_{0}$$A$$q_{2}$$q_{3}$$D$

Jetzt besteht der Trick darin, die richtigen "Rückwärts" -Übergänge hinzuzufügen, damit wir nicht zu weit entlang des Rückgrats zurückgehen, wenn wir etwas falsch machen. Hier setzen wir uns die Fehlerfunktion ein. Wenn wir uns im Zustand und als nächstes Symbol sehen, können wir alternativ zu übergehen, wenn wir . Wenn wir uns im Beispiel im Zustand und kein , aber ein , können wir zu . Jedes andere Symbol bringt uns in den Startzustand zurück.$q_{i-1}$$W[i]$$q_{T[i]}$$W[T[i]]$$q_{5}$$D$$C$$q_{2}$

Wiederholen; Es gibt drei Arten von Übergängen: den Backbone-Übergang, wenn alles gut läuft, den Übergang, der durch die Fehlertabelle angegeben wird, damit wir uns möglicherweise ein wenig erholen können, und weitere Übergänge, die uns zurück in den Startzustand bringen.$|\Sigma| - 2$

Der Start- und Endzustand sind natürlich etwas Besonderes, der Startzustand kann nicht weiter zurückgehen, sodass der Fehlerbehebungsübergang mit den anderen Übergängen angezeigt wird. Sobald wir den Endzustand erreicht haben, spielt es keine Rolle, was wir sonst noch sehen Es ist also auch ein Sink-Zustand.

Es gibt eine letzte Falte: In dem Fall, in dem das Fehlersymbol dem erwarteten entspricht (z. B. und ), können wir die Entscheidung einfach verschieben, bis sie unterschiedlich sind, oder wir können eine NFA erstellen .$W[1]$$W[5]$

Das Beispiel führt dann zu einem DFA, der wie folgt aussieht (mit Ausnahme von Fehlern):

Die gestrichelten Übergänge repräsentieren die Übergänge "alles übrig".

Es sollte leicht zu erkennen sein, dass wir anhand der Tabelle den DFA in -Zeit erstellen können (wirklich in einem Durchgang). Die Tabelle kann auch in - Zeit erstellt werden - der Quellcode auf Wikipedia ist ausreichend. Wenn wir schlau werden, können wir natürlich den Zwischentabellenschritt überspringen und den Tabellenerstellungsalgorithmus verwenden, um den DFA sofort zu erstellen. Diese Laufzeit ist auch die beste, auf die wir hoffen können, da ein DFA, der nur mit dieser Zeichenfolge übereinstimmt, mindestensÜbergänge (und Zustände), daher müssen wir den gesamten String lesen , der Schritte ausführt.$O(|W|)$$O(|W|)$$|W|$$|W|+1$$W$$\Omega(|W|)$

Antworten. Obwohl ich eine gelöschte Antwort gesehen habe, denke ich immer noch, dass die Konstruktion in der Länge der Zeichenfolge linear ist (unter Berücksichtigung der Alphabetgrößenkonstante). Aho Corasick 1975, doi: 10.1145 / 360825.360855

Oder vielleicht KMP. Aho & Corasick betrachten Mustervergleichsautomaten für eine endliche Menge von Wörtern und bilden bei Fehlanpassungen = Fehlern einen Baum mit Rückzeigern. Dies ist im Stil des Knuth-Morris-Pratt-Algorithmus, der eine einzelne Zeichenfolge berücksichtigt. Ich konnte nicht feststellen, ob KMP tatsächlich explizit von Übereinstimmungs- / Fehlerautomaten zu deterministischen Automaten wechselt (mit einem Übergang für jeden Buchstaben im Alphabet). Grundsätzlich genügt also der KMP-Ansatz zusammen mit einem klugen Argument, dass dies in linearer Zeit in einen DFA umgewandelt werden kann. A & C erwähnt diesen letzten Schritt ausdrücklich. Die KMP-Fehlertabelle ist jedoch etwas einfacher als die A & C-Konstruktion (man benötigt keinen String-Baum) und ist im gesamten Web zu finden.

Eine Notiz. Jeder, der an einem Mustervergleich interessiert ist, sollte das Original-KMP-Papier, doi: 10.1137 / 0206024 , oder zumindest die historischen Bemerkungen aus Abschnitt 7 lesen. Zitat: "Knuth war verärgert zu erfahren, dass Morris den Algorithmus bereits entdeckt hatte, ohne Cooks Theorem zu kennen [. .] ". Das KMP-Papier wurde erst 1977 veröffentlicht, während Morris seine Version bereits 1969 in einem Texteditor implementierte, während Knuth und Pratt sie etwas später als Anwendung eines Cook-Beweises entdeckten.