Frage Ukkonens Suffix-Baum-Algorithmus in einfachem Englisch


Ich fühle mich an dieser Stelle etwas dick. Ich habe tagelang versucht, meinen Kopf komplett um die Suffixbaum-Konstruktion zu wickeln, aber da ich keinen mathematischen Hintergrund habe, entziehen sich viele der Erklärungen, da sie anfangen, übermßig mathematische Symbole zu verwenden. Am nächsten zu einer guten Erklärung, die ich gefunden habe ist Schnelle String-Suche mit Suffix-Bäumen, aber er glänzt über verschiedene Punkte und einige Aspekte des Algorithmus bleiben unklar.

Eine Schritt-für-Schritt-Erklärung dieses Algorithmus hier auf Stack Overflow wäre für viele andere außer mir von unschätzbarem Wert, da bin ich mir sicher.

Als Referenz, hier ist Ukkonen's Papier zum Algorithmus: http://www.cs.helsinki.fi/u/ukkonen/SuffixT1withFigs.pdf

Mein grundlegendes Verständnis, soweit:

  • Ich muss jedes Präfix P einer gegebenen Zeichenkette T durchlaufen
  • Ich muss durch jedes Suffix S in Präfix P iterieren und das zu Baum hinzufügen
  • Um dem Suffix S den Baum hinzuzufügen, muss ich jedes Zeichen in S durchlaufen, wobei die Iterationen entweder aus einem bestehenden Zweig bestehen, der mit demselben Satz von Zeichen C in S beginnt, und möglicherweise eine Kante in untergeordnete Knoten spaltet, wenn I Erreiche ein unterschiedliches Zeichen im Suffix ODER, wenn es keine passende Kante gab, um hinunterzugehen. Wenn keine passende Kante für C gefunden wird, wird eine neue Blattkante für C erstellt.

Der grundlegende Algorithmus scheint O (n2) Wie wir in den meisten Erklärungen gezeigt haben, müssen wir, da wir alle Präfixe durchlaufen müssen, jedes der Suffixe für jedes Präfix durchlaufen. Der Algorithmus von Ukkonen ist offensichtlich einzigartig wegen der Suffix-Zeiger-Technik, die er verwendet, obwohl ich denke Das ist, was ich nicht verstehen kann.

Ich habe auch Probleme zu verstehen:

  • genau wann und wie der "aktive Punkt" zugewiesen, verwendet und verändert wird
  • Was passiert mit dem Kanonisierungsaspekt des Algorithmus?
  • Warum müssen die Implementierungen, die ich gesehen habe, Begrenzungsvariablen, die sie verwenden, "reparieren"?

Hier ist das abgeschlossen C # Quellcode. Es funktioniert nicht nur korrekt, sondern unterstützt auch die automatische Kanonisierung und macht einen schöneren Textgraph der Ausgabe. Quellcode und Beispielausgabe ist:

https://gist.github.com/2373868


Update 2017-11-04

Nach vielen Jahren habe ich eine neue Verwendung für Suffixbäume gefunden und den Algorithmus in implementiert JavaScript. Gist ist unten. Es sollte fehlerfrei sein. Dump es in eine js-Datei, npm install chalk von der gleichen Stelle, und dann mit node.js laufen, um einige bunte Ausgabe zu sehen. Es gibt eine abgespeckte Version in demselben Gist, ohne den Debugging-Code.

https://gist.github.com/axefrog/c347bf0f5e0723cbd09b1aaed6ec6fc6


949
2018-02-26 11:30


Ursprung


Antworten:


Das Folgende ist ein Versuch, den Ukkonen-Algorithmus zu beschreiben, indem zuerst gezeigt wird, was er macht, wenn die Zeichenfolge einfach ist (d. H. Keine wiederholten Zeichen enthält), und dann auf den vollständigen Algorithmus erweitert wird.

Zunächst ein paar vorläufige Aussagen.

  1. Was wir bauen, ist Grundsätzlich gilt wie ein Suchtrie. Also da ist ein Wurzelknoten, Kanten, die zu neuen Knoten führen, und weitere Kanten gehen aus diesen heraus und so weiter

  2. Aber: Im Gegensatz zu einem Suchtrie sind die Kantenbeschriftungen nicht einzeln Figuren. Stattdessen wird jede Kante mit einem Paar Ganzzahlen beschriftet [from,to]. Dies sind Zeiger in den Text. In diesem Sinne jeder Edge trägt ein String-Label beliebiger Länge, nimmt aber nur O (1) Leerzeichen (zwei Zeiger).

Grundprinzip

Ich möchte zuerst zeigen, wie man den Suffixbaum von a erstellt besonders einfache Zeichenfolge, eine Zeichenfolge ohne wiederholte Zeichen:

abc

Der Algorithmus arbeitet in Schritten von links nach rechts. Es gibt ein Schritt für jedes Zeichen der Zeichenfolge. Jeder Schritt kann mehr als eine einzelne Operation umfassen, aber wir werden sehen (siehe die letzten Beobachtungen am Ende), dass die Gesamtzahl der Operationen O (n) ist.

