Jak usunąć podciągi z drzewa sufiksów?

Question

Sprawdziłem wiele literatury, ale nie znalazłem żadnych informacji o usuwaniu lub wstawianiu podciągów do drzewa sufiksów. Istnieją tylko algorytmy Ukkonena lub McCreighta do budowania drzewa.
Najbiedniejszym sposobem jest odbudowanie drzewa po usunięciu lub wstawieniu podciągu. Ale myślę, że jest to najlepszy sposób na zrobienie tego.
Na przykład (pozycje są liczone od 0):
Mam drzewo przyrostków z "abcdef" i muszę usunąć symbole od 1 do 3. A potem będę mieć drzewo przyrostków z "aef". A następnie muszę dodać z pozycji 1 ciąg "jak". A potem będę miał drzewo przyrostków z "aasef". Czy możesz mi pomóc?

Answer 1

mieszacie dwa zadania w pytaniu, najpierw szukacie bohatera, a następnie zastępujecie go. Drzewo przyrostków wykonuje pierwszą część szukania dla ciebie, teraz potrzebujesz drugiego algorytmu, który zastąpi tę postać nowym znakiem. Gdy znaki zostaną zastąpione, oryginalne drzewo sufiksu staje się nieważne, więc drzewo musi zostać ponownie zamapowane, aby wykonać drugie zastąpienie.

Potrzebne są dwie rzeczy, pierwsza "tablica sufiksów" da ci większą kontrolę nad wyszukiwaniem znaków i ich lokalizacją, druga to "algorytm pamięci podręcznej", który pomoże ci w zastąpieniu.

Answer 2

Dopiero co zacząłem pracować z drzewkami przyrostków, więc mogę się mylić, ale wygląda na to, że wstawienia lub usunięcia mogą zmienić drzewo na dość radykalny sposób.

„abcdef” jest naprawdę trywialne drzewo przyrostek:

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

Dodawanie „g” na końcu lub usuwając „a” na początku jest niezwykle łatwe.

Ale powiedzieć, że wpakować kolejny „a” w środku:

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

Musimy wrócić i sprawdzić każdy list od samego początku, aby zobaczyć czy musimy wstawić węzeł na podstawie tego. Samo, jeśli mamy znak od końca:

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

Jeśli teraz dodaje coś jak „ef” do końca, trzeba przejść i dodać nowe węzły w każdym miejscu!

Wstawienie postaci wygląda tak, jakby wymagało ponownego rozpatrzenia każdego znaku w ciągu, tj. Czasu liniowego. Ponieważ algorytm Ukkonena zajmuje już czas liniowy, nie powinien być wart wykorzystania algorytmu dynamicznego wstawiania, powinieneś tylko zregenerować drzewo od początku za każdym razem z przekonaniem, że jest to wciąż całkiem dobre.

Jeśli nie dbasz o przestrzeń, zawsze możesz buforować każdy krok algorytmu generowania drzewa, a następnie, gdy przychodzi czas na wstawienie lub usunięcie w punkcie x, po prostu załaduj drzewo jako skonstruowane do punktu x .