Der Suffixbaum-Algorithmus von Ukkonen in einfacher Sprache

Question

Ich fühle mich an diesem Punkt ein bisschen dick. Ich habe Tage damit verbracht, die Konstruktion von Suffixbäumen zu verstehen, aber da ich keinen mathematischen Hintergrund habe, entziehen sich mir viele der Erklärungen, da sie sich zu sehr auf mathematische Symbole stützen. Die beste Erklärung, die ich gefunden habe, ist Schnelle String-Suche mit Suffix-Bäumen Er übergeht jedoch verschiedene Punkte und einige Aspekte des Algorithmus bleiben unklar.

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

Als Referenz finden Sie hier Ukkonens Arbeit über den Algorithmus: http://www.cs.helsinki.fi/u/ukkonen/SuffixT1withFigs.pdf

Mein grundlegendes Verständnis, soweit:

• Ich muss durch jedes Präfix P einer gegebenen Zeichenfolge T iterieren
• Ich muss jedes Suffix S im Präfix P durchlaufen und es zum Baum hinzufügen
• Um dem Baum ein Suffix S hinzuzufügen, muss ich jedes Zeichen in S durchlaufen, wobei die Iterationen entweder darin bestehen, dass ich einen bestehenden Zweig hinuntergehe, der mit derselben Menge von Zeichen C in S beginnt, und möglicherweise eine Kante in absteigende Knoten aufspalte, wenn ich ein abweichendes Zeichen im Suffix erreiche, ODER wenn es keine passende Kante zum Hinuntergehen gab. Wenn keine passende Kante für C gefunden wird, wird eine neue Blattkante für C erstellt.

Der grundlegende Algorithmus ist offenbar O(n 2 ), wie in den meisten Erklärungen hervorgehoben wird, da wir durch alle Präfixe gehen müssen, dann müssen wir durch jedes Suffix für jedes Präfix gehen. Ukkonens Algorithmus ist anscheinend einzigartig, weil er eine Suffix-Zeiger-Technik verwendet, obwohl ich denke 其の ist das, was ich nicht verstehen kann.

Ich habe auch Schwierigkeiten, das zu verstehen:

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

---

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

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 JavaScript . Gist ist unten. Sie sollte fehlerfrei sein. Dump es in eine js-Datei, npm install chalk von derselben Stelle aus und führen Sie es dann mit node.js aus, um eine bunte Ausgabe zu sehen. Es gibt eine abgespeckte Version in der gleichen Gist, ohne jede der Debugging-Code.

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

Answer 1

Im Folgenden wird versucht, den Ukkonen-Algorithmus zu beschreiben, indem zunächst gezeigt wird, was er tut, wenn die Zeichenkette einfach ist (d. h. keine wiederholten Zeichen enthält), und dann auf den vollständigen Algorithmus ausgedehnt wird.

Zunächst ein paar Vorbemerkungen.

1. Was wir bauen, ist Grundsätzlich wie ein Suchauftrag. Es gibt also gibt es einen Wurzelknoten, von dem Kanten ausgehen, die zu neuen Knoten führen, und weitere Kanten, die von diesen ausgehen, und so weiter

2. Aber : Anders als in einem Such-Trie sind die Kantenbeschriftungen nicht ein Zeichen. Stattdessen wird jede Kante mit einem Paar ganzer Zahlen beschriftet [from,to] . Dies sind Verweise auf den Text. In diesem Sinne ist jede Kante eine Zeichenfolge beliebiger Länge, benötigt aber nur O(1) Platz (zwei Zeiger).

Grundprinzip

Ich möchte zunächst zeigen, wie man den Suffixbaum einer besonders einfachen Zeichenkette, einer Zeichenkette ohne wiederholte Zeichen:

abc

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

Wir gehen also von der links und fügen Sie zunächst nur das einzelne Zeichen a indem Sie eine Kante vom Wurzelknoten (links) zu einem Blatt erstellen, und beschriften sie als [0,#] , d.h. die Kante repräsentiert die Teilstring, der an Position 0 beginnt und an das aktuelle Ende . I verwende das Symbol # zu bedeuten das aktuelle Ende die sich an Position 1 befindet (direkt nach a ).

Wir haben also einen ersten Baum, der wie folgt aussieht:

Und das bedeutet Folgendes:

Jetzt gehen wir zu Position 2 (direkt nach b ). Unser Ziel bei jedem Schritt ist einzufügen alle Suffixe bis zur aktuellen Position . Wir tun dies von

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

In unserer Darstellung sieht das wie folgt aus

Und das bedeutet Folgendes:

Wir beobachten zwei Dinge:

• Die Kantendarstellung für ab ist derselbe wie es früher einmal war im ursprünglichen 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) Platz, da sie nur aus zwei Teilen besteht Zeigern in den Text besteht, unabhängig davon, wie viele Zeichen sie repräsentiert.

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

