wake-up-neo.net

Der Suffix-Tree-Algorithmus von Ukkonen in Klartext

Ich fühle mich an dieser Stelle ein bisschen dick. Ich habe tagelang versucht, mich ganz mit der Suffix-Baum-Konstruktion zu beschäftigen, aber da ich keinen mathematischen Hintergrund habe, entziehen sich viele der Erklärungen mir, da sie anfangen, die mathematische Symbologie übermäßig zu nutzen. Die beste Erklärung, die ich gefunden habe, ist Schnelle Suche nach Zeichenfolgen mit Suffixbäumen, aber er geht auf verschiedene Punkte und einige Aspekte des Algorithmus ein bleibt unklar.

Eine schrittweise 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 finden Sie hier Ukkonens Artikel zum Algorithmus: http://www.cs.helsinki.fi/u/ukkonen/SuffixT1withFigs.pdf

Mein bisheriges Grundverständnis:

  • Ich muss jedes Präfix P einer gegebenen Zeichenfolge T durchlaufen
  • Ich muss durch jedes Suffix S im Präfix P iterieren und das zum Baum hinzufügen
  • Um dem Baum das Suffix S hinzuzufügen, muss ich jedes Zeichen in S durchlaufen, wobei die Iteration darin besteht, entweder einen vorhandenen Zweig entlangzulaufen, der mit der gleichen Menge von Zeichen C in S beginnt, und möglicherweise eine Kante in untergeordnete Knoten aufzuteilen, wenn ich Erreiche ein anderes Zeichen im Suffix, OR, wenn es keine passende Kante zum Abstieg gab. Wenn für C keine passende Kante gefunden wird, wird für C eine neue Blattkante erstellt.

Der grundlegende Algorithmus scheint O (n zu sein2), wie in den meisten Erklärungen ausgeführt, müssen wir, da wir alle Präfixe durchgehen müssen, für jedes Präfix die einzelnen Suffixe durchgehen. Ukkonens Algorithmus ist anscheinend einzigartig, da er eine Suffix-Zeigertechnik verwendet, obwohl ich denke , dass das ist, was ich nur schwer verstehe.

Ich habe auch Probleme beim Verstehen:

  • genau wann und wie der "aktive Punkt" zugewiesen, verwendet und geändert wird
  • was ist mit dem Kanonisierungsaspekt des Algorithmus los?
  • Warum müssen die Implementierungen, die ich gesehen habe, die verwendeten Begrenzungsvariablen "korrigieren"?

Hier ist der fertige C # Quellcode. Es funktioniert nicht nur korrekt, sondern unterstützt auch die automatische Kanonisierung und erstellt eine schönere Textgrafik der Ausgabe. Quellcode und Beispielausgabe finden Sie unter:

https://Gist.github.com/2373868


Update 04.11.2017

Nach vielen Jahren habe ich eine neue Verwendung für Suffix-Bäume gefunden und den Algorithmus in JavaScript implementiert. Das Wesentliche ist unten. Es sollte fehlerfrei sein. Kopieren Sie es vom selben Speicherort in eine js-Datei, npm install chalk, und führen Sie dann node.js aus, um eine farbenfrohe Ausgabe zu erhalten. Es gibt eine abgespeckte Version im selben Gist, ohne den Debug-Code.

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

1048
Nathan Ridley

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

Zunächst einige vorläufige Aussagen.

  1. Was wir bauen, istim Grunde genommenwie ein Suchversuch. Es gibt also einen Wurzelknoten, von dem Kanten ausgehen und zu neuen Knoten führen, und weitere Kanten, die von diesen ausgehen und so weiter

  2. Aber: Anders als in einem Suchversuch sind die Kantenbeschriftungen keine einzelnen Zeichen. Stattdessen wird jede Kante mit einem Paar von Ganzzahlen [from,to] beschriftet. Dies sind Hinweise auf den Text. In diesem Sinne trägt jede Kante eine Zeichenfolgenbezeichnung von beliebiger Länge, benötigt jedoch nur O(1) Leerzeichen (zwei Zeiger).

Grundprinzip

Ich möchte zunächst zeigen, wie der Suffix-Baum einer besonders einfachen Zeichenfolge erstellt wird, einer Zeichenfolge ohne wiederholte Zeichen:

abc

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

