Wie Teilstring aus Suffix-Baum entfernen?

Question

Ich habe viel Literatur rezensiert, aber ich habe keine Informationen über das Löschen oder Einfügen von Teilstrings in den Suffixbaum gefunden. Es gibt nur Algorithmen von Ukkonen oder McCreight zum Aufbau von Bäumen.
Der schlechteste Weg besteht darin, den Baum nach dem Löschen oder Einfügen einer Teilzeichenfolge neu zu erstellen. Aber ich denke, dass es einen besten Weg gibt, es zu tun.
Zum Beispiel (Positionen werden von 0 gezählt):
Ich habe Suffixbaum mit "abcdef" und ich muss Symbole von 1 bis 3 löschen. Und dann habe ich Suffixbaum mit "Aef". Und dann muss ich aus Position 1 String "as" hinzufügen. Und danach werde ich einen Suffixbaum mit "aasef" haben. Können Sie mir helfen?

Answer 1

Sie mischen zwei Aufgaben in Ihrer Frage, zuerst nach dem Zeichen suchen, zweitens das Zeichen ersetzen. Suffix-Baum sucht der erste Teil das Zeichen für Sie, jetzt brauchen Sie einen zweiten Algorithmus, um diesen Charakter durch neues Zeichen zu ersetzen. Wenn die Zeichen ersetzt werden, wird der ursprüngliche Suffixbaum ungültig, so dass der Baum erneut gemappt werden muss, um einen zweiten Austausch durchzuführen.

Was Sie brauchen, ist zwei Dinge, zuerst "Suffix-Array" Dies gibt Ihnen mehr Kontrolle über die Suche nach Zeichen und ihrer Position, zweitens ist der "Cache-Algorithmus" dies wird Ihnen mit Ersatz helfen.

Answer 2

Ich habe gerade erst damit begonnen, mit Suffix-Bäumen zu arbeiten, also könnte ich mich irren, aber es scheint, als ob Einfügungen oder Löschungen den Baum auf ziemlich radikale Weisen ändern können.

"abcdef" ist ein wirklich trivial Suffixbaum:

abcdef 
├a..$ 
├b..$ 
├c..$ 
├d..$ 
├e..$ 
└f$ 

ein 'g' am Ende oder das Löschen der 'a' am Anfang einfach unglaublich Hinzufügen.

Aber sagen wir ein anderes ‚a‘ in der Mitte schieben:

abcadef 
├a 
│├b..$ 
│└d..$ 
├b 
├c 
├... 

Wir müssen zurückgehen und prüfen jeden Brief von Anfang an zu sehen, ob wir einen Knoten einfügen müssen auf dieser Basis. Gleiches gilt, wenn wir ein Zeichen vom Ende haben:

abafef 
├a 
│├bafef$ 
│└fef$ 
├bafef$ 
├f 
│├ef$ 
│└$ 
└ef$ 

Wenn Sie jetzt so etwas wie „ef“ bis zum Ende eingefügt, dann würden Sie durchlaufen müssen und neue Knoten überall gibt!

Das Einfügen eines Zeichens sieht so aus, als würde jedes Zeichen in der Zeichenkette, dh die lineare Zeit, erneut untersucht werden. Da Ukkonens Algorithmus bereits lineare Zeit benötigt, sollte es sich nicht lohnen, einen dynamischen Einfügealgorithmus zu verwenden. Sie sollten den Baum einfach jedes Mal neu generieren, mit der Gewissheit, dass dies immer noch ziemlich gut ist.

Wenn Sie sich nicht um Speicherplatz kümmern, können Sie jeden Schritt des Baumgenerierungsalgorithmus zwischenspeichern. Wenn es an einem Punkt x eingefügt oder gelöscht werden soll, laden Sie einfach den Baum bis zum Punkt x hoch .