In unserer Darstellung sieht das wie folgt aus

Und das bedeutet Folgendes:

Wir beobachten:

• Der Baum ist der richtige Suffixbaum bis zur aktuellen Position nach jedem Schritt
• Es gibt so viele Schritte, wie es Zeichen im Text gibt
• Der Arbeitsaufwand ist in jedem Schritt O(1), da alle vorhandenen Kanten automatisch durch Inkrementierung aktualisiert werden # und das Einfügen der eine neue Kante für das letzte Zeichen kann in O(1) Zeit erledigt werden. Für eine Zeichenkette der Länge n wird also nur O(n) Zeit benötigt.

Erste Verlängerung: Einfache Wiederholungen

Das funktioniert natürlich nur deshalb so gut, weil unser String keine keine Wiederholungen enthält. Sehen wir uns nun eine realistischere Zeichenfolge an:

abcabxabcd

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

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

Schritt 4: Wir bewegen uns # auf Platz 4. Dies aktualisiert implizit alle bestehenden Kanten auf diese Position:

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

Bevor wir dies tun, führen wir ein zwei weitere Variablen (zusätzlich zu # ), die natürlich schon immer da waren, die wir aber bisher nicht genutzt haben sie bisher nicht genutzt:

• En aktiver Punkt was ein Dreifaches ist (active_node,active_edge,active_length)
• En remainder ist eine ganze Zahl, die angibt, wie viele neue Suffixe wir einfügen müssen

Die genaue Bedeutung dieser beiden Begriffe wird in Kürze klar werden, aber zunächst einmal lassen Sie uns einfach sagen:

• In der einfachen abc Beispiel war der aktive Punkt immer (root,'\0x',0) d.h. active_node war der Wurzelknoten, active_edge wurde als Nullzeichen angegeben '\0x' y active_length war Null. Dies hatte zur Folge, dass die eine neue Kante, die die wir in jedem Schritt eingefügt haben, am Wurzelknoten als eine frisch erstellte Kante. Wir werden gleich sehen, warum ein Tripel notwendig ist, um diese Information darzustellen.
• En remainder immer auf 1 gesetzt wurde, und zwar zu Beginn eines jeden Schrittes. Dies bedeutete, dass die Anzahl der Suffixe, die wir am Ende jeder am Ende eines jeden Schritts aktiv einfügen mussten, 1 war (immer nur das letzte Zeichen).

Das wird sich jetzt ändern. Wenn wir das aktuelle Endzeichen einfügen Zeichen a an der Wurzel, stellen wir fest, dass es bereits eine ausgehende Kante gibt, die mit a konkret: abca . Das tun wir in einem solchen Fall:

• Wir nicht eine neue Kante einfügen [4,#] am Wurzelknoten. Stattdessen wird einfach feststellen, dass das Suffix a ist bereits in unserem Baum. Er endet in der Mitte einer längeren Kante, aber wir sind nicht stört uns das nicht. Wir lassen die Dinge einfach so, wie sie sind.
• Wir den aktiven Punkt einstellen a (root,'a',1) . Das bedeutet, dass der aktive Punkt liegt jetzt irgendwo in der Mitte der ausgehenden Kante des Wurzelknotens, die mit a und zwar nach der Position 1 auf dieser Kante. Wir bemerken, dass die Kante einfach durch ihr erstes Zeichen angegeben wird Zeichen a . Das reicht aus, denn es können sein nur einer Rand beginnend mit einem bestimmten Zeichen (vergewissern Sie sich, dass dies der Fall ist, nachdem Sie die gesamte Beschreibung durchgelesen haben).
• Wir erhöhen auch die remainder so dass zu Beginn des nächsten Schrittes wird es 2 sein.

Beobachtung: Wenn die endgültige Suffix, das wir einfügen müssen, wird gefunden als bereits im Baum vorhanden ist ist der Baum selbst nicht geändert überhaupt nicht (wir aktualisieren nur den aktiven Punkt und remainder ). Der Baum ist dann keine genaue Darstellung des Suffixbaums bis zum aktuellen Position nicht mehr, aber es enthält alle Suffixe (weil die Endung Suffix a enthalten ist implizit ). Daher ist neben der Aktualisierung der Variablen (die alle eine feste Länge haben, so dass dies O(1) ist), gab es keine Arbeit in diesem Schritt durchgeführt.

Schritt 5: Wir aktualisieren die aktuelle Position # bis 5. Diese wird der Baum automatisch auf diesen Wert aktualisiert:

Et denn remainder ist 2 müssen wir zwei abschließende Suffixe an der aktuellen Position einfügen: ab y b . Dies ist im Wesentlichen darauf zurückzuführen:

• En a Suffix aus dem vorangegangenen Schritt wurde nie richtig eingefügt. Es hat also blieb und da wir einen Schritt weitergekommen sind Schritt gemacht haben, ist sie nun von a a ab .
• Und wir müssen die neue Endkante einfügen b .

In der Praxis bedeutet dies, dass wir zum aktiven Punkt gehen (der auf hinter dem a auf dem heutigen Gelände der abcab Kante), und setzen Sie die aktuellen Endzeichen b . Aber: Auch hier zeigt sich, dass b ist bereits an derselben Kante vorhanden.

Also noch einmal, wir ändern den Baum nicht. Wir einfach:

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

Um es klar zu sagen: Wir mussten die ab y b im aktuellen Schritt, aber weil ab bereits gefunden wurde, haben wir den aktiven Punkt aktualisiert und nicht einmal versucht, einen b . Warum? Weil, wenn ab ist im Baum, jede Nachsilbe davon (einschließlich b ) muss im Baum sein, auch. Vielleicht nur implizit aber sie muss da sein, wegen der wie wir den Baum bisher aufgebaut haben.

Wir fahren fort mit Stufe 6 durch Inkrementierung # . Der Baum wird automatisch aktualisiert:

Denn remainder ist 3 müssen wir einfügen abx , bx y x . Der aktive Punkt sagt uns, wo ab endet, also müssen wir nur springen und die x . In der Tat, x ist noch nicht da, also haben wir teilen die abcabx Kante und fügen einen internen Knoten ein:

Die Randdarstellungen sind immer noch Zeiger auf den Text, so dass kann das Aufteilen und Einfügen eines internen Knotens in O(1) Zeit erfolgen.

Wir haben uns also mit abx und Dekrement remainder auf 2. Jetzt müssen wir 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 ist, nach dem Aufteilen und dem Einfügen einer Kante, wird Regel 1 unten, und sie gilt immer dann, wenn die active_node ist Root (wir werden Regel 3 für andere Fälle noch lernen weiter unten). Hier ist Regel 1:

Nach einer Einfügung von Root,

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

Daher ist das neue Aktivpunkt-Tripel (root,'b',1) zeigt an, dass die die nächste Einfügung an der Stelle erfolgen muss bcabx Rand, hinter 1 Zeichen, d.h. hinter b . Wir können den Einfügepunkt in O(1) Zeit identifizieren und prüfen, ob x bereits vorhanden ist oder nicht. Wenn sie vorhanden ist, würden wir würden wir den aktuellen Schritt beenden und alles so lassen, wie es ist. Aber x ist nicht vorhanden, also fügen wir es durch Aufteilung der Kante ein:

Auch dies dauerte O(1) Zeit und wir aktualisieren remainder auf 1 und die aktiven Punkt auf (root,'x',0) wie Regel 1 besagt.

Aber es gibt noch eine Sache, die wir tun müssen. Wir nennen dies Regel 2:

Wenn wir eine Kante teilen und einen neuen Knoten einfügen, und wenn das n erste Knoten die während des laufenden eingefügten Knoten und den neuen Knoten durch einen speziellen Zeiger, einen Suffix Link . Wir werden später sehen, warum das nützlich ist. Hier ist, was wir erhalten, das Suffix-Link wird als gepunktete Kante dargestellt:

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

Wie wir sehen können, wurden im aktuellen Schritt alle verbleibenden Einfügungen vorgenommen.

Wir fahren fort mit Stufe 7 durch Einstellung # =7, wodurch automatisch das nächste Zeichen angehängt wird, a zu allen Blatträndern, wie immer. Dann versuchen wir, das neue Endzeichen Zeichen in den aktiven Punkt (die Wurzel) einzufügen, und stellen fest, dass es sich dort bereits ist. Also beenden wir den aktuellen Schritt, ohne etwas einzufügen, und aktualisieren den aktiven Punkt auf (root,'a',1) .

Unter Stufe 8 , # =8, wir fügen hinzu b und wie bereits erwähnt, ist dies nur bedeutet, dass wir den aktiven Punkt auf (root,'a',2) und Inkrement remainder ohne zu tun etwas anderes zu tun, denn b ist bereits vorhanden. Allerdings, stellen wir fest (in O(1) Zeit), dass der aktive Punkt jetzt am Ende einer Kante liegt. Wir tragen dem Rechnung, indem wir ihn neu setzen auf (node1,'\0x',0) . Hier verwende ich node1 um auf den internen Knoten der ab Kante endet bei.

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

Zweite Verlängerung: Verwendung von Suffix-Links

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

Jetzt in Schritt # =10 , remainder ist 4, und deshalb müssen wir zuerst abcd (der von vor 3 Schritten übrig geblieben ist) durch Einfügen von d an der aktiven Punkt.

Versuch der Einfügung d am aktiven Punkt führt zu einer Kantenspaltung in O(1) Zeit:

En active_node von dem aus der Split eingeleitet wurde, ist in oben rot markiert. Hier ist die endgültige Regelung, Regel 3:

Nach der Abspaltung einer Kante von einer active_node t Knoten ist, folgen wir dem Suffix-Link, der von diesem Knoten ausgeht, wenn es gibt, und setzen die active_node auf den Knoten, auf den er zeigt. [ ] keinen Suffix-Link gibt, setzen wir den active_node zur Wurzel. active_edge y active_length bleiben unverändert.

Der aktive Punkt ist also jetzt (node2,'c',1) y node2 ist markiert in 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 rechten Knoten und die rechte Kante gesetzt also Einfügen bcd kann durch einfaches Einfügen des letzten Zeichens erreicht werden d am aktiven Punkt.

Dies führt zu einer weiteren Kantenaufspaltung, und aufgrund von Regel 2 wir müssen wir einen Suffix-Link von dem zuvor eingefügten Knoten zu dem neuen erstellen erstellen:

Wir beobachten: Suffix-Links ermöglichen uns den nächsten verbleibender Einsatz mit O(1) Aufwand. Betrachten Sie die Diagramm oben, um zu bestätigen, dass der Knoten mit der Bezeichnung ab i dem Knoten bei b (sein Suffix), und der Knoten bei abc i bc .

Der aktuelle Schritt ist noch nicht abgeschlossen. remainder ist jetzt 2, und wir müssen wir die Regel 3 befolgen, um den aktiven Punkt wieder zurückzusetzen. Da der aktuelle active_node (oben rot) keine Suffix-Verknüpfung hat, setzen wir auf Wurzel. Der aktive Punkt ist nun (root,'c',1) .

Die nächste Einfügung erfolgt also an der einen ausgehenden Kante des Wurzelknotens deren Etikett beginnt mit c : cabxabcd hinter dem ersten Zeichen, d.h. hinter c . Dies führt zu einer weiteren Spaltung:

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

(Ich verwende Graphviz-Punkt für diese kleinen Diagramme. Der neue Suffix-Link veranlasste dot, die bestehenden Kanten neu angeordnet hat. Prüfen Sie also sorgfältig, ob das einzige, was eine neue Suffix-Verbindung ist).

Mit diesem, remainder kann auf 1 gesetzt werden, und da die active_node ist Root, wir verwenden Regel 1, um den aktiven Punkt zu aktualisieren (root,'d',0) . Diese bedeutet, dass die letzte Einfügung des aktuellen Schritts die Einfügung einer einzelnen d bei Root:

Das war der letzte Schritt und wir sind fertig. Es gibt eine Reihe von endgültig Beobachtungen Allerdings:

• Bei jedem Schritt bewegen wir uns # um 1 Position nach vorne. Dadurch werden automatisch alle Blattknoten in O(1) Zeit aktualisiert.

• Sie befasst sich jedoch nicht mit a) irgendwelchen Suffixen verbleibende aus früheren Schritten und b) mit dem letzten Zeichen des aktuellen Schrittes.

