I suffix tree (o alberi dei suffissi) sono una struttura dati che estrinseca la struttura interna di una parola, in modo tanto profondo da essere fondamentale per diversi tipi di operazioni. Un esempio di queste potrebbe essere la ricerca di un testo in un dizionario. Le parole presenti nel dizionario verrebbero rappresentate da un albero dei suffissi che agirebbe da indice per il testo da cercare. Con questa struttura, la ricerca può essere eseguita in tempo lineare. Altre operazioni che si possono eseguire efficientemente utilizzando i suffix tree è la ricerca di occorrenze di stringhe in un testo, oppure la ricerca di alcune proprietà dei linguaggi, come ad esempio verificare se un linguaggio è un codice, ovvero se è univocamente decifrabile.

In poche parole, un suffix tree di un testo è un albero radicato che consente di rappresentare efficientemente tutti i suffissi di una data parola (testo). Esistono diversi algoritmi per la costruire un suffix tree che usano un approccio radicalmente diverso tra loro. Il primo algoritmo lineare (in tempo) per costruire un suffix tree è stato proposto da Weiner nel 1973 [U]: processa la parola della quale trovare i suffissi da destra a sinistra. Pochi anni dopo, McCreight [McC] disegnò un altro algoritmo in tempo lineare, ma più efficiente in spazio rispetto a quello di Weiner. L’algoritmo di McCreight usa un approccio differente. Ad ogni passo dell’algoritmo esso inserisce nell’albero un suffisso della parola in ordine decrescente rispetto alla loro lunghezza. Più recentemente, Ukkonen [U] ha sviluppato un algoritmo (in tempo lineare) concettualmente differente con tutti i vantaggi di quello di McCreight, ma di più semplice trattazione. L’algoritmo di Ukkonen usa un approccio più naturale per l’uomo, ovvero processare la parola da sinistra a destra. Esso ha inoltre il vantaggio di eseguire la costruzione dell’albero dei suffissi on-line.

Questo lavoro di tesi presenta in dettaglio l’algoritmo di McCreight, spiegando le operazioni coinvolte e presentando lo pseudocodice. Si è scelto di implementare questo algoritmo perché, a differenza degli altri due per i quali sono disponibili in rete diverse implementazioni, non è stata trovata nessuna implementazione. L’algoritmo di McCreight, inoltre, fa uso dei suffix links, ulteriori relazioni tra i nodi dell’albero; nell’articolo originale non era fatta alcuna menzione di come costruire tali link in modo efficiente. Si è scelto allora di implementare l’algoritmo di Mortiti G. Maab [M]. La scelta è stata motivata dal fatto che è un articolo recente e l’algoritmo proposto è di facile comprensione e di non difficile implementazione.

La prima parte della tesi è completamente dedicata alla presentazione e rielaborazione dell’algoritmo di McCreight e Maab usando le fonti [CR], [M], [McC]. Gli ultimi capitoli sono dedicati al software che implementa l’algoritmo di McCreight, inclusi i dettagli sull’interfaccia grafica e sulle strutture dati utilizzate. In particolare, viene fornita una descrizione sull’architettura del sistema realizzato, viene mostrata l’interfaccia grafica tramite la quale l’utente si interfaccia con il sistema e i dettagli su come l’output dell’elaborazione viene mostrato a video: l’utente inserisce in un campo di testo la parola da processare e il software disegna l’albero ottenuto dall’esecuzione dell’algoritmo di McCreight sul testo immesso. Innanzitutto per poter implementare efficientemente l’algoritmo si è reso necessario l’uso di alcune strutture dati classiche, che sono state implementate seguendo [GT]. Si tratta di sequenze, alberi, liste, vettori e iteratori. Inoltre si sono definite strutture dati specifiche per l’algoritmo di McCreight: si sono definite interfacce e implementazioni in Java di tali strutture, cercando di individuare le funzionalità più indicative del suffix tree. Il lavoro di tesi si conclude con il presentare in dettaglio l’implementazione dell’algoritmo di McCreight e dell’algoritmo di Maab (utilizzato da McCreight) spiegando tutte le scelte implementative che differiscono dalla definizione in pseudocodice degli algoritmi. Il progetto è realizzato in Java usando Eclipse e la tesi presenta una breve descrizione degli strumenti software utilizzati per realizzare il sistema.  

Bibliografia