Also, wir beginnen mit der links, und fügen Sie zuerst nur das einzelne Zeichen ein a indem Sie eine Kante vom Wurzelknoten (links) zu einem Blatt erstellen, und beschriftet es als [0,#], was bedeutet, dass die Kante das darstellt Teilzeichenfolge beginnend bei Position 0 und endend bei das aktuelle Ende. ich Verwende das Symbol # meinen das aktuelle Ende, die auf Position 1 ist (gleich nach a).

Wir haben also einen ersten Baum, der so aussieht:

Und was es bedeutet, ist dies:

Jetzt machen wir Fortschritte auf Position 2 (direkt nach b). Unser Ziel bei jedem Schritt ist einzufügen alle Suffixe bis zur aktuellen Position. Wir machen das durch

  • Erweiterung der bestehenden a-zu ab
  • Einfügen einer neuen Kante für b

In unserer Darstellung sieht das so aus

enter image description here

Und was es bedeutet ist:

Wir beobachten Zwei Dinge:

  • Die Kantendarstellung für ab ist das Gleiche wie es einmal war im ersten Baum: [0,#]. Seine Bedeutung hat sich automatisch geändert weil wir die aktuelle Position aktualisiert haben # von 1 bis 2.
  • Jede Kante verbraucht O (1) Raum, weil sie nur aus zwei besteht Zeiger in den Text, unabhängig davon, wie viele Zeichen es ist repräsentiert.

Als nächstes erhöhen wir die Position erneut und aktualisieren den Baum durch Anhängen ein c zu jeder vorhandenen Kante und Einfügen einer neuen Kante für die neue Suffix c.

In unserer Darstellung sieht das so aus

Und was es bedeutet ist:

Wir beobachten:

  • Der Baum ist der richtige Suffixbaum bis zur aktuellen Position nach jedem Schritt
  • Es gibt so viele Schritte wie Zeichen im Text vorkommen
  • Die Menge der Arbeit in jedem Schritt ist O (1), weil alle vorhandenen Kanten werden automatisch durch Inkrementieren aktualisiert #und Einfügen der eine neue Kante für das letzte Zeichen kann in O (1) gemacht werden Zeit. Daher wird für eine Kette der Länge n nur die Zeit O (n) benötigt.

Erste Erweiterung: Einfache Wiederholungen

Das funktioniert natürlich nur so gut, weil unsere Saite das nicht tut enthalten irgendwelche Wiederholungen. Wir schauen uns jetzt eine realistischere Zeichenkette an:

abcabxabcd

Es beginnt mit abc wie im vorherigen Beispiel ab wird wiederholt und gefolgt von x, und dann abc wird wiederholt gefolgt von d.

Schritte 1 bis 3: Nach den ersten 3 Schritten haben wir den Baum aus dem vorherigen Beispiel:

Schritt 4: Wir ziehen um # auf Position 4. Dies aktualisiert implizit alle vorhandenen Kanten dazu:

und wir müssen das letzte Suffix des aktuellen Schritts einfügen, a, beim der Ursprung.

Bevor wir dies tun, stellen wir vor zwei weitere Variablen (zusätzlich zu #), die natürlich die ganze Zeit dort waren, aber wir haben nicht benutzt sie bis jetzt:

  • Das aktiver PunktDas ist ein Tripel (active_node,active_edge,active_length)
  • Das remainderDies ist eine Ganzzahl, die angibt, wie viele neue Suffixe Wir müssen einfügen

Die genaue Bedeutung dieser beiden wird bald klar, aber für jetzt Lass uns einfach sagen:

  • Im einfachen abc ZB war der aktive Punkt immer (root,'\0x',0), d.h. active_node war der Wurzelknoten, active_edge wurde als Nullzeichen angegeben '\0x', und active_length war Null. Die Wirkung davon war, dass die eine neue Kante, die wir eingefügt in jedem Schritt wurde am Wurzelknoten als eingefügt frisch erstellte Kante. Wir werden bald sehen, warum ein Triple notwendig ist repräsentieren diese Informationen.
  • Das remainder wurde immer zu Beginn auf 1 gesetzt Schritt. Die Bedeutung davon war, dass wir die Anzahl der Suffixe hatten aktiv einfügen am Ende jedes Schrittes war 1 (immer nur die letzter Buchstabe).

Das wird sich jetzt ändern. Wenn wir das aktuelle Finale einfügen Charakter a An der Wurzel bemerken wir, dass es bereits ein Outgoing gibt Kante beginnend mit a, speziell: abca. Hier ist, was wir tun solch ein Fall:

  • Wir unterlassen Sie Fügen Sie eine frische Kante ein [4,#] am Wurzelknoten. Stattdessen wir merke einfach, dass das Suffix a ist schon in unserem Baum. Es endet in der Mitte einer längeren Kante, aber wir sind es nicht störte mich daran. Wir lassen die Dinge einfach so, wie sie sind.
  • Wir setze den aktiven Punkt zu (root,'a',1). Das bedeutet das Aktive Der Punkt befindet sich jetzt irgendwo in der Mitte der ausgehenden Kante des Wurzelknotens, der mit beginnt aund zwar nach Position 1 an dieser Kante. Wir Beachten Sie, dass die Kante einfach durch die erste angegeben wird Charakter a. Das reicht aus, weil es sein kann einziger Kante Beginnen Sie mit einem bestimmten Zeichen (bestätigen Sie, dass dies nach dem Durchlesen der gesamten Beschreibung zutrifft).
  • Wir erhöhen auch remainder, also zu Beginn des nächsten Schrittes es wird 2 sein.

Überwachung: Wenn das Finale Suffix, das wir einfügen müssen, wird gefunden existiere bereits im Baumder Baum selbst ist nicht geändert überhaupt (wir aktualisieren nur den aktiven Punkt und remainder). Der Baum ist dann keine genaue Darstellung des Suffixbaumes bis zum aktuelle Position mehr, aber es enthält alle Suffixe (weil das Finale Suffix a ist beinhaltet implizit). Daher, abgesehen von der Aktualisierung der Variablen (die alle von fester Länge sind, also ist dies O (1)) gab es keine Arbeit in diesem Schritt gemacht.

Schritt 5: Wir aktualisieren die aktuelle Position # zu 5. Dies aktualisiert automatisch den Baum auf diesen:

Und weil remainder ist 2Wir müssen zwei Final einfügen Suffixe der aktuellen Position: ab und b. Dies ist im Grunde, weil:

  • Das a Suffix aus dem vorherigen Schritt war nie richtig eingefügt. So ist es bliebund seit wir eins gemacht haben Schritt, es ist jetzt gewachsen von a zu ab.
  • Und wir müssen die neue finale Kante einfügen b.

In der Praxis bedeutet dies, dass wir zum aktiven Punkt gehen (der auf Hinter a auf was ist jetzt das abcab Rand), und fügen Sie die aktuelles letztes Zeichen b. Aber: Wieder stellt sich heraus, dass b ist auch schon vorhanden am selben Rand.

Also ändern wir den Baum nicht. Wir einfach:

  • Aktualisieren Sie den aktiven Punkt auf (root,'a',2) (gleicher Knoten und Kante wie zuvor, aber jetzt zeigen wir hinter die b)
  • Erhöhen Sie die remainder bis 3, weil wir noch nicht richtig haben eingefügt die letzte Kante aus dem vorherigen Schritt, und wir fügen nicht ein die aktuelle finale Kante entweder.

Um es klar zu sagen: Wir mussten einfügen ab und b im aktuellen Schritt, aber weil ab wurde bereits gefunden, wir haben den aktiven Punkt aktualisiert und haben es getan nicht einmal versuchen einzufügen b. Warum? Weil wenn ab ist in dem Baum, jedes Suffix davon (einschließlich b) Muss im Baum sein, auch. Vielleicht nur implizit, aber es muss da sein, wegen der So haben wir den Baum bisher gebaut.

Wir fahren fort mit Schritt 6 durch Inkrementieren #. Der Baum ist automatisch aktualisiert auf:

weil remainder ist 3Wir müssen einfügen abx, bx und x. Der aktive Punkt sagt uns, wo ab endet, also müssen wir nur Springe dorthin und füge die x. Tatsächlich, x ist noch nicht da, also wir teile die abcabx kanten und fügen einen internen Knoten ein:

Die Kantenrepräsentationen sind immer noch Zeiger in den Text Das Teilen und Einfügen eines internen Knotens kann in O (1) -Zeit erfolgen.

Also haben wir uns damit beschäftigt abx und dekrementieren remainder zu 2. Jetzt wir muss das nächste verbleibende Suffix einfügen, bx. Aber bevor wir das machen Wir müssen den aktiven Punkt aktualisieren. Die Regel dafür, nach der Spaltung und Einfügen einer Kante, wird aufgerufen Regel 1 unten, und es gilt immer wenn active_node ist Wurzel (wir lernen Regel 3 für andere Fälle weiter unten). Hier ist Regel 1:

Nach einem Einfügen von der Wurzel,

  • active_node bleibt Wurzel
  • active_edge wird auf das erste Zeichen des neuen Suffixes gesetzt   muss eingefügt werden, d.h. b
  • active_length wird um 1 reduziert

Daher das neue Aktivpunkt-Tripel (root,'b',1) zeigt an, dass die nächster Einsatz muss bei der bcabx Kante, hinter 1 Zeichen, d. h. hinter b. Wir können den Einfügepunkt in O (1) Zeit und prüfe ob x ist schon vorhanden oder nicht. Wenn es da war, wir würde den aktuellen Schritt beenden und alles so lassen, wie es ist. Aber x ist nicht vorhanden, also fügen wir es durch Teilen der Kante ein:

Auch dies dauerte O (1) Zeit und wir aktualisieren remainder zu 1 und der aktiver Punkt zu (root,'x',0) wie Regel 1 besagt.

Aber wir müssen noch etwas tun. Wir werden das nennen Regel 2:

Wenn wir eine Kante teilen und einen neuen Knoten einfügen, und wenn dies der Fall ist nicht der   erster Knoten erstellt während des aktuellen Schritts, verbinden wir die zuvor   eingefügt Knoten und den neuen Knoten durch einen speziellen Zeiger, a Suffix   Verknüpfung. Wir werden später sehen, warum das nützlich ist. Hier ist, was wir bekommen, die   Suffix-Link wird als gepunktete Kante dargestellt:

Wir müssen noch das letzte Suffix des aktuellen Schritts einfügen, x. Seit der active_length Komponente des aktiven Knotens ist gefallen auf 0 wird die letzte Einfügung direkt an der Wurzel vorgenommen. Da gibt es keine ausgehende Kante am Wurzelknoten beginnend mit x, wir fügen ein neues ein Kante:

Wie wir sehen können, wurden im aktuellen Schritt alle verbleibenden Einsätze hergestellt.

Wir fahren fort mit Schritt 7 indem man es einstellt #= 7, die automatisch das nächste Zeichen anfügt, a, an allen Blattkanten, wie immer. Dann versuchen wir das neue Finale einzufügen Zeichen an den aktiven Punkt (die Wurzel) und finden, dass es da ist bereits. So beenden wir den aktuellen Schritt ohne etwas einzufügen und Aktualisiere den aktiven Punkt auf (root,'a',1).

Im Schritt 8, #= 8, wir hängen an bund wie vorher gesehen, nur dies bedeutet, wir aktualisieren den aktiven Punkt auf (root,'a',2) und erhöhen remainder ohne zu tun alles andere, weil b ist schon da. Jedoch, Wir bemerken (in O (1) Zeit), dass der aktive Punkt ist jetzt am Ende einer Kante. Wir reflektieren dies, indem wir es auf neu setzen (node1,'\0x',0). Hier benutze ich node1 auf das beziehen interner Knoten der ab Kante endet bei.

Dann in Schritt #= 9, wir müssen 'c' einfügen und das wird uns helfen verstehe den letzten Trick:

Zweite Erweiterung: Verwenden von Suffix-Links

Wie immer, die # Update hängt an c automatisch an den Blatträndern und wir gehen zum aktiven Punkt, um zu sehen, ob wir 'c' einfügen können. Es wendet sich out 'c' existiert bereits an dieser Kante, also setzen wir den aktiven Punkt auf (node1,'c',1), Zuwachs remainder und nichts anderes tun.

Jetzt in Schritt #= 10, remainder is 4und so müssen wir zuerst einfügen abcd (was von vor 3 Schritten herrührt) durch Einfügen d am aktiven Punkt.

Versuch, einzufügen d am aktiven Punkt verursacht eine Kante geteilt in O (1) Zeit:

Das active_node, aus dem der Split ausgelöst wurde, ist in markiert rot oben. Hier ist die letzte Regel, Regel 3:

Nach dem Teilen einer Kante von einem active_node das ist nicht die Wurzel   Knoten, folgen wir dem Suffix-Link, der aus diesem Knoten herausgeht, falls es einen gibt   any, und setzen Sie die active_node zu dem Knoten, auf den es zeigt. Wenn da ist   kein Suffix Link, wir setzen den active_nodezur Wurzel. active_edge   und active_length bleiben unverändert.

Also ist der aktive Punkt jetzt (node2,'c',1), und node2 ist markiert in rot unten:

Seit dem Einfügen von abcd ist vollständig, wir dekrementieren remainder zu 3 und betrachte das nächste verbleibende Suffix des aktuellen Schrittes, bcd. Regel 3 hat den aktiven Punkt auf den richtigen Knoten und die richtige Kante gesetzt also einfügen bcd kann getan werden, indem einfach sein endgültiges Zeichen eingefügt wird d am aktiven Punkt.

Dies verursacht einen weiteren Kantensplit und wegen Regel 2wir muss einen Suffix-Link vom zuvor eingefügten zum neuen Knoten erstellen ein:

Wir beobachten: Suffix-Links ermöglichen es uns, den aktiven Punkt so zurückzusetzen, dass wir   kann das nächste machen verbleibender Einsatz bei O (1) Anstrengung. Schaue auf die   Diagramm oben, um zu bestätigen, dass tatsächlich Knoten bei Label ab ist verbunden mit   der Knoten bei b (sein Suffix) und der Knoten an abc ist verbunden mit    bc.

Der aktuelle Schritt ist noch nicht abgeschlossen. remainder ist jetzt 2, und wir Folge Regel 3, um den aktiven Punkt erneut zu setzen. Seit der Strom active_node (rot oben) hat keine Suffixverbindung, auf die wir zurückgesetzt haben Wurzel. Der aktive Punkt ist jetzt (root,'c',1).

Daher tritt die nächste Einfügung an der einen Ausgangskante des Wurzelknotens auf wessen Label beginnt mit c: cabxabcd, hinter dem ersten Charakter, d. h. hinter c. Dies verursacht eine weitere Trennung:

Und da dies die Schaffung eines neuen internen Knotens beinhaltet, folgen wir Regel 2 und setze einen neuen Suffix-Link aus dem zuvor erstellten internen Link Knoten:

(Ich benutze Graphviz Punkt für diese kleinen Grafiken. Der neue Suffix-Link führte dazu, dass dot das vorhandene neu anordnete Kanten, also überprüfen Sie sorgfältig, um zu bestätigen, dass das einzige, was war oben eingefügt ist ein neuer Suffixlink.)

Mit diesem, remainder kann auf 1 gesetzt werden und seit dem active_node ist root verwenden wir Regel 1, um den aktiven Punkt zu aktualisieren (root,'d',0). Dies bedeutet, dass der letzte Schritt des aktuellen Schritts darin besteht, einen einzelnen einzufügen d im Wurzelverzeichnis:

Das war der letzte Schritt und wir sind fertig. Es gibt eine Anzahl von Finale Beobachtungenaber,

  • In jedem Schritt bewegen wir uns # vorwärts um 1 Position. Dies automatisch aktualisiert alle Blattknoten in O (1) Zeit.

  • Aber es behandelt nicht a) irgendwelche Suffixe verbleibend von früher Schritte und b) mit dem letzten Zeichen des aktuellen Schritts.

  • remainder sagt uns, wie viele zusätzliche Inserts wir brauchen machen. Diese Einsätze entsprechen eins zu eins den Endsilben von die Zeichenfolge, die an der aktuellen Position endet #. Wir betrachten einen nach dem anderen und mache den Einsatz. Wichtig: Jeder Einsatz ist getan in O (1) Zeit, da der aktive Punkt uns genau sagt, wo zu gehen, und wir müssen nur ein einzelnes Zeichen am aktiven hinzufügen Punkt. Warum? Weil die anderen Charaktere sind implizit enthalten (Ansonsten wäre der aktive Punkt nicht da, wo er ist).

  • Nach jedem solchen Einsatz dekrementieren wir remainder und folge dem Suffix Link wenn es welche gibt. Wenn nicht, gehen wir zur Wurzel (Regel 3). Wenn wir sind bereits im root, modifizieren wir den aktiven Punkt mit Regel 1. In Jedenfalls dauert es nur O (1) Zeit.

  • Wenn wir während eines dieser Einsätze den Charakter finden, den wir wollen einfügen ist schon da, wir machen nichts und beenden das aktueller Schritt, auch wenn remainder> 0. Der Grund ist, dass jeder Einfügungen, die übrig bleiben, sind Suffixe desjenigen, den wir gerade versucht haben machen. Daher sind sie alle implizit im aktuellen Baum. Die Tatsache Das remainder> 0 stellt sicher, dass wir mit den verbleibenden Suffixen umgehen später.

  • Was ist, wenn am Ende des Algorithmus remainder> 0? Das wird das sein Fall, wenn das Ende des Textes eine Teilzeichenfolge ist, die aufgetreten ist irgendwo vorher. In diesem Fall müssen wir ein zusätzliches Zeichen hinzufügen am Ende der Zeichenfolge, die zuvor nicht aufgetreten ist. In dem Literatur, normalerweise das Dollarzeichen $ wird als Symbol für verwendet Das. Wieso spielt das eine Rolle? -> Wenn wir später den vervollständigten Suffixbaum verwenden, um nach Suffixen zu suchen, müssen wir Übereinstimmungen nur akzeptieren, wenn sie übereinstimmen Ende an einem Blatt. Sonst würden wir viele falsche Übereinstimmungen bekommen, weil es solche gibt viele Saiten implizit enthalten in der Struktur, die nicht tatsächliche Suffixe der Hauptsaite sind. Erzwingen remainder am Ende 0 zu sein, ist im Wesentlichen eine Möglichkeit sicherzustellen, dass alle Suffixe an einem Blattknoten enden. Jedoch, wenn wir den Baum für die Suche verwenden möchten allgemeine Teilstrings, nicht nur Suffixe der letzte Schritt ist in der Tat nicht erforderlich, wie der Kommentar des OP unten andeutet.

  • Was ist also die Komplexität des gesamten Algorithmus? Wenn der Text n ist Zeichen in der Länge, gibt es offensichtlich n Schritte (oder n + 1, wenn wir hinzufügen das Dollarzeichen). In jedem Schritt tun wir nichts (außer Aktualisieren der Variablen), oder wir machen remainder Einsätze, die jeweils O (1) einnehmen Zeit. Schon seit remainder gibt an, wie oft wir nichts getan haben in den vorherigen Schritten, und wird für jede Einfügung, die wir machen, dekrementiert jetzt, die Gesamtzahl der Male, die wir etwas tun, ist genau n (oder n + 1). Daher ist die Gesamtkomplexität O (n).

  • Es gibt jedoch eine kleine Sache, die ich nicht richtig erklärt habe: Es kann vorkommen, dass wir einem Suffix-Link folgen, den aktiven aktualisieren zeigen Sie, und dann finden Sie das active_length Komponente nicht arbeite gut mit dem Neuen active_node. Betrachten Sie zum Beispiel eine Situation so was:

(Die gestrichelten Linien zeigen den Rest des Baumes an. Die gepunktete Linie ist a Suffix-Link.)

Jetzt lass den aktiven Punkt sein (red,'d',3)Es deutet also auf den Ort hin Hinter f auf der defg Kante. Nehmen wir an, wir haben das Notwendige gemacht Updates und folgen Sie nun dem Suffix-Link, um den aktiven Punkt zu aktualisieren gemäß Regel 3. Der neue aktive Punkt ist (green,'d',3). Jedoch, das d-edge geht aus dem grünen Knoten ist de, so hat es nur 2 Figuren. Um den richtigen aktiven Punkt zu finden, sind wir offensichtlich muss dieser Kante zum blauen Knoten folgen und auf zurücksetzen (blue,'f',1).

In einem besonders schlimmen Fall, der active_length könnte so groß sein wie remainder, die so groß wie n sein kann. Und es könnte sehr gut passieren Um den richtigen aktiven Punkt zu finden, müssen wir nicht nur über einen springen interner Knoten, aber vielleicht viele, bis zu n im schlimmsten Fall. Macht das bedeutet, dass der Algorithmus einen versteckten O (n2) Komplexität, weil in jedem Schritt remainder ist in der Regel O (n), und die Nachjustierungen zu dem aktiven Knoten nach dem Folgen eines Suffix-Links könnte auch O (n) sein?

Nein. Der Grund ist, dass wir den aktiven Punkt tatsächlich anpassen müssen (z.B. von grün nach blau wie oben), das bringt uns zu einem neuen Knoten, der hat seinen eigenen Suffix Link und active_length wird reduziert. Wie wir folgen der Kette von Suffix-Links, die wir machen, die restlichen Einsätze, active_length kann nur verringern und die Anzahl der Aktivpunktanpassungen, an denen wir Änderungen vornehmen können Der Weg kann nicht größer sein als active_length jederzeit. Schon seit active_length kann niemals größer sein als remainder, und remainder ist O (n) nicht nur in jedem einzelnen Schritt, sondern die Gesamtsumme der Inkremente jemals gemacht zu remainder im Laufe des gesamten Prozesses ist Auch für O (n) ist die Anzahl der aktiven Punktanpassungen begrenzt durch Auf).


2164
2018-03-01 09:13



Ich habe versucht, den Suffix-Baum mit dem Ansatz zu implementieren, der in Jogojapans Antwort angegeben wurde, aber er hat in einigen Fällen aufgrund der für die Regeln verwendeten Formulierung nicht funktioniert. Außerdem habe ich erwähnt, dass niemand mit diesem Ansatz einen absolut korrekten Suffixbaum implementiert hat. Im Folgenden werde ich eine "Übersicht" über Jogojapan's Antwort mit einigen Änderungen an den Regeln schreiben. Ich werde auch den Fall beschreiben, wenn wir vergessen zu schaffen wichtig Suffix-Links.

Zusätzliche Variablen verwendet

  1. aktiver Punkt - ein Triple (active_node; active_edge; active_length), aus dem hervorgeht, wo wir anfangen müssen, ein neues Suffix einzufügen.
  2. Rest - zeigt die Anzahl der Suffixe, die wir hinzufügen müssen ausdrücklich. Zum Beispiel, wenn unser Wort 'abcaabca' ist, und Rest = 3, bedeutet dies, dass wir 3 letzte Suffixe verarbeiten müssen: bca, ca und ein.

Lassen Sie uns ein Konzept von einem verwenden interner Knoten - alle Knoten außer dem Wurzel und das Blätter sind interne Knoten.

Beobachtung 1

Wenn das letzte Suffix, das wir einfügen müssen, bereits im Baum vorhanden ist, wird der Baum selbst überhaupt nicht geändert (wir aktualisieren nur den active point und remainder).

Beobachtung 2

Wenn irgendwann active_length ist größer oder gleich der Länge der aktuellen Kante (edge_length), bewegen wir unsere active point runter bis edge_length ist streng größer als active_length.

Lassen Sie uns nun die Regeln neu definieren:

Regel 1

Wenn nach einem Einfügen von der aktiver Knoten = Wurzel, das aktive Länge ist größer als 0, dann:

  1. aktiver Knoten wird nicht geändert
  2. aktive Länge wird dekrementiert
  3. aktive Kante wird nach rechts verschoben (zum ersten Zeichen des nächsten Suffix müssen wir einfügen)

Regel 2

Wenn wir ein neues erstellen interner Knoten  ODER Machen Sie einen Inserter von einem interner Knotenund das ist nicht das erste EINE SOLCHE  interner Knoten im aktuellen Schritt verknüpfen wir dann den vorherigen EINE SOLCHE Knoten mit DIES eins bis a Suffix-Link.

Diese Definition der Rule 2 unterscheidet sich von jogojapan ', da hier nicht nur der neu erstellt interne Knoten, aber auch die internen Knoten, aus denen wir eine Einfügung machen.

Regel 3

Nach einem Einfügen von der aktiver Knoten Das ist nicht das Wurzel Knoten, müssen wir den Suffix Link folgen und die aktiver Knoten zu dem Knoten, auf den es zeigt. Wenn keine Suffixverbindung vorhanden ist, legen Sie die Option fest aktiver Knoten zum Wurzel Knoten. In jedem Fall, aktive Kante und aktive Länge bleibe unverändert.

In dieser Definition von Rule 3 Wir betrachten auch die Inserts von Blattknoten (nicht nur Split-Nodes).

Und schließlich, Beobachtung 3:

Wenn das Symbol, das wir dem Baum hinzufügen wollen, bereits am Rande ist, dann sind wir, so Observation 1, nur aktualisieren active point und remainder, den Baum unverändert lassen. ABER wenn es ein gibt interner Knoten markiert als Suffix-Link benötigt, wir müssen diesen Knoten mit unserem Strom verbinden active node durch einen Suffix-Link.

Betrachten wir das Beispiel eines Suffixbaums für cdddcdc wenn wir in einem solchen Fall einen Suffix-Link hinzufügen und wenn wir nicht:

  1. Wenn wir NICHT Verbinden Sie die Knoten über einen Suffix-Link:

    • bevor Sie den letzten Buchstaben hinzufügen c:

    • nach dem Hinzufügen des letzten Buchstabens c:

  2. Wenn wir MACHEN Verbinden Sie die Knoten über einen Suffix-Link:

    • bevor Sie den letzten Buchstaben hinzufügen c:

    • nach dem Hinzufügen des letzten Buchstabens c:

Offensichtlich gibt es keinen signifikanten Unterschied: Im zweiten Fall gibt es zwei weitere Suffix-Links. Aber diese Suffix-Links sind richtigund einer von ihnen - vom blauen Knoten zum roten - ist sehr wichtig für unseren Ansatz mit aktiver Punkt. Das Problem ist, dass wir, wenn wir hier keinen Suffix-Link einfügen, später, wenn wir einige neue Buchstaben zum Baum hinzufügen, das Hinzufügen von einigen Knoten zum Baum aufgrund des Rule 3weil, wenn es keinen Suffixlink gibt, dann müssen wir den active_node zur Wurzel.

Als wir den letzten Buchstaben zum Baum hinzufügten, hatte der rote Knoten existierte bereits bevor wir einen Insert aus dem blauen Knoten gemacht haben (die Kante ist markiert) "c"). Da es eine Einfügung vom blauen Knoten gab, markieren wir sie als Ich brauche einen Suffix-Link. Dann verlassen Sie sich auf die aktiver Punkt Ansatz, der active node wurde auf den roten Knoten gesetzt. Aber wir machen keine Insert aus dem roten Knoten, wie der Buchstabe "c" ist schon am Rande. Bedeutet dies, dass der blaue Knoten ohne Suffix-Link verlassen werden muss? Nein, wir müssen den blauen Knoten mit dem roten durch einen Suffix verbinden. Warum ist es richtig? Weil das aktiver Punkt Approach garantiert, dass wir an einen richtigen Ort gelangen, d. h. an den nächsten Ort, an dem wir eine Insert von a bearbeiten müssen kürzer Suffix.