Wir beginnen also mitleftund fügen zuerst nur das einzelne Zeichen a ein, indem wir eine Kante vom Wurzelknoten (links) zu einem Blatt erstellen und es beschriften als [0,#], was bedeutet, dass die Kante die Teilzeichenfolge darstellt, die an Position 0 beginnt und andem aktuellen Endeendet. Ich verwende das Symbol #, umdas aktuelle Endezu bedeuten, das sich an Position 1 befindet (direkt nach a).

Wir haben also einen ersten Baum, der so aussieht:

Und was es bedeutet, ist das:

Jetzt fahren wir mit Position 2 fort (direkt nach b). nser Ziel bei jedem Schritt ​​ist es, alle Suffixe bis zur aktuellen Position einzufügen. Wir machen das durch

  • erweitern des vorhandenen a- Edge 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 Edge-Darstellung für ab ist dasselbe wie im ursprünglichen Baum: [0,#]. Ihre Bedeutung hat sich automatisch geändert, da wir die aktuelle Position # von 1 auf 2 aktualisiert haben.
  • Jede Kante belegt O(1) Platz, da sie nur aus zwei Zeigern im Text besteht, unabhängig davon, wie viele Zeichen sie darstellt.

Als Nächstes erhöhen wir die Position erneut und aktualisieren den Baum, indem wir an jede vorhandene Kante eine c anhängen und eine neue Kante für das neue Suffix c einfügen.

In unserer Darstellung sieht das so aus

Und was es bedeutet, ist:

Wir beobachten:

  • Der Baum ist der richtige Suffixbaumbis zur aktuellen Positionnach jedem Schritt
  • Es gibt so viele Schritte wie Zeichen im Text
  • Der Arbeitsaufwand in jedem Schritt beträgt O (1), da alle vorhandenen Kanten automatisch aktualisiert werden, indem # erhöht wird. Das Einfügen der einen neuen Kante für das letzte Zeichen kann in O(1) erfolgen. Für eine Zeichenfolge der Länge n ist daher nur O(n) Zeit erforderlich.

Erste Erweiterung: Einfache Wiederholungen

Das funktioniert natürlich nur deshalb so gut, weil unsere Saite keine Wiederholungen enthält. Wir betrachten nun eine realistischere Zeichenfolge:

abcabxabcd

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

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

Schritt 4: Wir verschieben # auf Position 4. Dadurch werden implizit alle vorhandenen Kanten folgendermaßen aktualisiert:

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

Bevor wir dies tun, führen wir zwei weitere Variablen (zusätzlich zu #) ein, die natürlich die ganze Zeit dort waren, aber bisher noch nicht verwendet wurden:

  • Der aktive Punkt, der ein dreifacher (active_node,active_Edge,active_length) ist
  • remainder, eine Ganzzahl, die angibt, wie viele neue Suffixe eingefügt werden müssen

Die genaue Bedeutung dieser beiden wird in Kürze klar, aber jetzt sagen wir einfach:

  • In dem einfachen Beispiel abc war der aktive Punkt immer (root,'\0x',0), d. H. active_node war der Wurzelknoten, active_Edge wurde als Nullzeichen '\0x' angegeben und active_length war Null. Dies hatte zur Folge, dass die eine neue Kante, die wir in jedem Schritt eingefügt haben, am Stammknoten als frisch erstellte Kante eingefügt wurde. Wir werden gleich sehen, warum ein Triple erforderlich ist, um diese Informationen darzustellen.
  • remainder wurde zu Beginn jedes Schritts immer auf 1 gesetzt. Die Bedeutung davon war, dass die Anzahl der Suffixe, die wir am Ende jedes Schritts aktiv einfügen mussten, 1 war (immer nur das letzte Zeichen).

Das wird sich jetzt ändern. Wenn wir das aktuelle letzte Zeichen a im Stammverzeichnis einfügen, stellen wir fest, dass bereits eine ausgehende Flanke vorhanden ist, die mit a beginnt, insbesondere: abca. In einem solchen Fall machen wir Folgendes:

  • Wir nicht ​​fügen einen neuen Edge [4,#] am Wurzelknoten ein. Stattdessen stellen wir einfach fest, dass sich das Suffix a bereits in unserem Baum befindet. Es endet in der Mitte einer längeren Kante, aber das stört uns nicht. Wir lassen die Dinge einfach so wie sie sind.
  • Wir setzen den aktiven Punkt ​​auf (root,'a',1). Das heißt, der aktive Punkt befindet sich jetzt irgendwo in der Mitte der ausgehenden Kante des Stammknotens, die mit a beginnt, und zwar nach Position 1 auf dieser Kante. Wir bemerken, dass der Edge einfach durch sein erstes Zeichen a spezifiziert wird. Das reicht aus, weil esnur eineKante geben kann, die mit einem bestimmten Zeichen beginnt (bestätigen Sie dies, nachdem Sie die gesamte Beschreibung durchgelesen haben).
  • Wir erhöhen auch remainder, so dass es zu Beginn des nächsten Schritts 2 sein wird.

Beobachtung: Wenn das endgültige Suffix, das wir einfügen müssen, bereits im Baum vorhanden ist, ist der Baum selbst nicht geändert ​​überhaupt (wir aktualisieren Sie nur den aktiven Punkt und remainder). Der Baum ist dann keine genaue Darstellung des Suffixbaumsbis zur aktuellen Positionmehr, sondern enthält ​​alle Suffixe (weil das Finale Suffix a ist enthaltenimplizit). Abgesehen von der Aktualisierung der Variablen (die alle eine feste Länge haben, also 0 (1)) wurde in diesem Schritt keine Arbeit ​​erledigt.

Schritt 5: Wir aktualisieren die aktuelle Position # auf 5. Dadurch wird der Baum automatisch folgendermaßen aktualisiert:

Und weil remainder 2 ist, müssen wir zwei abschließende Suffixe der aktuellen Position einfügen: ab und b. Dies liegt im Grunde daran, dass:

  • Das Suffix a aus dem vorherigen Schritt wurde nie richtig eingefügt. Es ist alsogeblieben, und seit wir einen Schritt vorangekommen sind, ist es von a zu ab gewachsen.
  • Und wir müssen die neue letzte Kante b einfügen.

In der Praxis bedeutet dies, dass wir zu dem aktiven Punkt gehen (der auf den a hinter dem abcab-Rand zeigt) und das aktuelle Endzeichen b einfügen. Aber: Wieder stellt sich heraus, dass b auch bereits an derselben Kante vorhanden ist.

Also ändern wir den Baum nicht. Wir einfach:

  • Aktualisieren Sie den aktiven Punkt auf (root,'a',2) (derselbe Knoten und Edge wie zuvor, aber jetzt zeigen wir hinter b).
  • Erhöhen Sie die Variable remainder auf 3, da wir die letzte Kante aus dem vorherigen Schritt noch nicht richtig eingefügt haben und auch die aktuelle letzte Kante nicht einfügen.

Um es klar auszudrücken: Wir mussten ab und b in den aktuellen Schritt einfügen, aber da ab bereits gefunden wurde, haben wir den aktiven Punkt aktualisiert und nicht einmal versucht, b einzufügen. Warum? Denn wenn ab im Baum ist, muss jedes Suffix davon (einschließlich b) auch im Baum sein. Vielleicht nurimplizit, aber es muss da sein, wegen der Art und Weise, wie wir den Baum bisher gebaut haben.

Wir fahren mit Schritt 6 fort, indem wir # erhöhen. Der Baum wird automatisch aktualisiert auf:

Da remainder ist, müssen wir abx, bx und x einfügen. Der aktive Punkt sagt uns, wo ab endet, also müssen wir nur dorthin springen und das x einfügen. Da x noch nicht vorhanden ist, teilen wir die Kante abcabx und fügen einen internen Knoten ein:

Die Kantendarstellungen sind weiterhin Zeiger auf den Text, sodass das Teilen und Einfügen eines internen Knotens in O(1) Zeit erfolgen kann.

Also haben wir uns mit abx befasst und remainder auf 2 dekrementiert. Jetzt müssen wir das nächste verbleibende Suffix einfügen, bx. Aber bevor wir das tun, müssen wir den aktiven Punkt aktualisieren. Die Regel dafür wird nach dem Aufteilen und Einfügen einer Kante Regel 1 genannt und gilt immer dann, wenn der active_node root ist (für andere Fälle werden wir die Regel 3 weiter unten lernen). Hier ist Regel 1:

Nach dem Einfügen von root

  • active_node bleibt root
  • active_Edge wird auf das erste Zeichen des neuen Suffixes gesetzt, das wir einfügen müssen, d. h. b
  • active_length wird um 1 reduziert

Daher gibt das neue Aktivpunkt-Tripel (root,'b',1) an, dass die nächste Einfügung an der Kante bcabx hinter 1 Zeichen erfolgen muss, d. H. Hinter b. Wir können die Einfügemarke in der Zeit O(1) identifizieren und prüfen, ob x bereits vorhanden ist oder nicht. Wenn es vorhanden wäre, würden wir den aktuellen Schritt beenden und alles so lassen, wie es ist. Da x nicht vorhanden ist, wird es durch Teilen der Kante eingefügt:

Dies hat wiederum O(1) Zeit in Anspruch genommen und wir aktualisieren remainder auf 1 und den aktiven Punkt auf (root,'x',0), wie in Regel 1 angegeben.

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

Wenn wir eine Kante teilen und einen neuen Knoten einfügen und diesnicht der erste Knotenist, der während des aktuellen Schritts erstellt wurde, verbinden wir den zuvor eingefügten Knoten und den neuen Knoten durch ein spezieller Zeiger, ein Suffix Link. Wir werden später sehen, warum das nützlich ist. Folgendes erhalten wir, der Suffix-Link wird als gepunktete Kante dargestellt:

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

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

Wir fahren mit Schritt 7 fort, indem wir # = 7 setzen, wodurch wie immer automatisch das nächste Zeichen a an alle Blattränder angehängt wird. Dann versuchen wir, das neue Endzeichen an der aktiven Stelle (der Wurzel) einzufügen und stellen fest, dass es bereits vorhanden ist. So beenden wir den aktuellen Schritt, ohne etwas einzufügen, und aktualisieren den aktiven Punkt auf (root,'a',1).

In Schritt 8, # = 8 hängen wir b an, und wie zuvor gesehen, bedeutet dies nur, dass wir den aktiven Punkt auf (root,'a',2) aktualisieren und remainder erhöhen, ohne etwas anderes zu tun, da b bereits vorhanden ist. Allerdings wir bemerken (in O(1) Zeit), dass der aktive Punkt jetzt am Ende einer Kante ist. Wir reflektieren dies, indem wir es auf (node1,'\0x',0) zurücksetzen. Hier verwende ich node1, um auf den internen Knoten zu verweisen, an dem die ab-Kante endet.

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

Zweite Erweiterung: Verwenden von Suffix-Links

Wie immer hängt das #-Update c automatisch an die Blattränder und wir gehen zum aktiven Punkt, um zu sehen, ob wir 'c' einfügen können. Es hat sich herausgestellt, dass 'c' bereits an diesem Edge vorhanden ist. Daher setzen wir den aktiven Punkt auf (node1,'c',1), inkrementieren remainder und tun nichts anderes.

Jetzt müssen wir in Schritt # = 1, remainder is 4 zuerst abcd (das von vor 3 Schritten noch vorhanden ist) einfügen, indem wir d am aktiven Punkt einfügen.

Beim Versuch, d am aktiven Punkt einzufügen, wird die Kante in der Zeit O(1) aufgeteilt:

Der active_node, von dem aus die Teilung initiiert wurde, ist oben rot markiert. Hier ist die letzte Regel, Regel 3:

Nach dem Aufteilen einer Kante von einem active_node, der nicht der Stammknoten ist, folgen wir dem Suffix-Link, der von diesem Knoten ausgeht, sofern vorhanden, und setzen den active_node auf den Knoten zurück, auf den er zeigt. Wenn es keinen Suffix-Link gibt, setzen wir den active_node auf root. active_Edge und active_length bleiben unverändert.

Der aktive Punkt ist also jetzt (node2,'c',1) und node2 ist unten rot markiert:

Da die Einfügung von abcd abgeschlossen ist, dekrementieren wir remainder auf 3 und berücksichtigen das nächste verbleibende Suffix des aktuellen Schritts, bcd. Regel 3 hat den aktiven Punkt auf den richtigen Knoten und die richtige Kante gesetzt, sodass Sie bcd einfügen können, indem Sie einfach das letzte Zeichen d am aktiven Punkt einfügen.

Wenn Sie dies tun, wird die Kante erneut geteilt, und aufgrund von Regel 2 müssen Sie einen Suffix-Link vom zuvor eingefügten Knoten zum neuen erstellen:

Wir beobachten: Suffix-Links ermöglichen es uns, den aktiven Punkt zurückzusetzen, so dass wir den nächstenverbleibendenbei O(1) einfügen können Anstrengung. Sehen Sie sich die obige Grafik an, um zu bestätigen, dass der Knoten mit der Bezeichnung ab tatsächlich mit dem Knoten mit b (dessen Suffix) verknüpft ist und der Knoten mit abc mit bc verknüpft ist.

Der aktuelle Schritt ist noch nicht abgeschlossen. remainder ist jetzt 2 und wir müssen Regel 3 folgen, um den aktiven Punkt wieder zurückzusetzen. Da der aktuelle active_node (oben rot) keinen Suffix-Link hat, setzen wir ihn auf root zurück. Der aktive Punkt ist jetzt (root,'c',1).

Daher erfolgt die nächste Einfügung an der einen ausgehenden Kante des Wurzelknotens, dessen Bezeichnung mit c beginnt: cabxabcd, hinter dem ersten Zeichen, d. H. Hinter c. Dies führt zu einer weiteren Aufteilung:

Und da dies die Erstellung eines neuen internen Knotens beinhaltet, befolgen wir Regel 2 und setzen einen neuen Suffix-Link vom zuvor erstellten internen Knoten:

(Ich verwende Graphviz Dot für diese kleinen Grafiken. Der neue Suffix-Link hat bewirkt, dass der Punkt die vorhandenen Kanten neu anordnet. Überprüfen Sie daher sorgfältig, ob das einzige, was oben eingefügt wurde, ein neuer Suffix-Link ist .)

Damit kann remainder auf 1 gesetzt werden, und da der active_node root ist, verwenden wir Regel 1, um den aktiven Punkt auf (root,'d',0) zu aktualisieren. Dies bedeutet, dass die letzte Einfügung des aktuellen Schritts darin besteht, ein einzelnes d im Stammverzeichnis einzufügen:

Das war der letzte Schritt und wir sind fertig. Es gibt jedoch eine Reihe von abschließenden Beobachtungen:

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

  • Es geht jedoch nicht um a) irgendwelche Suffixeverbleibendeaus vorherigen Schritten und b) mit dem einen letzten Zeichen des aktuellen Schritts.

  • remainder gibt an, wie viele zusätzliche Einfügungen wir vornehmen müssen. Diese Einfügungen entsprechen eins zu eins den Endsuffixen der Zeichenfolge, die an der aktuellen Position # endet. Wir überlegen nacheinander und machen den Einsatz. Wichtig: Jedes Einfügen erfolgt in der Zeit O(1), da der aktive Punkt genau angibt, wohin es gehen soll, und wir am aktiven Punkt nur ein einziges Zeichen hinzufügen müssen. Warum? Weil die anderen Zeichenimplizit enthalten sind(ansonsten wäre der aktive Punkt nicht dort, wo er ist).

  • Nach jeder solchen Einfügung dekrementieren wir remainder und folgen dem Suffix-Link, falls vorhanden. Wenn nicht, gehen wir zu root (Regel 3). Wenn wir bereits an der Wurzel sind, ändern wir den aktiven Punkt mit Regel 1. In jedem Fall dauert es nur O(1).

  • Wenn wir während einer dieser Einfügungen feststellen, dass das Zeichen, das wir einfügen möchten, bereits vorhanden ist, tun wir nichts und beenden den aktuellen Schritt, auch wenn remainder> 0 ist. Der Grund dafür ist, dass alle verbleibenden Einfügungen Suffixe derjenigen sind, die wir gerade versucht haben. Daher sind sie alleimplizitim aktuellen Baum. Die Tatsache, dass remainder> 0 ist, stellt sicher, dass wir uns später mit den verbleibenden Suffixen befassen.

  • Was ist, wenn am Ende des Algorithmus remainder> 0 ist? Dies ist immer dann der Fall, wenn das Ende des Texts eine Teilzeichenfolge ist, die irgendwo zuvor aufgetreten ist. In diesem Fall müssen wir ein zusätzliches Zeichen an das Ende der zuvor nicht aufgetretenen Zeichenfolge anhängen. In der Literatur wird üblicherweise das Dollarzeichen $ als Symbol dafür verwendet. Warum ist das wichtig? -> Wenn wir später den ausgefüllten Suffixbaum verwenden, um nach Suffixen zu suchen, müssen wir Übereinstimmungen nur akzeptieren, wenn siean einem Blatt enden. Andernfalls würden viele falsche Übereinstimmungen auftreten, da der BaumvieleZeichenfolgenimplizitenthält Nicht tatsächliche Suffixe der Hauptzeichenfolge. Wenn Sie remainder am Ende auf 0 setzen, können Sie im Wesentlichen sicherstellen, dass alle Suffixe an einem Blattknoten enden. Allerdings wenn wir den Baum verwenden wollen, um nachallgemeinen Teilstringszu suchen, nicht nur nachSuffixendes Hauptstrings ist dieser letzte Schritt in der Tat nicht erforderlich, wie aus dem Kommentar des OP unten hervorgeht.

  • Wie komplex ist der gesamte Algorithmus? Wenn der Text n Zeichen lang ist, gibt es offensichtlich n Schritte (oder n + 1, wenn wir das Dollarzeichen hinzufügen). In jedem Schritt tun wir entweder nichts (außer die Variablen zu aktualisieren) oder wir fügen remainder ein, wobei jedes Mal O(1) Zeit in Anspruch nimmt. Da remainder angibt, wie oft wir in den vorherigen Schritten nichts getan haben, und für jede jetzt vorgenommene Einfügung dekrementiert wird, beträgt die Gesamtanzahl der Aktionen 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 Punkt aktualisieren und dann feststellen, dass die Komponente active_length mit dem neuen active_node nicht gut funktioniert. Betrachten Sie zum Beispiel eine Situation wie diese:

(Die gestrichelten Linien geben den Rest des Baums an. Die gepunktete Linie ist ein Suffix-Link.)

Nun sei der aktive Punkt (red,'d',3), so dass er auf die Stelle hinter dem f am defg-Rand zeigt. Nehmen wir nun an, wir haben die erforderlichen Aktualisierungen vorgenommen und folgen nun dem Suffix-Link, um den aktiven Punkt gemäß Regel 3 zu aktualisieren. Der neue aktive Punkt ist (green,'d',3). Die d- Kante, die vom grünen Knoten ausgeht, ist de, hat also nur 2 Zeichen. Um den richtigen aktiven Punkt zu finden, müssen wir natürlich dieser Kante zum blauen Knoten folgen und auf (blue,'f',1) zurücksetzen.

In einem besonders schlimmen Fall kann der active_length so groß wie remainder sein, der so groß wie n sein kann. Und es kann durchaus vorkommen, dass wir, um den richtigen aktiven Punkt zu finden, nicht nur über einen internen Knoten springen müssen, sondern möglicherweise über viele, im schlimmsten Fall bis zu n. Bedeutet das, dass der Algorithmus ein verstecktes O (n) hat?2) Komplexität, weil in jedem Schritt remainder im Allgemeinen O (n) ist und die Nachjustierung des aktiven Knotens nach dem Folgen eines Suffix-Links auch O (n) sein könnte?

Nein. Der Grund dafür ist, dass, wenn wir tatsächlich den aktiven Punkt anpassen müssen (z. B. von Grün nach Blau wie oben), dies uns zu einem neuen Knoten mit einer eigenen Suffix-Verknüpfung führt und active_length reduziert wird. Wenn wir der Kette der Suffix-Links folgen, die wir für die verbleibenden Einfügungen verwenden, kann sich active_length nur verringern, und die Anzahl der aktiven Punktanpassungen, die wir unterwegs vornehmen können, kann nicht größer sein als active_length zu einem bestimmten Zeitpunkt. Da active_length niemals größer als remainder sein kann und remainder nicht nur in jedem einzelnen Schritt O(n) ist, beträgt die Gesamtsumme der jemals im Verlauf des gesamten Prozesses an remainder vorgenommenen Inkremente O(n) Auch die Anzahl der aktiven Punktanpassungen ist durch O (n) begrenzt.

2295
jogojapan

Ich habe versucht, den Suffix-Baum mit dem in jogojapans Antwort angegebenen Ansatz zu implementieren, aber es hat in einigen Fällen aufgrund der für die Regeln verwendeten Formulierung nicht funktioniert. Außerdem habe ich erwähnt, dass es niemandem gelungen ist, mit diesem Ansatz einen absolut korrekten Suffix-Baum zu implementieren. Nachfolgend schreibe ich einen "Überblick" über die Antwort von jogojapan mit einigen Änderungen an den Regeln. Ich werde den Fall auch beschreiben, wenn wir vergessen, wichtig Suffix-Links zu erstellen.

Weitere verwendete Variablen

  1. active point- ein Tripel (active_node; active_Edge; active_length), aus dem hervorgeht, ab welchem ​​Punkt ein neues Suffix eingefügt werden muss.
  2. rest- zeigt die Anzahl der Suffixe an, die wir hinzufügen müssen explizit . Wenn unser Wort beispielsweise 'abcaabca' ist und der Rest = 3, bedeutet dies, dass wir 3 letzte Suffixe verarbeiten müssen:bca,caunda.

Verwenden wir das Konzept einesinternen Knotens- aller Knoten mit Ausnahme des root und des ) leafs sindinterne Knoten.