• remainder sagt uns, wie viele zusätzliche Einsätze wir brauchen, um machen müssen. Diese Einfügungen entsprechen eins-zu-eins den Endsuffixen von der Zeichenkette, die an der aktuellen Position endet # . Wir betrachten eine nacheinander und fügen sie ein. Wichtig: Jeder Einsatz ist wird in O(1) Zeit durchgeführt, da der aktive Punkt uns genau sagt, wo wir und wir nur ein einziges Zeichen am aktiven Punkt hinzufügen müssen Punkt hinzufügen. Und warum? Weil die anderen Zeichen implizit enthalten (sonst wäre der aktive Punkt nicht dort, wo er ist).

• Nach jeder solchen Einfügung wird die Zahl remainder und folgen Sie der Suffix-Link, wenn es einen solchen gibt. Wenn nicht, gehen wir zu Root (Regel 3). Wenn wir bereits bei Root sind, ändern wir den aktiven Punkt nach Regel 1. Unter In jedem Fall dauert es nur O(1) Zeit.

• Wenn wir bei einem dieser Einsätze feststellen, dass das gewünschte Zeichen Zeichen, das wir einfügen wollen, bereits vorhanden ist, tun wir nichts und beenden den aktuellen Schritt, auch wenn remainder >0. Der Grund dafür ist, dass jede Einfügungen, die übrig bleiben, Suffixe derjenigen sind, die wir gerade versucht haben zu machen. Daher sind sie alle implizit im aktuellen Baum. Die Tatsache dass remainder >0 stellt sicher, dass wir die verbleibenden Suffixe behandeln später.

