La struttura dati Suffix Tree: teoria e pratica

La tesi affronta lo studio delle strutture dati per l’indicizzazione di stringhe, concentrandosi sui Suffix Tree e, in particolarmente sulla sua variante compressa: Compressed Suffix Tree. Dopo una presentazione dei concetti di base relativi alle stringhe e alle operazioni fondamentali, su di esse, vengono descritti i concetti fondamentali del Suffix Tree e brevemente i vari algoritmi di costruzione, dando risalto all’algoritmo di Ukkonen, che è efficiente e semplice da implementare. Successivamente, viene discusso il problema del costo di memoria dei Suffix Tree classici, citando diverse varianti compresse sviluppate nel tempo. La tesi analizza il Compressed Suffix Tree di Sadakane andando a studiare in dettaglio le strutture ausiliarie che utilizza: Suffix Array, LCP array e rappresentazione a parentesi bilanciate. L’albero compresso mantiene le stesse funzionalità del suffix tree classico, ma con un compromesso tra spazio e tempo.