Schließlich, hier sind meine Implementierungen des Suffix-Baumes:

  1. Java
  2. C ++

Ich hoffe, dass diese "Übersicht" in Verbindung mit Jogojapan's detaillierter Antwort jemandem helfen wird, seinen eigenen Suffix-Baum zu implementieren.


112
2018-01-29 09:57



Danke für das gut erklärte Tutorial von @jogojapan, Habe ich den Algorithmus in Python implementiert.

Ein paar kleinere Probleme, die von @jogojapan erwähnt werden, sind mehr anspruchsvoll als ich erwartet habe und sehr sorgfältig behandelt werden muss. Es kostete mich mehrere Tage, um meine Implementierung zu bekommen robust genug (Ich nehme an). Probleme und Lösungen sind nachfolgend aufgeführt:

  1. Ende mit Remainder > 0 Es stellt sich heraus, dass diese Situation auch passieren kann während des Entfaltungsschrittsnicht nur das Ende des gesamten Algorithmus. Wenn das passiert, können wir den Rest, actnode, actege und actlength lassen unverändert, beenden Sie den aktuellen Entfaltungsschritt und starten Sie einen weiteren Schritt, indem Sie entweder weiterfalten oder entfalten, je nachdem, ob das nächste Zeichen in der ursprünglichen Zeichenfolge auf dem aktuellen Pfad ist oder nicht.

  2. Springe über Knoten: Wenn wir einem Suffix-Link folgen, aktualisieren Sie den aktiven Punkt und stellen Sie dann fest, dass seine active_length-Komponente nicht gut mit dem neuen active_node funktioniert. Wir müssen vorwärts gehen an den richtigen Ort, um zu teilen oder ein Blatt einzufügen. Dieser Prozess könnte sein nicht so einfach weil sich die actlength und actege während des moves ständig ändern, wenn du zurück zum Wurzelknoten, das gespielt und Aktlänge könnte sein falsch wegen dieser Bewegungen. Wir benötigen zusätzliche Variablen, um diese Informationen zu behalten.

    enter image description here