Beobachtung 1

Wenn sich herausstellt, dass das endgültige 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 active_length irgendwann größer oder gleich der Länge der aktuellen Kante (Edge_length) ist, verschieben wir unser active point nach unten, bis Edge_length streng größer als active_length ist.

Nun definieren wir die Regeln neu:

Regel 1

Wenn nach einer Einfügung vom aktiven Knoten root , ist die aktive Länge ist größer als 0, dann:

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

Regel 2

Wenn wir einen neuen internen Knoten ODERerstellen, erstellen wir einen Inserter aus einem internen Knoten , und dies ist nicht der ersteWIE interner Knoten im aktuellen Schritt, dann verknüpfen wir der vorherigeSOLCHERKnoten mitDIESEReins durch ein Suffix link .

Diese Definition des Rule 2 unterscheidet sich von jogojapan ', da hier nicht nur die neu erstellten internen Knoten berücksichtigt werden, sondern auch die internen Knoten, aus denen wir eine Einfügung vornehmen.

Regel 3

Nach einer Einfügung vom aktiven Knoten , der nicht der root Knoten ist, müssen wir dem Suffix-Link folgen und den aktiver Knoten zu dem Knoten, auf den er zeigt. Wenn es keinen Suffix-Link gibt, setzen Sie den aktiven Knoten auf den root Knoten. In beiden Fällen bleiben active Edge und active Length unverändert.

