Gerichtete Graphen mit SQL lösen – Teil 2

Das Problem besteht nun darin, diese Tabellen mit Zuständen und Übergängen ausgehend von der Menge der Token zu erstellen. Wie bei den bereits besprochenen Problemen mit gerichteten Graphen beginnt man auch hier mit einem Ausgangsknoten (in diesem Fall dem Ausgangszustand) und versucht, alle Verbindungen zwischen den einzelnen Zuständen zu finden. Jede Verbindung ist eine Menge der bislang erkannten Zeichen, zum Beispiel:

Zustand 0: Ausgangszustand, Leerstring
Zustand 1: Zustand 'A'
Zustand 2: Zustand 'AA'
Zustand 3: Zustand 'AB'
Zustand 4: Zustand 'ABC'

Man kann die Tabelle mit den Übergängen ausfüllen, indem man den jeweiligen Buchstaben (oder, in einem realistischeren Programm, den regulären Ausdruck) mit dem aktuellen Zustand sowie mit dem Zielzustand verknüpft. Der folgende Code füllt die Tabelle aus und optimiert diese:

Der erste Ausdruck fügt den Ausgangszustand ein. Um die Token dann in unterschiedliche Längen aufzuspalten, können alle Zustände durchnummeriert werden. Im nächsten Schritt wird die Tabelle mit den Übergängen mit denjenigen Zeichen gefüllt, die erforderlich sind, um von einem Zustand zum nächsten zu gelangen. Und schließlich wird die Token-ID an den Zielzustand angehängt, um anzuzeigen, dass dieser Zustand ein vollständiges Token repräsentiert. Wenn man zum Beispiel drei Token hinzufügt (1 = AAA, 2 = ABC, 3 = ASC) und dann den obigen Code ausführt, ergibt sich ein Datensatz wie in Tabelle A.