Auf die anderen beiden Probleme wurde irgendwie hingewiesen @managonov

  1. Split könnte entartet sein Wenn Sie versuchen, eine Kante zu teilen, werden Sie manchmal feststellen, dass die Split-Operation auf einem Knoten liegt. In diesem Fall müssen wir nur ein neues Blatt zu diesem Knoten hinzufügen, nehmen Sie es als Standard-Edge-Split-Operation, was bedeutet, dass die Suffix-Links, falls vorhanden, entsprechend gepflegt werden sollten.

  2. Versteckte Suffix Links Es gibt noch einen Sonderfall, der bei Problem 1 und Problem 2. Manchmal müssen wir über mehrere Knoten an den richtigen Punkt springen, um zu teilen übertreffen der richtige Punkt, wenn wir uns bewegen, indem wir den Reststring und die Pfadlabels vergleichen. In diesem Fall wird der Suffix-Link unbeabsichtigt vernachlässigt, falls es einen geben sollte. Dies könnte durch vermieden werden Sich an den richtigen Punkt erinnern beim Vorwärtskommen. Der Suffix-Link sollte beibehalten werden, wenn der Split-Knoten bereits existiert, oder sogar der Problem 1 passiert während eines Entfaltungsschrittes.

Endlich, meine Umsetzung in Python ist wie folgt:

Tipps:  Es beinhaltet ein naives Baum drucken Funktion im obigen Code, der beim Debuggen sehr wichtig ist. Es hat mich sehr gerettet   Zeit und ist bequem für die Suche nach Sonderfällen.


7
2017-08-02 02:35



Meine Intuition ist wie folgt:

Nach k Iterationen der Hauptschleife haben Sie einen Suffixbaum erstellt, der alle Suffixe der vollständigen Zeichenfolge enthält, die in den ersten k Zeichen beginnt.

Zu Beginn bedeutet dies, dass der Suffixbaum einen einzelnen Wurzelknoten enthält, der die gesamte Zeichenfolge darstellt (dies ist das einzige Suffix, das bei 0 beginnt).

Nach len (string) Iterationen haben Sie einen Suffixbaum, der alle Suffixe enthält.

Während der Schleife ist der Schlüssel der aktive Punkt. Meine Vermutung ist, dass dies den tiefsten Punkt im Suffixbaum darstellt, der einem richtigen Suffix der ersten k Zeichen der Zeichenkette entspricht. (Ich denke, richtig bedeutet, dass das Suffix nicht die gesamte Zeichenfolge sein kann.)

Angenommen, Sie haben die Zeichen "abcabc" gesehen. Der aktive Punkt würde den Punkt in dem Baum darstellen, der dem Suffix 'abc' entspricht.