• Was wäre, wenn am Ende des Algorithmus remainder >0? Dies wird der Fall sein der Fall, wenn das Ende des Textes eine Teilzeichenkette ist, die irgendwo vorher vorkam. In diesem Fall müssen wir ein zusätzliches Zeichen an das Ende der Zeichenkette anhängen, das vorher noch nicht vorkam. In der Literatur wird normalerweise das Dollarzeichen $ wird als Symbol verwendet für das. Warum ist das wichtig? --> Wenn wir später den vervollständigten Suffixbaum für die Suche nach Suffixen verwenden, dürfen wir nur Übereinstimmungen akzeptieren, wenn sie an einem Blatt enden . Andernfalls würden wir eine Menge falscher Treffer erhalten, da es viele viele Zeichenketten implizit die im Baum enthalten sind, aber keine eigentlichen Suffixe der Hauptzeichenkette sind. Erzwingen remainder am Ende 0 zu sein, ist im Wesentlichen ein Weg, um sicherzustellen, dass alle Suffixe an einem Blattknoten enden. Allerdings, wenn wir den Baum verwenden wollen, um zu suchen allgemeine Substrate nicht nur Suffixe des Hauptstrangs ist dieser letzte Schritt in der Tat nicht erforderlich, wie in dem unten stehenden Kommentar des Auftraggebers vorgeschlagen.