In dieser Definition von Rule 3 berücksichtigen wir auch die Einfügungen von Blattknoten (nicht nur Teilknoten).

Und zum Schluss noch Bemerkung 3:

Wenn sich das Symbol, das wir dem Baum hinzufügen möchten, bereits am Rand befindet, aktualisieren wir gemäß Observation 1 nur active point und remainder, wobei der Baum unverändert bleibt.ABERwenn ein interner Knoten markiert ist als benötigt Suffix Link , wir müssen diesen Knoten mit unserem aktuellen active node über einen Suffixlink verbinden.

Schauen wir uns das Beispiel eines Suffix-Baums fürcdddcdcan, wenn wir in einem solchen Fall einen Suffix-Link hinzufügen und wenn wir dies nicht tun:

  1. Wenn wirNICHTdie Knoten durch einen Suffixlink verbinden:

    • vor dem letzten Buchstabenc:

    • nach dem letzten Buchstabenc:

  2. Wenn wirTUNdie Knoten durch einen Suffix-Link verbinden:

    • vor dem letzten Buchstabenc:

    • nach dem letzten Buchstabenc:

Es scheint keinen signifikanten Unterschied zu geben: Im zweiten Fall gibt es zwei weitere Suffix-Links. Aber diese Suffix-Links sind korrekt , und einer von ihnen - vom blauen zum roten Knoten - ist sehrwichtigfür unsere Annäherung mitactive point. Das Problem ist, dass wir, wenn wir hier keinen Suffix-Link einfügen, später, wenn wir dem Baum einige neue Buchstaben hinzufügen, das Hinzufügen einiger Knoten zum Baum aufgrund des Rule 3 möglicherweise weglassen, da es demnach keinen gibt ein Suffix-Link, dann müssen wir den active_node in den Root setzen.

