Come funzionano gli alberi Suffix?

Question

Sto passando attraverso il capitolo delle strutture dati in The Algorithm Design Manual e ho trovato Suffix Trees.

I esempio stati:

ingresso:

XYZXYZ$ 
YZXYZ$ 
    ZXYZ$ 
    XYZ$ 
    YZ$ 
    Z$ 
     $ 

uscita:

io non sono in grado di capire come l'albero viene generato dalla data stringa di input. Gli alberi suffissi vengono utilizzati per trovare una data sottostringa in una determinata stringa, ma in che modo l'albero fornito può essere d'aiuto? Capisco un altro esempio dato di un trie mostrato sotto, ma se il trie di sotto viene compattato in un albero di suffisso, allora come sarebbe?

Answer 1

Gli algoritmi efficienti standard per la costruzione di un albero di suffissi sono sicuramente non banale. L'algoritmo principale per farlo è chiamato algoritmo di Ukkonen ed è una modifica dell'algoritmo ingenuo con due ottimizzazioni aggiuntive. Probabilmente stai meglio leggendo this earlier question per i dettagli su come costruirlo.

È possibile costruire alberi di suffisso utilizzando gli algoritmi di inserimento standard, su radix tries per inserire ogni suffisso nell'albero, ma così facendo wlil prendere tempo O (n), che può essere costoso per stringhe di grandi dimensioni.

Per quanto riguarda la ricerca veloce della sottostringa, ricordare che un albero di suffisso è un trie compresso di tutti i suffissi della stringa originale (più un indicatore speciale di fine stringa). Se una stringa S è una sottostringa della stringa iniziale T e hai un trie di tutti i suffissi di T, allora puoi semplicemente fare una ricerca per vedere se T è un prefisso di una qualsiasi delle stringhe in quel trie. Se è così, allora T deve essere una sottostringa di S, poiché tutti i suoi caratteri esistono in sequenza da qualche parte in T. L'algoritmo di ricerca della sottostringa dell'albero di suffisso è precisamente questa ricerca applicata al trie compresso, dove si seguono i bordi appropriati ad ogni passaggio.

Spero che questo aiuti!

Answer 2

Un albero di suffisso, in pratica, compila semplicemente le serie di lettere quando non ci sono scelte da fare. Ad esempio, se si guarda il lato destro del trie nella domanda, dopo aver visto uno w, ci sono solo due scelte: was e when. Nel trie, il as in was e lo hen in when hanno ancora un nodo per ogni lettera. In un albero suffisso, che ci si mettono insieme in quelle due nodi che tengono as e hen, in modo che il lato destro del trie si trasformerebbe in:

Answer 3

Io non sono in grado di capire come questo l'albero viene generato dalla stringa di input specificata.

Essenzialmente si crea un trie patricia con tutti i suffissi che hai elencato. Quando si inserisce in un trie patricia, si cerca nella radice un figlio che inizia con il primo carattere dalla stringa di input, se esiste si continua lungo l'albero, ma se non lo fa, si crea un nuovo nodo fuori dalla radice.La radice avrà tanti bambini quanti caratteri univoci nella stringa di input ($, a, e, h, i, n, r, s, t, w). Puoi continuare quel processo per ogni carattere nella stringa di input.

Gli alberi di suffisso vengono utilizzati per trovare una data sottostringa in una determinata stringa, ma in che modo l'albero fornito può essere d'aiuto?

Se stai cercando la sottostringa "gallina", inizia la ricerca dalla radice per un bambino che inizia con "h". Se la lunghezza della stringa di in "h" figlio continua a elaborare child "h" finché non si arriva alla fine della stringa o si ottiene una mancata corrispondenza dei caratteri nella stringa di input e nella stringa "h" figlio. Se abbini tutto il bambino "h", cioè l'input "gallina" corrisponde a "lui" nel bambino "h", quindi passa ai figli di "h" finché non arrivi a "n", se non riesce a trovare un bambino che inizia con "n" quindi la sottostringa non esiste.

Compact Suffix Trie code:

└── (black) 
    ├── (white) as 
    ├── (white) e 
    │ ├── (white) eir 
    │ ├── (white) en 
    │ └── (white) ere 
    ├── (white) he 
    │ ├── (white) heir 
    │ ├── (white) hen 
    │ └── (white) here 
    ├── (white) ir 
    ├── (white) n 
    ├── (white) r 
    │ └── (white) re 
    ├── (white) s 
    ├── (white) the 
    │ ├── (white) their 
    │ └── (white) there 
    └── (black) w 
     ├── (white) was 
     └── (white) when 

Suffix Tree code:

String = the$their$there$was$when$ 
End of word character = $ 
└── (0) 
    ├── (22) $ 
    ├── (25) as$ 
    ├── (9) e 
    │ ├── (10) ir$ 
    │ ├── (32) n$ 
    │ └── (17) re$ 
    ├── (7) he 
    │ ├── (2) $ 
    │ ├── (8) ir$ 
    │ ├── (31) n$ 
    │ └── (16) re$ 
    ├── (11) ir$ 
    ├── (33) n$ 
    ├── (18) r 
    │ ├── (12) $ 
    │ └── (19) e$ 
    ├── (26) s$ 
    ├── (5) the 
    │ ├── (1) $ 
    │ ├── (6) ir$ 
    │ └── (15) re$ 
    └── (29) w 
     ├── (24) as$ 
     └── (30) hen$