UNA STRUTTURA D’INDICIZZAZIONE DATI EFFICIENTE ED ELEGANTE

BASI TEORICHE PER ALBERO DEI SUFFISSI

Contenuti

Definizione di albero di suffissi

Tecniche per costruire un albero dei suffissi

Vantaggi e Svantaggi

Applicazioni generiche

Definizione: teorica

Un albero dei suffissi è una struttura dati che -per sua natura- evidenzia la struttura di una stringa di caratteri, dandone una rappresentazione interna, mediante i suoi suffissi.

La sua definizione ne caratterizza le parti da cui è composto

Definizione: pratica

Un albero dei suffissi per una stringa di caratteri S di m elementi, è un albero direzionato con esattamente m foglie numerate da 1 ad m, che rappresentano la posizione iniziale del suffisso che termina su quella determinata foglia.

Ogni nodo interno ha almeno due figli, e ogni arco è etichettato con una sottostringa non vuota di S

La concatenazione delle labels degli archi percorsi dalla radice fino alla foglia determinano l’esatto suffisso che comincia dalla posizione indicata dalla foglia stessa

Storia

Il primo algoritmo per la costruzione di alberi dei suffissi in tempi lineari è stato sviluppato da Weiner nel 1973.

Un più efficente algoritmo

per la la riduzione dello spazio necessario è stato introdotto da McCreight nel 1976.

Ukkonen (1995) produsse una variante “on-line” di McCreight che semplifica molto la procedura, sebbene sia intrinsecamente meno efficiente.

Albero implicito di una stringa

un albero implicito di una stringa S come un albero ottenuto dall’albero di S$ ma rimuovendo ogni coppia del simbolo terminale, e rimuovendo ogni nodo che non ha almeno due figli

Algoritmo di costruzione di Ukkonen (1/2)

Ukkonen definì un algoritmo in grado di costruire una sequenza di alberi impliciti, uno per ogni prefisso s[1…i]. Incrementando di passo in passo l’albero implicito (per i che va da 1 ad m) si riesce a costruire l’albero dei suffissi della stringa S di lunghezza m. Il tempo per costruire tale albero è pari a O(m^2) .

L’algoritmo inizia con un albero implicito contenente il primo carattere della stringa. Quindi gli step successivi constano in aggiunte successive di caratteri finchè l’albero non è completo.

Ad ogni passo dell’estensione dei rami dell’albero vengono seguite 3 regole:

1. Se non esiste un arco che comincia con il prefisso che voglio collocare creo un nuovo arco a partire dalla radice

2. Se esiste già una foglia, aggiorno l’arco aggiungendo alla fine dell’etichetta corrispondente il carattere nuovo

3. Se c’è già non faccio nulla (non inserisco archi terminali $).

Algoritmo di costruzione di Ukkonen (2/2)

Tecniche di riduzione del tempo

Il primo trick è il concetto di Suffix link. Per un nodo v con label generica x-alfa, se esiste un altro nodo s(v) con label uguale ad alfa, allora posso creare un link tra v e s(v), una sorta di puntatore, o percorso alternativo che mi permette di passare direttamente da un nodo all’altro.

Il secondo concetto per migliorare i tempi di calcolo è lo Skip/count . Si basa sul concetto di profondità dei nodi.Sfruttando questi accorgimenti è possibile ridurre il tempo di

costruzione dell’albero, il tempo di percorrenza e lo spazio necessario a O(m).

Albero Generalizzato

l’albero generalizzato viene utilizzato quando occorre fare operazioni su più di una singola stringa.

Ogni foglia rappresenta sia un suffisso di una delle due stringhe, sia un suffisso che occorre in entrambe le stringhe. Ogni nodo interno v è marcato con 1 (o 2) dipendentemente se esiste una foglia nel sotto albero di v che rappresenta la stringa S1 (o S2).

Un albero generalizzato può essere costruito in un tempo O(m1+m2) dove m1 e m2 sono la lunghezza delle due stringhe

Applicazioni dell’albero dei suffissi

La forma molto strutturata dell’albero dei suffissi permette di implementare in modo semplice e computazionalmente veloce, molte applicazioni specifiche sulla base dell’osservazione della struttura ripetitiva del modello stesso.

Foglie e nodi interni, insieme ai vari puntatori che posso associare ad essi, possono assumere significati diversi, appropriati all’applicazione che voglio implementare.

1. Pattern matching (exact string matching)

Gli alberi dei suffissi permettono l’individuazione di un pattern di lunghezza n in un tempo O(n+k), dove k è il numero di occorrenze del pattern nel data set.

Il problema dell’Exact Set Matching: Questo problema comporta la ricerca di tutti i match esatti per un set di stringhe. Il tempo di risoluzione con l’albero dei suffissi è ancora una volta in O(n + k),

dove n è la lunghezza totale del set di patterns

Il procedimento: si segue, a partire dalla radice, l’arco etichettato con i caratteri del pattern

cercato, ci si ferma o quando arrivo in fondo al pattern e si osserva la foglia finale o quando si trova un mis-match sull’arco (nel qual caso il pattern non è

presente tra i dati).

Il cammino percorso durante la ricerca è unico.

2. La più lunga sottostringa comune

Questo problema può essere risolto, attraverso un albero dei suffissi generalizzato di dimensione m, in un tempo O(m). Per farlo è richiesto sfruttare due valori associati ad ogni nodo interno:  String coverage c(v) – il numero di stringhe distinte sottese

dai suffissi nei figli di v. string-depth d(v) – il numero di caratteri che costituiscono

l’etichetta suffisso per il nodo v.

La più lunga sottostringa comune è identificata dal nodo interno marcato da tutte le stringhe, e con la maggiore profondità di stringa.

3. Sottostringhe comuni per più di due stringhe

Estensione concettuale della ricerca della più lunga sottostringa comune. Al posto di calcolare singolarmente i coverage string per ogni nodo si genera una lista delle profondità di stringa e una lista di stringhe uniche

Ogni nodo ha sotteso più di un finale di stringa. Per esempio il nodo 8 indica che le stringhe 1, 2, 3 e 4 hanno una comune sottostringa di lunghezza 8

4. Problema dell’accavallamento ( prefisso-suffisso comune)

Si tratta di distinguere la più lunga parte comune di stringa in un set di stringhe, nell’ipotesi che nessuna stringa sia sottostringa di un’altra.

La risoluzione di questo problema si riduce alla determinazione del prefisso non comune all’altra stringa.

Per esempio, date due sequenze S1=ABACD e S2=acdef

A B A C D a c d e f

  La componente comune è “acd” e il prefisso non comune è “AB”. Per individuarlo si ricorre alla ricerca di un arco terminale ( ovvero

un arco dell’albero etichettato dal solo terminatore di stringa $). La presenza di un arco terminale indica che l’arco che lo precede

sul cammino sarà un suffisso finale, ma al contempo esso rappresenterà un prefisso per l’altro cammino che parte da quel nodo.