Als wir den letzten Buchstaben zum Baum hinzufügten, hatte der rote Knotenbereits existiert, bevor wir eine Einfügung aus dem blauen Knoten machten (der Rand beschriftet'c'). Da es eine Einfügung vom blauen Knoten gab, markieren wir sie als benötigt einen Suffix-Link . Dann wurde unter Verwendung desactive pointapproach das active node auf den roten Knoten gesetzt. Wir machen aber keine Einfügung aus dem roten Knoten, da der Buchstabe'c'bereits am Rand steht. Bedeutet das, dass der blaue Knoten ohne Suffix-Link belassen werden muss? Nein, wir müssen den blauen Knoten mit dem roten über einen Suffix-Link verbinden. Warum ist es richtig? Denn deractive point-Ansatz garantiert, dass wir an die richtige Stelle gelangen, dh an die nächste Stelle, an der wir eine Einfügung vonverarbeiten müssen/kürzerSuffix.

Zum Schluss hier meine Implementierungen des Suffix-Baums:

  1. Java
  2. C++

Hoffe, dass diese "Übersicht" in Kombination mit der detaillierten Antwort von jogojapan jemandem hilft, seinen eigenen Suffix-Baum zu implementieren.

126
makagonov

Vielen Dank für das gut erläuterte Tutorial von@ jogojapan. Ich habe den Algorithmus in Python implementiert.

Ein paar kleinere Probleme, die von @jogojapan erwähnt wurden, erweisen sich als mehranspruchsvollals ich erwartet habe und müssen sehr sorgfältig behandelt werden. Es hat mich mehrere Tage gekostet, meine Implementierungrobust genug(nehme ich an) zu bekommen. Probleme und Lösungen sind nachfolgend aufgeführt:

  1. Ende mit Remainder > 0Es hat sich herausgestellt, dass diese Situation auchwährend des Entfaltungsschrittsauftreten kann, nicht nur am Ende des gesamten Algorithmus. In diesem Fall können wir den Rest, den Aktknoten, den Aktkeil und die Aktlängeunverändertbelassen, den aktuellen Entfaltungsschritt beenden und einen weiteren Schritt beginnen, indem wir entweder weiter falten oder entfalten, je nachdem, ob das nächste Zeichen eingegeben wird Die ursprüngliche Zeichenfolge befindet sich im aktuellen Pfad oder nicht.

  2. Sprung über Knoten:Wenn wir einem Suffix-Link folgen, aktualisieren Sie den aktiven Punkt und stellen dann fest, dass seine active_length-Komponente mit dem neuen active_node nicht gut funktioniert. Wir müssenvorwärts bewegenan die richtige Stelle, um zu spalten oder ein Blatt einzufügen. Dieser Vorgang ist möglicherweisenicht ganz so einfach, da sich während des Verschiebens die Länge und das Aktendeck ständig ändern, wenn Sie zumWurzelknotenzurückkehren müssen. Dasactedgeundactlengthkönntefalschaufgrund dieser Bewegungen sein. Wir benötigen zusätzliche Variablen, um diese Informationen zu speichern.

    enter image description here

Die beiden anderen Probleme wurden irgendwie von@ managonov

  1. Teilen könnte degenerierenWenn Sie versuchen, eine Kante zu teilen, werden Sie manchmal feststellen, dass sich die Teilungsoperation direkt auf einem Knoten befindet. In diesem Fall müssen wir nur ein neues Blatt zu diesem Knoten hinzufügen. Nehmen Sie es als Standard-Edge-Split-Operation. Das bedeutet, dass die Suffix-Links, falls vorhanden, entsprechend beibehalten werden sollten.

  2. Versteckte Suffix-LinksEs gibt einen weiteren Sonderfall, der bei Problem 1 und Problem 2 auftritt. Manchmal müssen wir zum Teilen über mehrere Knoten zum richtigen Punkt springen. Wenn wir uns bewegen, indem wir die verbleibende Zeichenfolge und die Pfadbezeichnungen vergleichen, können wirüberschreitenden richtigen Punkt. In diesem Fall wird der Suffix-Link unbeabsichtigt vernachlässigt, falls vorhanden. Dies könnte vermieden werden, indemsich beim Vorwärtsfahren an den richtigen Punkterinnert. Die Suffix-Verknüpfung sollte beibehalten werden, wenn der geteilte Knoten bereits vorhanden ist oder sogar das Problem 1 während eines Entfaltungsschritts auftritt.

Schließlich ist meine Implementierung inPythonwie folgt:

Tipps: Es enthält eine naiveBaum-Druckfunktionim obigen Code, was beim Debuggen sehr wichtig ist . Das hat mir viel Zeit gespart und ist praktisch, um Sonderfälle zu lokalisieren.

9
mutux

@jogojapan du hast tolle Erklärungen und Visualisierungen mitgebracht. Aber wie @makagonov erwähnt hat, fehlen einige Regeln für das Setzen von Suffix-Links. Es ist auf nette Weise sichtbar, wenn Sie Schritt für Schritt auf http://brenden.github.io/ukkonen-animation/ durch das Wort 'aabaaabb' gehen. Wenn Sie von Schritt 10 zu Schritt 11 wechseln, besteht keine Suffix-Verbindung von Knoten 5 zu Knoten 2, sondern der aktive Punkt bewegt sich plötzlich dorthin.

@makagonov da ich in Java Welt lebe, habe ich auch versucht, Ihrer Implementierung zu folgen, um den ST-Building-Workflow zu verstehen, aber es fiel mir schwer, weil:

  • kanten mit Knoten kombinieren
  • verwenden von Indexzeigern anstelle von Referenzen
  • bricht Aussagen;
  • aussagen fortsetzen;

So endete ich mit einer solchen Implementierung in Java, die hoffentlich alle Schritte klarer widerspiegelt und die Lernzeit für andere Java Personen 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);
        }
    });
  }
}
7
Kamil

Entschuldigung, wenn meine Antwort überflüssig erscheint, aber ich habe kürzlich den Ukkonen-Algorithmus implementiert und habe tagelang damit zu kämpfen gehabt. Ich musste mehrere Artikel zu diesem Thema durchlesen, um das Warum und Wie einiger Kernaspekte des Algorithmus zu verstehen.