• Wie komplex ist also der gesamte Algorithmus? Wenn der Text n Zeichen lang ist, gibt es offensichtlich n Schritte (oder n+1, wenn wir das das Dollarzeichen). In jedem Schritt tun wir entweder nichts (außer Aktualisierung der Variablen), oder wir machen remainder Einfügungen, die jeweils O(1) Zeit. Da remainder zeigt an, wie oft wir nichts getan haben in den vorangegangenen Schritten getan haben, und wird für jede Einfügung, die wir vornehmen, dekrementiert Jetzt ist die Gesamtzahl der Schritte, die wir gemacht haben, genau n (oder n+1). Daher ist die Gesamtkomplexität O(n).

• Es gibt jedoch eine Kleinigkeit, die ich nicht richtig erklärt habe: Es kann vorkommen, dass wir einem Suffix-Link folgen, den aktiven Punkt aktualisieren Punkt, und dann feststellen, dass sein active_length Komponente nicht funktioniert nicht gut mit dem neuen active_node . Betrachten Sie zum Beispiel eine Situation wie diese:

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

Der aktive Punkt sei nun (red,'d',3) und verweist damit auf den Ort hinter dem f über die defg Rand. Nehmen wir nun an, wir haben die notwendigen Aktualisierungen vorgenommen und folgen nun dem Suffix-Link, um den aktiven Punkt zu aktualisieren gemäß der Regel 3. Der neue aktive Punkt ist (green,'d',3) . Allerdings, die d -Kante, die von dem grünen Knoten ausgeht, ist de und hat daher nur 2 Zeichen. Um den richtigen aktiven Punkt zu finden, müssen wir natürlich müssen wir natürlich dieser Kante bis zum blauen Knoten folgen und auf (blue,'f',1) .

