Suffice tree and Tries. Qual è la differenza?

Question

Sto leggendo su Tries comunemente noto come alberi Prefisso e Suffix Trees.
Anche se ho trovato il codice per un Trie non riesco a trovare un esempio per un Suffix Tree. Inoltre ho la sensazione che il codice che costruisce uno Trie sia lo stesso di uno Suffix Tree con la sola differenza che nel primo caso memorizziamo prefissi ma negli ultimi suffissi.
È vero? Qualcuno può aiutarmi a chiarire questo nella mia testa? Un codice di esempio sarebbe di grande aiuto!

Answer 1

Un albero di suffisso può essere visualizzato come una struttura di dati costruita sopra un trie dove, invece di aggiungere semplicemente la stringa stessa nel trie, si aggiungerà anche ogni possibile suffisso di quella stringa. Per fare un esempio, se si voleva indice stringa banane in un albero suffisso, si dovrebbe costruire un trie con le seguenti stringhe:

banana 
anana 
nana 
ana 
na 
a 

Una volta fatto ciò è possibile cercare per ogni n-gram e vedere se è presente nella stringa indicizzata. In altre parole, la ricerca n-gram è una ricerca prefisso di tutti i possibili suffissi della stringa.

Questo è il modo più semplice e più lento per creare un albero di suffisso. Si scopre che ci sono molte varianti più elaborate su questa struttura dati che migliorano in entrambi o nello spazio e nei tempi di costruzione. Non sono abbastanza esperto in questo settore per dare una visione d'insieme, ma puoi iniziare esaminando suffix arrays o questa classe advanced data structures (lezione 16 e 18).

Questo answer fa anche un ottimo lavoro spiegando una variante di questa struttura dati.

Answer 2

Se si immagina un Trie in cui si mettono i suffissi di una parola, è possibile interrogarlo molto facilmente per le sottostringhe della stringa. Questa è l'idea principale dietro l'albero del suffisso, fondamentalmente è un "suffisso trie".

Ma usando questo approccio ingenuo, la costruzione di questo albero per una stringa di dimensione n sarebbe O (n^2) e richiedere molta memoria.

Poiché tutte le voci di questo albero sono suffissi della stessa stringa, condividono molte informazioni, pertanto sono disponibili algoritmi ottimizzati che consentono di crearli in modo più efficiente. L'algoritmo di Ukkonen, ad esempio, consente di creare un albero di suffisso online in O (n) complessità temporale.

Answer 3

La differenza è molto semplice. Un albero di suffisso ha meno nodi "fittizi" del suffisso trie. Questi nodi fittizi sono singoli caratteri che aumentano l'operazione di ricerca nell'albero