Ich fand den "Regel" -Ansatz früherer Antworten nicht hilfreich für das Verständnis der zugrunde liegenden Gründe, deshalb habe ich alles unten geschrieben und mich ausschließlich auf die Pragmatik konzentriert. Wenn Sie Probleme damit haben, anderen Erklärungen zu folgen, wie ich es getan habe, wird es durch meine zusätzliche Erklärung möglicherweise für Sie "klick".

Ich habe meine C # -Implementierung hier veröffentlicht: https://github.com/baratgabor/SuffixTree

Bitte beachten Sie, dass ich kein Experte auf diesem Gebiet bin, daher können die folgenden Abschnitte Ungenauigkeiten (oder Schlimmeres) enthalten. Wenn Sie auf etwas stoßen, können Sie es gerne bearbeiten.

Voraussetzungen

Der Ausgangspunkt der folgenden Erläuterung setzt voraus, dass Sie mit dem Inhalt und der Verwendung von Suffix-Bäumen sowie den Merkmalen des Ukkonen-Algorithmus vertraut sind, z. wie Sie den Suffixbaum von Anfang bis Ende zeichenweise erweitern. Grundsätzlich gehe ich davon aus, dass Sie einige der anderen Erklärungen bereits gelesen haben.

(Ich musste jedoch einige grundlegende Erzählungen für den Ablauf hinzufügen, damit der Anfang sich tatsächlich überflüssig anfühlt.)

Der interessanteste Teil ist Erklärung des Unterschieds zwischen der Verwendung von Suffix-Links und dem erneuten Scannen von der Wurzel. Dies hat mir viele Fehler und Kopfschmerzen bei meiner Implementierung bereitet.

Endlose Blattknoten und ihre Einschränkungen

Ich bin sicher, dass Sie bereits wissen, dass der grundlegendste Trick darin besteht, zu erkennen, dass wir das Ende der Suffixe einfach offen lassen können, d. H. Auf die aktuelle Länge der Zeichenfolge verweisen, anstatt das Ende auf einen statischen Wert zu setzen. Auf diese Weise werden beim Hinzufügen zusätzlicher Zeichen diese Zeichen implizit allen Suffixbezeichnungen hinzugefügt, ohne dass alle besucht und aktualisiert werden müssen.

Dieses offene Ende von Suffixen funktioniert jedoch - aus offensichtlichen Gründen - nur für Knoten, die das Ende der Zeichenfolge darstellen, d. H. Für die Blattknoten in der Baumstruktur. Die Verzweigungsoperationen, die wir für den Baum ausführen (das Hinzufügen neuer Verzweigungsknoten und Blattknoten), breiten sich nicht automatisch überall dort aus, wo sie benötigt werden.

Es ist wahrscheinlich elementar und sollte nicht erwähnt werden, dass wiederholte Teilzeichenfolgen nicht explizit im Baum erscheinen, da der Baum diese bereits enthält, da es sich um Wiederholungen handelt. Wenn die sich wiederholende Teilzeichenfolge jedoch auf ein sich nicht wiederholendes Zeichen trifft, müssen wir an diesem Punkt eine Verzweigung erstellen, um die Abweichung von diesem Punkt an darzustellen.

Beispiel: Im Fall der Zeichenfolge 'ABCXABCY' (siehe unten) muss eine Verzweigung zu X und Y hinzugefügt werden zu drei verschiedenen Suffixen, ABC, BC und C; Andernfalls wäre es kein gültiger Suffixbaum, und wir könnten nicht alle Teilzeichenfolgen der Zeichenfolge finden, indem wir die Zeichen von der Wurzel abwärts abgleichen.

Noch einmal, um - any hervorzuheben, muss eine Operation, die wir für ein Suffix im Baum ausführen, auch durch ihre aufeinanderfolgenden Suffixe wiedergegeben werden (z. B. ABC> BC> C), da sie sonst einfach keine gültigen Suffixe mehr sind .

Repeating branching in suffixes

Aber selbst wenn wir akzeptieren, dass wir diese manuellen Updates durchführen müssen, woher wissen wir, wie viele Suffixe aktualisiert werden müssen? Da wir, wenn wir das wiederholte Zeichen A (und den Rest der wiederholten Zeichen nacheinander) hinzufügen, noch keine Ahnung haben, wann/wo wir das Suffix in zwei Zweige aufteilen müssen. Die Notwendigkeit der Aufteilung wird nur festgestellt, wenn wir auf das erste nicht wiederholende Zeichen stoßen, in diesem Fall Y (anstelle des bereits im Baum vorhandenen X) ).

Was wir tun können, ist, den längsten wiederholten String zu finden, den wir können, und zu zählen, wie viele seiner Suffixe wir später aktualisieren müssen. Dafür steht 'rest'.

Das Konzept von "Rest" und "Rescanning"

Die Variable remainder gibt an, wie viele wiederholte Zeichen wir implizit ohne Verzweigung hinzugefügt haben. d.h. wie viele Suffixe wir besuchen müssen, um die Verzweigungsoperation zu wiederholen, sobald wir das erste Zeichen gefunden haben, das wir nicht finden können. Dies entspricht im Wesentlichen der Anzahl der Zeichen, die sich von der Wurzel an im Baum befinden.

Bleiben wir also beim vorherigen Beispiel des Strings ABCXABCY, stimmen wir den wiederholten ABC - Teil 'implizit' ab und erhöhen remainder jedes Mal, was ergibt den Rest von 3. Dann stoßen wir auf das sich nicht wiederholende Zeichen 'Y'. Hier teilen wir die zuvor hinzugefügten ABCX in ABC -> X und ABC -> Y. Dann dekrementieren wir remainder von 3 auf 2, weil wir uns bereits um die ABC -Verzweigung gekümmert haben. Jetzt wiederholen wir die Operation, indem wir die letzten 2 Zeichen - BC - von der Wurzel abgleichen, um den Punkt zu erreichen, an dem wir teilen müssen, und wir teilen BCX ebenfalls in BC -> X und BC -> Y. Wieder dekrementieren wir remainder auf 1 und wiederholen die Operation; bis das remainder 0 ist. Als letztes müssen wir das aktuelle Zeichen (Y) selbst ebenfalls zur Wurzel hinzufügen.

Diese Operation wird im Ukkonen-Algorithmus als 'rescanning' bezeichnet und ist nach den aufeinanderfolgenden Suffixen von der Wurzel bis zu dem Punkt, an dem eine Operation ausgeführt werden muss, in der Regel der teuerste Teil des Algorithmus . Stellen Sie sich eine längere Zeichenfolge vor, in der Sie lange Teilzeichenfolgen über viele Dutzend Knoten hinweg (wir werden später darauf eingehen) erneut prüfen müssen, möglicherweise tausende Male.

Als Lösung stellen wir vor, was wir 'Suffix-Links' nennen.

Das Konzept der "Suffix-Links"

Suffix-Verknüpfungen verweisen im Grunde genommen auf die Positionen, zu denen wir normalerweise 'rescan' müssen, sodass wir anstelle des teuren Rescan-Vorgangs einfach zur verknüpften Position springen, unsere Arbeit erledigen und zur nächsten verknüpften springen können positionieren und wiederholen - bis keine Positionen mehr aktualisiert werden müssen.