In einem besonders schlimmen Fall, dem active_length könnte so groß sein wie remainder , die so groß wie n sein kann. Und es kann durchaus vorkommen dass wir, um den richtigen aktiven Punkt zu finden, nicht nur über eine internen Knoten springen müssen, sondern vielleicht über viele, im schlimmsten Fall bis zu n. Bedeutet das bedeutet das, dass der Algorithmus eine versteckte O(n 2 ) Komplexität, denn in jedem Schritt remainder ist im Allgemeinen O(n), und die Nachkorrekturen an den aktiven Knoten nach einem Suffix-Link könnte auch O(n) sein?

Nein. Der Grund dafür ist, dass wir, wenn wir den aktiven Punkt tatsächlich anpassen müssen (z.B. von grün auf blau, wie oben), bringt uns das zu einem neuen Knoten, der seinen eigenen Suffix-Link hat, und active_length reduziert werden. Als folgen wir der Kette der Suffix-Glieder und nehmen die restlichen Einfügungen vor, active_length kann nur abnehmen, und die Zahl der aktiven Punkte, die wir auf dem Weg auf dem Weg nicht größer sein kann als active_length zu jedem beliebigen Zeitpunkt. Da active_length kann nie größer sein als remainder y remainder ist O(n) nicht nur in jedem einzelnen Schritt, sondern die Gesamtsumme der Inkremente die jemals an remainder im Verlauf des gesamten Prozesses ist O(n) ist, ist auch die Anzahl der aktiven Punktanpassungen begrenzt durch O(n).

Answer 2

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

Zusätzlich verwendete Variablen

1. aktiver Punkt - ein Tripel (aktiver_Knoten; aktive_Kante; aktive_Länge), das angibt, von wo aus wir mit dem Einfügen eines neuen Suffixes beginnen müssen.
2. Restbetrag - zeigt die Anzahl der Suffixe, die wir hinzufügen müssen ausdrücklich . Wenn unser Wort zum Beispiel "abcaabca" lautet und der Rest = 3 ist, bedeutet dies, dass wir 3 letzte Suffixe verarbeiten müssen: bca , ca y a .

Lassen Sie uns das Konzept eines interner Knoten - alle Knoten, mit Ausnahme des Knotens Wurzel y el Blätter son interne Knotenpunkte .

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 die active point y remainder ).

Beobachtung 2

Wenn zu einem bestimmten Zeitpunkt active_length größer oder gleich der Länge der aktuellen Kante ist ( edge_length ), verschieben wir unsere active point runter bis edge_length unbedingt größer ist als active_length .

Lassen Sie uns nun die Regeln neu definieren:

Regel 1

Wenn nach einer Einfügung aus dem aktiver Knoten \= Wurzel die aktive Länge größer als 0 ist, dann:

1. aktiver Knoten wird nicht geändert
2. aktive Länge wird dekrementiert
3. aktive Flanke wird nach rechts verschoben (zum ersten Zeichen des nächsten einzufügenden Suffixes)

Regel 2

Wenn wir eine neue interner Knoten OR eine Einfügemaschine aus einer interner Knoten und dies ist nicht das erste Mal SUCH interner Knoten im aktuellen Schritt, dann verknüpfen wir die vorherige SUCH Knoten mit DIESE eine durch eine Suffix-Link .

Diese Definition des Rule 2 unterscheidet sich von jogojapan", denn hier wird nicht nur die neu erstellt internen Knoten, sondern auch die internen Knoten, aus denen wir eine Einfügung vornehmen.

Regel 3

Nach einer Einfügung aus dem aktiver Knoten was nicht der Wurzel müssen wir dem Suffix-Link folgen und die aktiver Knoten zu dem Knoten, auf den er zeigt. Wenn es keinen Suffix-Link gibt, setzen Sie den aktiver Knoten zum Wurzel Knoten. So oder so, aktive Flanke y aktive Länge bleiben unverändert.

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

Und schließlich die Beobachtung 3:

