Come rimuovere la sottostringa dall'albero del suffisso?

Question

Ho esaminato molta letteratura, ma non ho trovato alcuna informazione sull'eliminazione o l'inserimento di sottostringhe nell'albero dei suffissi. Esistono solo gli algoritmi di Ukkonen o McCreight per la costruzione di alberi.
Il modo più semplice è ricostruire l'albero dopo aver eliminato o inserito una sottostringa. Ma penso che esista un modo migliore per farlo.
Ad esempio (le posizioni vengono contate da 0):
Ho un albero di suffisso con "abcdef" e ho bisogno di eliminare i simboli da 1 a 3. E quindi avrò un albero di suffisso con "aef". E poi ho bisogno di aggiungere dalla posizione 1 stringa "come". E dopo questo avrò un albero con suffisso "aasef". Potete aiutarmi?

Answer 1

si stanno missando due compiti nella domanda, prima si cerca il carattere, in secondo luogo si sostituisce il carattere. Suffix tree fa la prima parte a cercare il personaggio per te, ora hai bisogno di un secondo algoritmo per sostituire quel personaggio con un nuovo personaggio. Quando i caratteri vengono sostituiti, l'albero del suffisso originale diventa non valido, quindi l'albero deve essere mappato nuovamente per eseguire una seconda sostituzione.

Quello che ti serve sono due cose, prima "suffix array" questo ti darà più controllo sulla ricerca dei caratteri e sulla loro posizione, secondo è "l'algoritmo della cache" che ti aiuterà con la sostituzione.

Answer 2

Ho appena iniziato a lavorare con gli alberi di suffisso, quindi potrei sbagliarmi, ma sembra che inserzioni o cancellazioni possano cambiare l'albero in modi abbastanza radicali.

"abcdef" è un albero suffisso davvero banale:

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

L'aggiunta di un 'g' alla fine o l'eliminazione della 'a' in principio è incredibilmente facile.

Ma dicono che ficco un altro 'a' nel mezzo:

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

Dobbiamo tornare indietro e controllare ogni lettera dall'inizio per vedere se abbiamo bisogno di inserire un nodo in base a questo. Lo stesso se abbiamo un personaggio dalla fine:

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

Se ora si è inserito qualcosa come "ef" fino alla fine, che ci si deve passare attraverso e aggiungere nuovi nodi in tutto il posto!

L'inserimento di un carattere sembra implicherà riesaminare ogni carattere nella stringa, ad esempio il tempo lineare. Poiché l'algoritmo di Ukkonen impiega già un tempo lineare, non dovrebbe valere la pena di utilizzare alcun algoritmo di inserimento dinamico, dovresti semplicemente rigenerare l'albero da zero ogni volta con la certezza che questo è ancora abbastanza buono.

Se non ti interessa lo spazio, puoi sempre memorizzare nella cache ogni passo dell'algoritmo di generazione dell'albero, quindi quando arriva il momento per un inserimento o una cancellazione al punto x, basta caricare l'albero come costruito fino al punto x .