Der aktive Punkt wird durch (Ursprung, erster, letzter) repräsentiert. Dies bedeutet, dass Sie sich an dem Punkt in der Baumstruktur befinden, an den Sie gelangen, indem Sie mit dem Ursprung des Knotens beginnen und dann die Zeichen in der Zeichenfolge [first: last] eingeben.

Wenn Sie ein neues Zeichen hinzufügen, sehen Sie, ob der aktive Punkt immer noch in der vorhandenen Struktur ist. Wenn es dann ist, bist du fertig. Andernfalls müssen Sie dem Suffixbaum am aktiven Punkt einen neuen Knoten hinzufügen, auf die nächstkleinere Übereinstimmung zurückgreifen und erneut prüfen.

Anmerkung 1: Die Suffixzeiger geben eine Verbindung zu der nächst kürzesten Übereinstimmung für jeden Knoten.

Anmerkung 2: Wenn Sie einen neuen Knoten und einen neuen Fallback hinzufügen, fügen Sie einen neuen Suffixzeiger für den neuen Knoten hinzu. Das Ziel für diesen Suffixzeiger ist der Knoten am gekürzten aktiven Punkt. Dieser Knoten ist entweder bereits vorhanden oder wird bei der nächsten Iteration dieser Fallback-Schleife erstellt.

Anmerkung 3: Der Heiligsprechungsteil spart einfach Zeit beim Überprüfen des aktiven Punktes. Angenommen, Sie haben immer Ursprung = 0 verwendet und zuerst und zuletzt geändert. Um den aktiven Punkt zu überprüfen, müssten Sie jedes Mal den Suffixbaum entlang aller Zwischenknoten verfolgen. Es ist sinnvoll, das Ergebnis der Verfolgung dieses Pfades zu cachen, indem nur die Entfernung vom letzten Knoten aufgezeichnet wird.

Können Sie ein Codebeispiel dazu geben, was Sie meinen, indem Sie Begrenzungsvariablen "fixieren"?

Gesundheitswarnung: Ich fand auch diesen Algorithmus besonders schwierig zu verstehen, also bitte erkennen Sie, dass diese Intuition wahrscheinlich in allen wichtigen Details falsch ist ...


6
2018-02-26 20:16



Hallo ich habe versucht, die oben erläuterte Implementierung in Ruby zu implementieren, bitte überprüfen Sie es. es scheint gut zu funktionieren.

Der einzige Unterschied in der Implementierung ist, dass ich versucht habe, das Edge-Objekt zu verwenden, anstatt nur Symbole zu verwenden.

es ist auch anwesend bei https://gist.github.com/suchitpuri/9304856

    require 'pry'


class Edge
    attr_accessor :data , :edges , :suffix_link
    def initialize data
        @data = data
        @edges = []
        @suffix_link = nil
    end

    def find_edge element
        self.edges.each do |edge|
            return edge if edge.data.start_with? element
        end
        return nil
    end
end

class SuffixTrees
    attr_accessor :root , :active_point , :remainder , :pending_prefixes , :last_split_edge , :remainder

    def initialize
        @root = Edge.new nil
        @active_point = { active_node: @root , active_edge: nil , active_length: 0}
        @remainder = 0
        @pending_prefixes = []
        @last_split_edge = nil
        @remainder = 1
    end

    def build string
        string.split("").each_with_index do |element , index|


            add_to_edges @root , element        

            update_pending_prefix element                           
            add_pending_elements_to_tree element
            active_length = @active_point[:active_length]

            # if(@active_point[:active_edge] && @active_point[:active_edge].data && @active_point[:active_edge].data[0..active_length-1] ==  @active_point[:active_edge].data[active_length..@active_point[:active_edge].data.length-1])
            #   @active_point[:active_edge].data = @active_point[:active_edge].data[0..active_length-1]
            #   @active_point[:active_edge].edges << Edge.new(@active_point[:active_edge].data)
            # end

            if(@active_point[:active_edge] && @active_point[:active_edge].data && @active_point[:active_edge].data.length == @active_point[:active_length]  )
                @active_point[:active_node] =  @active_point[:active_edge]
                @active_point[:active_edge] = @active_point[:active_node].find_edge(element[0])
                @active_point[:active_length] = 0
            end
        end
    end

    def add_pending_elements_to_tree element

        to_be_deleted = []
        update_active_length = false
        # binding.pry
        if( @active_point[:active_node].find_edge(element[0]) != nil)
            @active_point[:active_length] = @active_point[:active_length] + 1               
            @active_point[:active_edge] = @active_point[:active_node].find_edge(element[0]) if @active_point[:active_edge] == nil
            @remainder = @remainder + 1
            return
        end



        @pending_prefixes.each_with_index do |pending_prefix , index|

            # binding.pry           

            if @active_point[:active_edge] == nil and @active_point[:active_node].find_edge(element[0]) == nil

                @active_point[:active_node].edges << Edge.new(element)

            else

                @active_point[:active_edge] = node.find_edge(element[0]) if @active_point[:active_edge]  == nil

                data = @active_point[:active_edge].data
                data = data.split("")               

                location = @active_point[:active_length]


                # binding.pry
                if(data[0..location].join == pending_prefix or @active_point[:active_node].find_edge(element) != nil )                  


                else #tree split    
                    split_edge data , index , element
                end

            end
        end 
    end



    def update_pending_prefix element
        if @active_point[:active_edge] == nil
            @pending_prefixes = [element]
            return

        end

        @pending_prefixes = []

        length = @active_point[:active_edge].data.length
        data = @active_point[:active_edge].data
        @remainder.times do |ctr|
                @pending_prefixes << data[-(ctr+1)..data.length-1]
        end

        @pending_prefixes.reverse!

    end

    def split_edge data , index , element
        location = @active_point[:active_length]
        old_edges = []
        internal_node = (@active_point[:active_edge].edges != nil)

        if (internal_node)
            old_edges = @active_point[:active_edge].edges 
            @active_point[:active_edge].edges = []
        end

        @active_point[:active_edge].data = data[0..location-1].join                 
        @active_point[:active_edge].edges << Edge.new(data[location..data.size].join)


        if internal_node
            @active_point[:active_edge].edges << Edge.new(element)
        else
            @active_point[:active_edge].edges << Edge.new(data.last)        
        end

        if internal_node
            @active_point[:active_edge].edges[0].edges = old_edges
        end


        #setup the suffix link
        if @last_split_edge != nil and @last_split_edge.data.end_with?@active_point[:active_edge].data 

            @last_split_edge.suffix_link = @active_point[:active_edge] 
        end

        @last_split_edge = @active_point[:active_edge]

        update_active_point index

    end


    def update_active_point index
        if(@active_point[:active_node] == @root)
            @active_point[:active_length] = @active_point[:active_length] - 1
            @remainder = @remainder - 1
            @active_point[:active_edge] = @active_point[:active_node].find_edge(@pending_prefixes.first[index+1])
        else
            if @active_point[:active_node].suffix_link != nil
                @active_point[:active_node] = @active_point[:active_node].suffix_link               
            else
                @active_point[:active_node] = @root
            end 
            @active_point[:active_edge] = @active_point[:active_node].find_edge(@active_point[:active_edge].data[0])
            @remainder = @remainder - 1     
        end
    end

    def add_to_edges root , element     
        return if root == nil
        root.data = root.data + element if(root.data and root.edges.size == 0)
        root.edges.each do |edge|
            add_to_edges edge , element
        end
    end