Wenn das Symbol, das wir dem Baum hinzufügen wollen, bereits auf der Kante liegt, müssen wir gemäß Observation 1 nur aktualisieren active point y remainder und lässt den Baum unverändert. BUT wenn es eine interner Knoten markiert als Suffix-Link erforderlich müssen wir diesen Knoten mit unserem aktuellen active node durch einen Suffix-Link.

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

1. Wenn wir NICHT die Knoten durch einen Suffix-Link verbinden:

   • bevor der letzte Buchstabe hinzugefügt wird c :

   

   • nach Hinzufügen des letzten Buchstabens c :

   

2. Wenn wir DO die Knoten durch einen Suffix-Link verbinden:

   • bevor der letzte Buchstabe hinzugefügt wird c :

   

   • nach Hinzufügen des letzten Buchstabens c :

   

Es scheint keinen signifikanten Unterschied zu geben: Im zweiten Fall gibt es zwei weitere Suffix-Links. Aber diese Suffixe sind richtig und einer von ihnen - vom blauen zum roten Knoten - 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 dem Baum neue Buchstaben hinzufügen, möglicherweise einige Knoten aufgrund der Rule 3 denn wenn es keinen Suffix-Link gibt, dann müssen wir die active_node zur Wurzel.

Als wir den letzten Buchstaben zum Baum hinzufügten, hatte der rote Knoten existierte bereits bevor wir eine Einfügung vom blauen Knoten (die Kante mit der Bezeichnung 'c' ). Da es eine Einfügung vom blauen Knoten gab, markieren wir sie als die einen Suffix-Link benötigen . Dann, unter Berufung auf die aktiver Punkt Ansatz, die active node wurde auf den roten Knoten gesetzt. Aber wir fügen nicht vom roten Knoten aus ein, da der Buchstabe 'c' ist bereits am Rande des Abgrunds. Bedeutet das, dass der blaue Knoten ohne Suffix-Link belassen werden muss? Nein, wir müssen den blauen Knoten mit dem roten Knoten durch eine Suffix-Verbindung verbinden. Warum ist das richtig? Weil der aktiver Punkt Ansatz garantiert, dass wir an die richtige Stelle gelangen, d. h. an die nächste Stelle, an der wir eine Einfügung eines kürzer Suffix.

Schließlich sind hier meine Implementierungen des Suffixbaums:

1. Java
2. C++

Ich hoffe, dass dieser "Überblick" zusammen mit jogojapans detaillierter Antwort jemandem hilft, seinen eigenen Suffix-Baum zu implementieren.

Answer 3

@jogojapan du hast eine tolle Erklärung und Visualisierung gebracht. Aber wie @makagonov erwähnte, fehlen einige Regeln für das Setzen von Suffix-Links. Es ist schön zu sehen, wenn man Schritt für Schritt auf http://brenden.github.io/ukkonen-animation/ durch das Wort "aabaaabb". Wenn Sie von Schritt 10 zu Schritt 11 gehen, gibt es keine Suffix-Verbindung 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-Gebäude-Workflow zu verstehen, aber es war schwer für mich, weil der:

• Kombination von Kanten und Knoten
• Verwendung von Indexzeigern anstelle von Referenzen
• bricht Aussagen;
• Aussagen fortsetzen;

Also habe ich eine solche Implementierung in Java entwickelt, die hoffentlich alle Schritte klarer widerspiegelt und die Lernzeit für andere Java-Anwender verkürzen wird:

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);
        }
    });
  }
}

Answer 4

Danke für das gut erklärte Tutorial von @jogojapan Ich habe den Algorithmus in Python implementiert.

Ein paar kleinere Probleme, die @jogojapan erwähnt hat, stellen sich als größere Probleme heraus anspruchsvoll als ich erwartet habe, und müssen sehr sorgfältig behandelt werden. Es hat mich mehrere Tage gekostet, meine Umsetzung zu bekommen robust genug (nehme ich an). Die Probleme und Lösungen sind unten aufgeführt:

1. Ende mit Remainder > 0 Es hat sich herausgestellt, dass diese Situation auch eintreten kann während des Entfaltungsschritts und nicht nur das Ende des gesamten Algorithmus. Wenn das passiert, können wir den Rest, actnode, actedge und actlength unverändert beenden Sie den aktuellen Entfaltungsschritt und beginnen einen weiteren Schritt, indem Sie entweder weiter falten oder entfalten, je nachdem, ob das nächste Zeichen in der ursprünglichen Zeichenkette auf dem aktuellen Pfad liegt oder nicht.

