Come e quando creare un suffisso link nell'albero dei suffissi?

Question

Qualcuno potrebbe darmi un esempio su come e quando creare un suffisso link nella struttura dei suffissi?

Se la mia stringa è ABABABC, ma utilizzare un esempio diverso se è meglio.

Spero di dare qualche foto per illustrare ogni passaggio.

molto apprezzato.

Answer 1

Per comprendere ciò, prima richiamo che ci sono tre tipi di nodi in un albero suffisso:

• La radice
• nodi interni
nodi
• Foglia

Nel grafico sotto, che è l'albero del suffisso per ABABABC, il cerchio giallo è la radice , quelli grigio, blu e verde sono interni nodi e quelli piccoli neri sono foglie .

ci sono due cose importanti da notare:

• I nodi interni hanno sempre più di 1 bordo in uscita. Cioè, i nodi interni contrassegnano quelle parti dell'albero in cui si verifica la diramazione .

• La ramificazione si verifica ovunque sia implicata una stringa ripetuta e solo . Per qualsiasi nodo interno X, la stringa che porta dalla radice a X deve essere verificata nella stringa di input almeno tante volte in quanto ci sono bordi in uscita da X.

Esempio: La stringa che porta al nodo blu è ABAB. Infatti, questa stringa appare due volte nella stringa di input: In posizione 0 e in posizione 2. Ed è per questo che esiste il nodo blu.

Ora circa i collegamenti di suffisso:

1. Se la stringa s che porta fino a qualche nodo X interno è più lungo di 1 carattere, la stessa stringa meno il primo carattere (chiamata questo s _-1) deve essere nella struttura, troppo (si tratta di un albero suffissi, dopo tutto, quindi il suffisso di una qualsiasi delle sue corde deve essere 01.235.nell'albero, anche).

   Esempio: Sia s = ABAB, la stringa che conduce al nodo blu. Quindi dopo aver rimosso il primo carattere, s _-1 è BAB. E effettivamente quella stringa si trova anche nell'albero. Porta al nodo verde .

2. Se qualche stringa s porta ad un nodo interno, la sua ridotta versione s -1 must portare ad un nodo interno (chiamata It X _-1) pure. Perché? Poiché s deve apparire almeno due volte nella stringa ingresso, così s -1 deve apparire almeno tante volte (perché è parte di s: dove compare s, s _-1 deve apparire anche). Ma se s _{-1 appare più volte nella stringa di input, quindi ci deve essere un nodo interno per esso.}

3. In tale situazione, un collegamento speciale collegamento X a X _-1 è un collegamento suffisso.

Nota: causa di (1) e (2) di cui sopra, ogni nodo interno X che ha un'etichetta dalla radice a X superiore a 1 carattere must hanno un suffisso link a esattamente un altro nodo interno.

Esempio:

Questo è lo stesso albero suffisso come prima; le linee tratteggiate indicano i collegamenti suffisso .Se si inizia dal nodo blu e si seguono i suffissi da lì (dal blu, al verde, al primo grigio, al secondo grigio), e si guardano le stringhe che portano dalla radice a ciascun nodo, si vedrà vedere questo :

ABAB -> BAB -> AB -> B 
(blue)  (green)  (gray1)  (gray2) 

Questo è il motivo per cui essi sono chiamati suffisso collega (l'intera sequenza è chiamato catena suffisso).

A cosa servono?

Sono buoni per sorprendentemente molte cose. Tuttavia, essi svolgono un ruolo particolare in Ukkonen's algorithm for suffix tree construction, specificamente in Regola 3 ivi indicato: Dopo aver inserito un carattere finale di alcuni suffisso s ad un certo punto X, l'algoritmo deve inserire il carattere finale di suffisso s _-1 in O (1) tempo. In per farlo, usa il suffisso per saltare direttamente al posto X _-1 e fa l'inserto.

Ma, nota che non è necessario mettere i collegamenti suffisso in un albero di suffisso. Non fanno parte della definizione di un albero suffisso —, sono solo collegamenti speciali utilizzati da alcuni algoritmi che costruiscono o utilizzano alberi di suffisso.

---

Riguardo nodi singolo carattere: se v'è un nodo X interno la cui stringa (cioè la corda sul percorso dalla radice a X) è costituito da un solo carattere? Con la definizione di cui sopra, X quindi non ha un suffisso link. Tuttavia, si può presumere che se avesse un suffisso link, farebbe riferimento al nodo radice. Inoltre: se, con la definizione sopra, un nodo interno non ha un suffisso, deve essere un nodo a carattere singolo, quindi puoi sempre presumere che se non è presente un suffisso in un nodo interno deve essere un singolo Nodo carattere, e quindi, il nodo che rappresenta il suffisso s _-1 è il nodo radice. (Alcuni algoritmi potrebbero in realtà aggiungere un suffisso esplicito che punta al nodo radice in questo caso). Grazie a j_random_hacker per il commento su questo.