Eine große Frage ist natürlich, wie man diese Links hinzufügt. Die bestehende Antwort ist, dass wir die Verknüpfungen hinzufügen können, wenn wir neue Verzweigungsknoten einfügen. Dabei wird die Tatsache ausgenutzt, dass in jeder Erweiterung des Baums die Verzweigungsknoten nacheinander in der genauen Reihenfolge erstellt werden, in der sie miteinander verknüpft werden müssen . Wir müssen jedoch eine Verknüpfung vom zuletzt erstellten Zweigknoten (dem längsten Suffix) zum zuvor erstellten Zweigknoten herstellen. Daher müssen wir den zuletzt erstellten Knoten zwischenspeichern, den zuletzt erstellten Knoten mit dem nächsten Knoten verknüpfen und den neu erstellten Knoten zwischenspeichern.

Eine Konsequenz ist, dass wir tatsächlich oft keine Suffix-Links folgen müssen, da der angegebene Zweigknoten gerade erstellt wurde. In diesen Fällen müssen wir immer noch auf das oben erwähnte 'rescanning' von root zurückgreifen. Aus diesem Grund werden Sie nach dem Einfügen angewiesen, entweder den Suffix-Link zu verwenden oder zum Stammverzeichnis zu springen.

(Oder alternativ, wenn Sie übergeordnete Zeiger in den Knoten speichern, können Sie versuchen, den übergeordneten Zeigern zu folgen, zu überprüfen, ob sie einen Link haben, und diesen zu verwenden. Ich habe festgestellt, dass dies sehr selten erwähnt wird, aber das Suffix Die Verwendung von Links ist nicht in Stein gemeißelt. Es gibt mehrere mögliche Ansätze, und wenn Sie den zugrunde liegenden Mechanismus verstehen, können Sie einen implementieren, der Ihren Anforderungen am besten entspricht.)

Das Konzept des aktiven Punktes

Bisher haben wir mehrere effiziente Werkzeuge zum Erstellen des Baums besprochen und uns vage auf das Überqueren mehrerer Kanten und Knoten bezogen, die entsprechenden Konsequenzen und Komplexitäten jedoch noch nicht untersucht.

Das zuvor erläuterte Konzept von 'remainder' ist nützlich, um zu verfolgen, wo wir uns im Baum befinden, aber wir müssen erkennen, dass es nicht genügend Informationen speichert.

Erstens befinden wir uns immer auf einer bestimmten Kante eines Knotens, daher müssen wir die Kanteninformationen speichern. Wir werden dies 'aktive Kante' nennen.

Zweitens haben wir auch nach dem Hinzufügen der Edge-Informationen keine Möglichkeit, eine Position zu identifizieren, die weiter unten im Baum liegt und nicht direkt mit dem Knoten root ​​verbunden ist. Also müssen wir auch den Knoten speichern. Nennen wir dies 'aktiver Knoten'.

Schließlich können wir feststellen, dass der 'Rest' nicht ausreicht, um eine Position auf einer Kante zu identifizieren, die nicht direkt mit der Wurzel verbunden ist, da 'Rest' die Länge des ist gesamte Strecke; und wir wollen uns wahrscheinlich nicht darum kümmern, die Länge der vorherigen Kanten zu merken und zu subtrahieren. Wir brauchen also eine Darstellung, die im Wesentlichen Rest auf der aktuellen Kante ist. Das nennen wir 'aktive Länge'.

Dies führt zu dem, was wir 'aktiver Punkt' nennen - einem Paket von drei Variablen, die alle Informationen enthalten, die wir über unsere Position im Baum benötigen:

Active Point = (Active Node, Active Edge, Active Length)

Auf dem folgenden Bild können Sie beobachten, wie die übereinstimmende Route von ABCABD aus 2 Zeichen am Rand besteht AB (von root) , plus 4 Zeichen am Rand CABDABCABD (von Knoten 4) - was zu einem 'Rest' von 6 Zeichen führt. Unsere aktuelle Position kann also als Active Node 4, Active Edge C, Active Length 4 identifiziert werden.

Remainder and Active Point

Eine weitere wichtige Rolle des 'aktiven Punkts' ist, dass es eine Abstraktionsschicht für unseren Algorithmus bereitstellt, was bedeutet, dass Teile unseres Algorithmus ihre Arbeit auf dem 'aktiven Punkt' ausführen können , unabhängig davon, ob sich dieser aktive Punkt in der Wurzel oder irgendwo anders befindet. Dies macht es einfach, die Verwendung von Suffix-Links in unserem Algorithmus auf eine saubere und unkomplizierte Weise zu implementieren.

Unterschiede zwischen dem erneuten Scannen und der Verwendung von Suffix-Links

Der schwierige Teil, der meiner Erfahrung nach viele Fehler und Kopfschmerzen verursachen kann und in den meisten Quellen nur unzureichend erklärt wird, ist der Unterschied in der Verarbeitung der Suffix-Link-Fälle gegenüber den Rescan-Fällen.

Betrachten Sie das folgende Beispiel der Zeichenfolge 'AAAABAAAABAAC':

Remainder across multiple edges

Sie können oben beobachten, wie der 'Rest' von 7 der Gesamtsumme der Zeichen von root entspricht, während 'aktive Länge' von 4 der Summe der übereinstimmenden Zeichen von entspricht die aktive Kante des aktiven Knotens.

Nach der Ausführung einer Verzweigungsoperation am aktiven Punkt enthält unser aktiver Knoten möglicherweise eine Suffix-Verknüpfung.

Wenn ein Suffix-Link vorhanden ist: Wir müssen nur den Abschnitt 'aktive Länge' verarbeiten. Der 'Rest' ist irrelevant, da der Knoten, zu dem wir über den Suffix-Link springen, implizit bereits den richtigen 'Rest' codiert, einfach weil wir uns in dem Baum befinden, in dem es ist.

Wenn kein Suffix-Link vorhanden ist: Wir müssen 'rescan' von null/root, was bedeutet, dass das gesamte Suffix verarbeitet wird von Anfang an. Zu diesem Zweck müssen wir den gesamten 'Rest' als Grundlage für das erneute Scannen verwenden.

Beispielvergleich der Verarbeitung mit und ohne Suffix-Link

Überlegen Sie, was im nächsten Schritt des obigen Beispiels passiert. Vergleichen wir, wie Sie dasselbe Ergebnis erzielen - d. H. Zum nächsten zu verarbeitenden Suffix wechseln - mit und ohne Suffix-Verknüpfung.

Verwenden von 'Suffix-Link'

Reaching consecutive suffixes via suffix links

Beachten Sie, dass wir automatisch am richtigen Ort sind, wenn wir einen Suffix-Link verwenden. Dies ist häufig nicht unbedingt der Fall, da die 'aktive Länge' mit der neuen Position 'inkompatibel' sein kann.

Im obigen Fall arbeiten wir, da 'aktive Länge' 4 ist, mit dem Suffix 'ABAA', beginnend mit dem verknüpften Node 4. Nachdem wir jedoch die Kante gefunden haben, die dem ersten Zeichen des Suffixes ('A') entspricht, stellen wir fest, dass unsere 'aktive Länge' diese Kante um 3 Zeichen überläuft . Also springen wir über die volle Kante zum nächsten Knoten und verringern 'aktive Länge' um die Zeichen, die wir mit dem Sprung verbraucht haben.