2. Leap Over Nodes: Wenn wir einem Suffix-Link folgen, den aktiven Punkt aktualisieren und dann feststellen, dass seine active_length-Komponente nicht gut mit dem neuen active_node funktioniert. Wir müssen vorankommen an die richtige Stelle zum Teilen oder Einfügen eines Blattes. Dieser Prozess kann sein nicht so einfach weil sich während des Verschiebens die Aktlänge und der Aktedge ständig ändern, wenn man zurück zum Wurzelknoten die actedge y actlength sein könnte falsch wegen dieser Bewegungen. Wir brauchen zusätzliche Variable(n), um diese Informationen zu speichern.

   

Auf die beiden anderen Probleme wurde bereits hingewiesen von @managonov

3. Split könnte ausarten Wenn Sie versuchen, eine Kante zu teilen, werden Sie manchmal feststellen, dass die Teilungsoperation genau auf einem Knoten liegt. In diesem Fall müssen wir nur ein neues Blatt zu diesem Knoten hinzufügen und es als eine Standard-Kantenaufspaltung betrachten, was bedeutet, dass die Suffix-Links, falls es welche gibt, entsprechend beibehalten werden sollten.

4. Versteckte Suffix-Links Es gibt einen weiteren Sonderfall, der durch Problem 1 y Problem 2 . Manchmal müssen wir über mehrere Knoten zum richtigen Punkt für die Aufteilung springen, wir könnten übertreffen den richtigen Punkt, wenn wir uns bewegen, indem wir die Restzeichenfolge und die Pfadbezeichnungen vergleichen. In diesem Fall wird die Suffix-Verknüpfung unbeabsichtigt vernachlässigt, falls es eine geben sollte. Dies könnte vermieden werden durch den richtigen Punkt nicht vergessen wenn Sie sich vorwärts bewegen. Die Suffix-Verknüpfung sollte beibehalten werden, wenn der geteilte Knoten bereits existiert, oder sogar der Problem 1 geschieht während eines Entfaltungsschritts.

Schließlich ist meine Implementierung in Python ist wie folgt:

• Python

Tipps: Es umfasst eine naive Baumdruck Funktion im obigen Code, die bei der Fehlersuche sehr wichtig ist . Es hat mir eine Menge Zeit gespart und ist praktisch für das Auffinden von Sonderfällen.

Answer 5

Meine Intuition ist die folgende:

Nach k Iterationen der Hauptschleife haben Sie einen Suffixbaum erstellt, der alle Suffixe der vollständigen Zeichenkette enthält, die mit den ersten k Zeichen beginnen.

Dies bedeutet, dass der Suffixbaum zu Beginn einen einzigen 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 die Taste der aktive Punkt. Ich vermute, dass dies der tiefste Punkt im Suffixbaum ist, der einem richtigen Suffix der ersten k Zeichen der Zeichenkette entspricht. (Ich denke, richtig bedeutet, dass das Suffix nicht die gesamte Zeichenfolge sein kann).

Nehmen wir zum Beispiel an, 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, erster, letzter) dargestellt. Das bedeutet, dass Sie sich derzeit an dem Punkt im Baum befinden, den Sie erreichen, wenn Sie beim Knoten origin beginnen und dann die Zeichen in string[first:last] eingeben

Wenn Sie ein neues Zeichen hinzufügen, sehen Sie nach, ob der aktive Punkt noch im bestehenden Baum vorhanden ist. Wenn dies der Fall ist, sind Sie fertig. Andernfalls müssen Sie dem Suffixbaum an der aktiven Stelle einen neuen Knoten hinzufügen, auf die nächste kürzeste Übereinstimmung zurückgreifen und erneut prüfen.

Anmerkung 1: Die Suffix-Zeiger geben einen Verweis auf die nächste kürzeste Übereinstimmung für jeden Knoten.

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

Anmerkung 3: Der Kanonisierungsteil spart lediglich Zeit bei der Überprüfung des aktiven Punktes. Nehmen wir zum Beispiel an, dass Sie immer origin=0 verwenden und nur first und last ändern. 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 zwischenzuspeichern, indem nur die Entfernung vom letzten Knoten aufgezeichnet wird.

Können Sie anhand eines Codebeispiels erläutern, was Sie mit "festen" Begrenzungsvariablen meinen?

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