end

suffix_tree = SuffixTrees.new
suffix_tree.build("abcabxabcd")
binding.pry

3
2018-03-02 10:54



@jogojapan hast du tolle Erklärung und Visualisierung gebracht. Aber wie @makagonov erwähnt hat, fehlen einige Regeln bezüglich der Einstellung von Suffix-Links. Es ist schön sichtbar, wenn man Schritt für Schritt weitergeht http://brenden.github.io/ukkonen-animation/ durch das Wort "Aabaaabb". Wenn Sie von Schritt 10 zu Schritt 11 gehen, gibt es keine Suffixverbindung von Knoten 5 zu Knoten 2, aber der aktive Punkt bewegt sich plötzlich dorthin.

@makagonov da ich in der Java-Welt lebe, habe ich auch versucht, Ihrer Implementierung zu folgen, um den ST-Aufbau-Workflow zu erfassen, aber es war schwer für mich wegen:

  • Kombinieren von Kanten mit Knoten
  • Verwenden von Indexzeigern anstelle von Referenzen
  • bricht Aussagen ab;
  • Anweisungen fortsetzen;

Also habe ich eine solche Implementierung in Java gefunden, die hoffentlich alle Schritte auf klarere Weise widerspiegelt und die Lernzeit für andere Java-Leute verkürzt:

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class ST {

  public class Node {
    private final int id;
    private final Map<Character, Edge> edges;
    private Node slink;

    public Node(final int id) {
        this.id = id;
        this.edges = new HashMap<>();
    }

    public void setSlink(final Node slink) {
        this.slink = slink;
    }

    public Map<Character, Edge> getEdges() {
        return this.edges;
    }

    public Node getSlink() {
        return this.slink;
    }

    public String toString(final String word) {
        return new StringBuilder()
                .append("{")
                .append("\"id\"")
                .append(":")
                .append(this.id)
                .append(",")
                .append("\"slink\"")
                .append(":")
                .append(this.slink != null ? this.slink.id : null)
                .append(",")
                .append("\"edges\"")
                .append(":")
                .append(edgesToString(word))
                .append("}")
                .toString();
    }

    private StringBuilder edgesToString(final String word) {
        final StringBuilder edgesStringBuilder = new StringBuilder();
        edgesStringBuilder.append("{");
        for(final Map.Entry<Character, Edge> entry : this.edges.entrySet()) {
            edgesStringBuilder.append("\"")
                    .append(entry.getKey())
                    .append("\"")
                    .append(":")
                    .append(entry.getValue().toString(word))
                    .append(",");
        }
        if(!this.edges.isEmpty()) {
            edgesStringBuilder.deleteCharAt(edgesStringBuilder.length() - 1);
        }
        edgesStringBuilder.append("}");
        return edgesStringBuilder;
    }

    public boolean contains(final String word, final String suffix) {
        return !suffix.isEmpty()
                && this.edges.containsKey(suffix.charAt(0))
                && this.edges.get(suffix.charAt(0)).contains(word, suffix);
    }
  }

  public class Edge {
    private final int from;
    private final int to;
    private final Node next;

    public Edge(final int from, final int to, final Node next) {
        this.from = from;
        this.to = to;
        this.next = next;
    }

    public int getFrom() {
        return this.from;
    }

    public int getTo() {
        return this.to;
    }

    public Node getNext() {
        return this.next;
    }

    public int getLength() {
        return this.to - this.from;
    }

    public String toString(final String word) {
        return new StringBuilder()
                .append("{")
                .append("\"content\"")
                .append(":")
                .append("\"")
                .append(word.substring(this.from, this.to))
                .append("\"")
                .append(",")
                .append("\"next\"")
                .append(":")
                .append(this.next != null ? this.next.toString(word) : null)
                .append("}")
                .toString();
    }

    public boolean contains(final String word, final String suffix) {
        if(this.next == null) {
            return word.substring(this.from, this.to).equals(suffix);
        }
        return suffix.startsWith(word.substring(this.from,
                this.to)) && this.next.contains(word, suffix.substring(this.to - this.from));
    }
  }

  public class ActivePoint {
    private final Node activeNode;
    private final Character activeEdgeFirstCharacter;
    private final int activeLength;

    public ActivePoint(final Node activeNode,
                       final Character activeEdgeFirstCharacter,
                       final int activeLength) {
        this.activeNode = activeNode;
        this.activeEdgeFirstCharacter = activeEdgeFirstCharacter;
        this.activeLength = activeLength;
    }

    private Edge getActiveEdge() {
        return this.activeNode.getEdges().get(this.activeEdgeFirstCharacter);
    }

    public boolean pointsToActiveNode() {
        return this.activeLength == 0;
    }

    public boolean activeNodeIs(final Node node) {
        return this.activeNode == node;
    }

    public boolean activeNodeHasEdgeStartingWith(final char character) {
        return this.activeNode.getEdges().containsKey(character);
    }

    public boolean activeNodeHasSlink() {
        return this.activeNode.getSlink() != null;
    }

    public boolean pointsToOnActiveEdge(final String word, final char character) {
        return word.charAt(this.getActiveEdge().getFrom() + this.activeLength) == character;
    }

    public boolean pointsToTheEndOfActiveEdge() {
        return this.getActiveEdge().getLength() == this.activeLength;
    }

    public boolean pointsAfterTheEndOfActiveEdge() {
        return this.getActiveEdge().getLength() < this.activeLength;
    }

    public ActivePoint moveToEdgeStartingWithAndByOne(final char character) {
        return new ActivePoint(this.activeNode, character, 1);
    }

    public ActivePoint moveToNextNodeOfActiveEdge() {
        return new ActivePoint(this.getActiveEdge().getNext(), null, 0);
    }

    public ActivePoint moveToSlink() {
        return new ActivePoint(this.activeNode.getSlink(),
                this.activeEdgeFirstCharacter,
                this.activeLength);
    }

    public ActivePoint moveTo(final Node node) {
        return new ActivePoint(node, this.activeEdgeFirstCharacter, this.activeLength);
    }

    public ActivePoint moveByOneCharacter() {
        return new ActivePoint(this.activeNode,
                this.activeEdgeFirstCharacter,
                this.activeLength + 1);
    }

    public ActivePoint moveToEdgeStartingWithAndByActiveLengthMinusOne(final Node node,
                                                                       final char character) {
        return new ActivePoint(node, character, this.activeLength - 1);
    }

    public ActivePoint moveToNextNodeOfActiveEdge(final String word, final int index) {
        return new ActivePoint(this.getActiveEdge().getNext(),
                word.charAt(index - this.activeLength + this.getActiveEdge().getLength()),
                this.activeLength - this.getActiveEdge().getLength());
    }

    public void addEdgeToActiveNode(final char character, final Edge edge) {
        this.activeNode.getEdges().put(character, edge);
    }

    public void splitActiveEdge(final String word,
                                final Node nodeToAdd,
                                final int index,
                                final char character) {
        final Edge activeEdgeToSplit = this.getActiveEdge();
        final Edge splittedEdge = new Edge(activeEdgeToSplit.getFrom(),
                activeEdgeToSplit.getFrom() + this.activeLength,
                nodeToAdd);
        nodeToAdd.getEdges().put(word.charAt(activeEdgeToSplit.getFrom() + this.activeLength),
                new Edge(activeEdgeToSplit.getFrom() + this.activeLength,
                        activeEdgeToSplit.getTo(),
                        activeEdgeToSplit.getNext()));
        nodeToAdd.getEdges().put(character, new Edge(index, word.length(), null));
        this.activeNode.getEdges().put(this.activeEdgeFirstCharacter, splittedEdge);
    }

    public Node setSlinkTo(final Node previouslyAddedNodeOrAddedEdgeNode,
                           final Node node) {
        if(previouslyAddedNodeOrAddedEdgeNode != null) {
            previouslyAddedNodeOrAddedEdgeNode.setSlink(node);
        }
        return node;
    }

    public Node setSlinkToActiveNode(final Node previouslyAddedNodeOrAddedEdgeNode) {
        return setSlinkTo(previouslyAddedNodeOrAddedEdgeNode, this.activeNode);
    }
  }

  private static int idGenerator;

  private final String word;
  private final Node root;
  private ActivePoint activePoint;
  private int remainder;

  public ST(final String word) {
    this.word = word;
    this.root = new Node(idGenerator++);
    this.activePoint = new ActivePoint(this.root, null, 0);
    this.remainder = 0;
    build();
  }

  private void build() {
    for(int i = 0; i < this.word.length(); i++) {
        add(i, this.word.charAt(i));
    }
  }

  private void add(final int index, final char character) {
    this.remainder++;
    boolean characterFoundInTheTree = false;
    Node previouslyAddedNodeOrAddedEdgeNode = null;
    while(!characterFoundInTheTree && this.remainder > 0) {
        if(this.activePoint.pointsToActiveNode()) {
            if(this.activePoint.activeNodeHasEdgeStartingWith(character)) {
                activeNodeHasEdgeStartingWithCharacter(character, previouslyAddedNodeOrAddedEdgeNode);
                characterFoundInTheTree = true;
            }
            else {
                if(this.activePoint.activeNodeIs(this.root)) {
                    rootNodeHasNotEdgeStartingWithCharacter(index, character);
                }
                else {
                    previouslyAddedNodeOrAddedEdgeNode = internalNodeHasNotEdgeStartingWithCharacter(index,
                            character, previouslyAddedNodeOrAddedEdgeNode);
                }
            }
        }
        else {
            if(this.activePoint.pointsToOnActiveEdge(this.word, character)) {
                activeEdgeHasCharacter();
                characterFoundInTheTree = true;
            }
            else {
                if(this.activePoint.activeNodeIs(this.root)) {
                    previouslyAddedNodeOrAddedEdgeNode = edgeFromRootNodeHasNotCharacter(index,
                            character,
                            previouslyAddedNodeOrAddedEdgeNode);
                }
                else {
                    previouslyAddedNodeOrAddedEdgeNode = edgeFromInternalNodeHasNotCharacter(index,
                            character,
                            previouslyAddedNodeOrAddedEdgeNode);
                }
            }
        }
    }
  }

  private void activeNodeHasEdgeStartingWithCharacter(final char character,
                                                    final Node previouslyAddedNodeOrAddedEdgeNode) {
    this.activePoint.setSlinkToActiveNode(previouslyAddedNodeOrAddedEdgeNode);
    this.activePoint = this.activePoint.moveToEdgeStartingWithAndByOne(character);
    if(this.activePoint.pointsToTheEndOfActiveEdge()) {
        this.activePoint = this.activePoint.moveToNextNodeOfActiveEdge();
    }
  }

  private void rootNodeHasNotEdgeStartingWithCharacter(final int index, final char character) {
    this.activePoint.addEdgeToActiveNode(character, new Edge(index, this.word.length(), null));
    this.activePoint = this.activePoint.moveTo(this.root);
    this.remainder--;
    assert this.remainder == 0;
  }

  private Node internalNodeHasNotEdgeStartingWithCharacter(final int index,
                                                         final char character,
                                                         Node previouslyAddedNodeOrAddedEdgeNode) {
    this.activePoint.addEdgeToActiveNode(character, new Edge(index, this.word.length(), null));
    previouslyAddedNodeOrAddedEdgeNode = this.activePoint.setSlinkToActiveNode(previouslyAddedNodeOrAddedEdgeNode);
    if(this.activePoint.activeNodeHasSlink()) {
        this.activePoint = this.activePoint.moveToSlink();
    }
    else {
        this.activePoint = this.activePoint.moveTo(this.root);
    }
    this.remainder--;
    return previouslyAddedNodeOrAddedEdgeNode;
  }

  private void activeEdgeHasCharacter() {
    this.activePoint = this.activePoint.moveByOneCharacter();
    if(this.activePoint.pointsToTheEndOfActiveEdge()) {
        this.activePoint = this.activePoint.moveToNextNodeOfActiveEdge();
    }
  }

  private Node edgeFromRootNodeHasNotCharacter(final int index,
                                             final char character,
                                             Node previouslyAddedNodeOrAddedEdgeNode) {
    final Node newNode = new Node(idGenerator++);
    this.activePoint.splitActiveEdge(this.word, newNode, index, character);
    previouslyAddedNodeOrAddedEdgeNode = this.activePoint.setSlinkTo(previouslyAddedNodeOrAddedEdgeNode, newNode);
    this.activePoint = this.activePoint.moveToEdgeStartingWithAndByActiveLengthMinusOne(this.root,
            this.word.charAt(index - this.remainder + 2));
    this.activePoint = walkDown(index);
    this.remainder--;
    return previouslyAddedNodeOrAddedEdgeNode;
  }

  private Node edgeFromInternalNodeHasNotCharacter(final int index,
                                                 final char character,
                                                 Node previouslyAddedNodeOrAddedEdgeNode) {
    final Node newNode = new Node(idGenerator++);
    this.activePoint.splitActiveEdge(this.word, newNode, index, character);
    previouslyAddedNodeOrAddedEdgeNode = this.activePoint.setSlinkTo(previouslyAddedNodeOrAddedEdgeNode, newNode);
    if(this.activePoint.activeNodeHasSlink()) {
        this.activePoint = this.activePoint.moveToSlink();
    }
    else {
        this.activePoint = this.activePoint.moveTo(this.root);
    }
    this.activePoint = walkDown(index);
    this.remainder--;
    return previouslyAddedNodeOrAddedEdgeNode;
  }

  private ActivePoint walkDown(final int index) {
    while(!this.activePoint.pointsToActiveNode()
            && (this.activePoint.pointsToTheEndOfActiveEdge() || this.activePoint.pointsAfterTheEndOfActiveEdge())) {
        if(this.activePoint.pointsAfterTheEndOfActiveEdge()) {
            this.activePoint = this.activePoint.moveToNextNodeOfActiveEdge(this.word, index);
        }
        else {
            this.activePoint = this.activePoint.moveToNextNodeOfActiveEdge();
        }
    }
    return this.activePoint;
  }

  public String toString(final String word) {
    return this.root.toString(word);
  }

  public boolean contains(final String suffix) {
    return this.root.contains(this.word, suffix);
  }

  public static void main(final String[] args) {
    final String[] words = {
            "abcabcabc$",
            "abc$",
            "abcabxabcd$",
            "abcabxabda$",
            "abcabxad$",
            "aabaaabb$",
            "aababcabcd$",
            "ababcabcd$",
            "abccba$",
            "mississipi$",
            "abacabadabacabae$",
            "abcabcd$",
            "00132220$"
    };
    Arrays.stream(words).forEach(word -> {
        System.out.println("Building suffix tree for word: " + word);
        final ST suffixTree = new ST(word);
        System.out.println("Suffix tree: " + suffixTree.toString(word));
        for(int i = 0; i < word.length() - 1; i++) {
            assert suffixTree.contains(word.substring(i)) : word.substring(i);
        }
    });
  }
}

2
2018-04-21 14:22