Nachdem wir dann die nächste Kante gefunden haben 'B', entsprechend dem dekrementierten Suffix 'BAA', stellen wir schließlich fest, dass die Kantenlänge größer ist als die verbleibende 'active length' von 3, was bedeutet, dass wir den richtigen Ort gefunden haben.

Bitte beachten Sie, dass dieser Vorgang normalerweise nicht als erneutes Scannen bezeichnet wird, obwohl er für mich das direkte Äquivalent zum erneuten Scannen zu sein scheint, nur mit einer verkürzten Länge und einem Nicht-Root-Ausgangspunkt.

Mit 'rescan'

Reaching consecutive suffixes via rescanning

Beachten Sie, dass wir, wenn wir eine herkömmliche "Rescan" -Operation verwenden (hier so tun, als hätten wir keinen Suffix-Link), am oberen Ende des Baums beginnen, an der Wurzel, und uns wieder nach unten zum richtigen Ort arbeiten müssen. Folgen entlang der gesamten Länge des aktuellen Suffix.

Die Länge dieses Suffixes ist der 'Rest', den wir zuvor besprochen haben. Wir müssen den gesamten Rest konsumieren, bis er Null erreicht. Dies kann (und oft auch) das Springen durch mehrere Knoten beinhalten, wobei bei jedem Sprung der Rest um die Länge der Kante verringert wird, durch die wir gesprungen sind. Dann erreichen wir endlich eine Kante, die länger ist als unsere verbleibenden 'Rest'; hier setzen wir die aktive Kante auf die angegebene Kante, setzen 'aktive Länge' auf verbleibend 'Rest' und wir sind fertig.

Beachten Sie jedoch, dass die aktuelle Variable 'remainder' beibehalten und erst nach jedem Einfügen eines Knotens dekrementiert werden muss. Was ich oben beschrieben habe, ging also davon aus, dass eine separate Variable verwendet wird, die mit 'remainder' initialisiert wurde.

Hinweise zu Suffix-Links und Rescans

1) Beachten Sie, dass beide Methoden zum gleichen Ergebnis führen. Das Springen von Suffix-Links ist jedoch in den meisten Fällen erheblich schneller. Das ist die ganze Logik hinter Suffix-Links.

2) Die tatsächlichen algorithmischen Implementierungen müssen sich nicht unterscheiden. Wie ich oben erwähnt habe, ist die 'aktive Länge' selbst im Fall der Verwendung des Suffix-Links oft nicht mit der verknüpften Position kompatibel, da dieser Zweig des Baums möglicherweise zusätzliche Verzweigungen enthält. Im Grunde genommen müssen Sie also nur 'aktive Länge' anstelle von 'Rest' verwenden und dieselbe Neuabtastlogik ausführen, bis Sie eine Kante finden, die kürzer ist als Ihre verbleibende Suffixlänge .

3) Eine wichtige Anmerkung zur Leistung ist, dass nicht jedes Zeichen beim erneuten Scannen überprüft werden muss. Aufgrund der Art und Weise, wie ein gültiger Suffixbaum erstellt wird, können wir davon ausgehen, dass die Zeichen übereinstimmen. Sie zählen also hauptsächlich die Längen, und die einzige Notwendigkeit für die Prüfung der Zeichenäquivalenz entsteht, wenn wir zu einer neuen Kante springen, da Kanten durch ihr erstes Zeichen identifiziert werden (das im Kontext eines bestimmten Knotens immer eindeutig ist). Dies bedeutet, dass sich die Logik des erneuten Scannens von der Logik des vollständigen String-Abgleichs unterscheidet (d. H. Nach einer Teilzeichenfolge im Baum suchen).

4) Die hier beschriebene Verknüpfung mit dem ursprünglichen Suffix ist nur einer der möglichen Ansätze. Zum Beispiel NJ Larsson et al. nennt diesen Ansatz Node-Oriented Top-Down und vergleicht ihn mit Node-Oriented Bottom-Up und zwei Kantenorientiert ​​Sorten. Die verschiedenen Ansätze weisen unterschiedliche typische und Worst-Case-Leistungen, -Anforderungen, -Einschränkungen usw. auf, aber es scheint im Allgemeinen, dass Kantenorientiert ​​Ansätze eine allgemeine Verbesserung des Originals darstellen.

7
MrValueType

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 beginnen.

Zu Beginn bedeutet dies, dass der Suffixbaum einen einzelnen Stammknoten 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 die Taste der aktive Punkt. Ich vermute, dass dies der tiefste Punkt im Suffixbaum ist, der einem richtigen Suffix der ersten k Zeichen der Zeichenfolge 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 im Baum darstellen, der dem Suffix 'abc' entspricht.

Der aktive Punkt wird durch (Ursprung, zuerst, zuletzt) ​​dargestellt. Dies bedeutet, dass Sie sich derzeit an dem Punkt in der Struktur befinden, zu dem Sie gelangen, indem Sie am Knoten Origin beginnen und dann die Zeichen in der Zeichenfolge [first: last] eingeben.

Wenn Sie ein neues Zeichen hinzufügen, prüfen Sie, ob sich der aktive Punkt noch im vorhandenen Baum befindet. Wenn ja, dann sind Sie fertig. Andernfalls müssen Sie dem Suffixbaum am aktiven Punkt einen neuen Knoten hinzufügen, auf die nächst kürzere Übereinstimmung zurückgreifen und erneut prüfen.

Hinweis 1: Die Suffix-Zeiger geben für jeden Knoten eine Verknüpfung zur nächst kürzeren Übereinstimmung.

Hinweis 2: Wenn Sie einen neuen Knoten und ein 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 verkürzten aktiven Punkt. Dieser Knoten ist entweder bereits vorhanden oder wird bei der nächsten Iteration dieser Fallback-Schleife erstellt.

Anmerkung 3: Der Kanonisierungsteil spart lediglich Zeit bei der Überprüfung des aktiven Punkts. Angenommen, Sie haben immer Origin = 0 verwendet und nur zuerst und zuletzt geändert. Um den aktiven Punkt zu überprüfen, müssten Sie dem Suffixbaum jedes Mal entlang aller Zwischenknoten folgen. Es ist sinnvoll, das Ergebnis der Verfolgung dieses Pfades zwischenzuspeichern, indem nur die Entfernung vom letzten Knoten aufgezeichnet wird.

Können Sie ein Codebeispiel dafür geben, was Sie unter "Fixieren" von Begrenzungsvariablen verstehen?

Gesundheitswarnung: Ich fand diesen Algorithmus auch besonders schwer verständlich. Bitte haben Sie Verständnis dafür, dass diese Intuition in allen wichtigen Details wahrscheinlich falsch ist ...

6
Peter de Rivaz

Hallo, ich habe versucht, die oben erläuterte Implementierung in Ruby zu implementieren. Bitte probieren Sie es aus. 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.

sein 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[[email protected]_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 @[email protected]_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
Suchit Puri