Albero dei suffissi

Un albero dei suffissi (suffix tree in inglese) è una struttura dati che evidenzia la struttura interna di una stringa in un modo da facilitare operazioni comuni come la ricerca di sottostringhe. Gli alberi dei suffissi permettono di risolvere il problema del matching esatto in tempo lineare (al pari di altri algoritmi come Knuth-Morris-Pratt, Boyer-Moore...) ma la loro principale virtù è che essi possono essere usati per risolvere in tempo lineare molti altri problemi più complessi del pattern matching esatto.

L'applicazione classica degli alberi dei suffissi è il problema della sottostringa: dato un testo T di lunghezza n, dopo una preelaborazione del testo (costruzione dell'albero dei suffissi) che richiede tempo $O(n)$, è possibile rispondere in tempo $O(m)$ alla domanda se una stringa S di lunghezza m compare in T.

In altre parole, la preelaborazione del testo richiede tempo proporzionale alla sua lunghezza n ma dopo tale preelaborazione ogni ricerca nel testo T di una stringa S richiede soltanto tempo proporzionale alla lunghezza m della stringa cercata indipendentemente dalla lunghezza n del testo T.

Concetti di base

Un albero dei suffissi A per una stringa S di lunghezza n è un albero radicato tale che:

1. Ci sono esattamente n foglie numerate da 1 ad n.
2. Ogni nodo interno, esclusa al più la radice, ha almeno due figli.
3. Ogni arco è etichettato con una sottostringa di S.
4. Due archi uscenti dallo stesso nodo non possono avere etichette che iniziano con lo stesso carattere.
5. La concatenazione delle etichette lungo il cammino dalla radice alla foglia numerata i è esattamente il suffisso S[i, n] di S di lunghezza n − i + 1.

Esempio di albero dei suffissi per la stringa "dabdac"

Ad esempio l'albero dei suffissi per la stringa "dabdac" è quello illustrato nella figura. Lungo il cammino dalla radice alla foglia 1 si legge l'intera stringa "dabdac" mentre lungo il cammino dalla radice alla foglia 2 si legge il suffisso "abdac" che inizia nella posizione 2 della stringa. Il nodo r è la radice ed i nodi u e w sono nodi interni. La definizione precedente non garantisce l'esistenza di un albero dei suffissi per ogni stringa. Il problema è che se qualche suffisso è prefisso di un altro suffisso di S il cammino relativo a tale suffisso non termina in una foglia. Ad esempio se togliamo l'ultimo carattere c alla stringa "dabdac" ottenendo la stringa "dabda", il suffisso a è prefisso di "abda" e quindi il cammino relativo ad a non termina in una foglia ma termina in un punto intermedio del cammino relativo ad "abda".

Per evitare questo problema si assume che ogni stringa S termini con un carattere diverso da tutti gli altri caratteri della stringa in modo che nessun suffisso possa essere prefisso di un altro suffisso. Se ciò non è vero possiamo sempre aggiungere alla fine della stringa un carattere sentinella che non appartiene all'alfabeto su cui è costruita la stringa. In seguito ci riferiremo a questo carattere con $.

Inoltre l'etichetta di un cammino dalla radice ad un nodo (interno o foglia) è la concatenazione delle etichette degli archi del cammino. L'etichetta di un nodo u è l'etichetta del cammino dalla radice a u. In particolare l'etichetta della radice è la stringa nulla e l'etichetta di una foglia è il suffisso associato a tale foglia.

La profondità di un nodo è la lunghezza della sua etichetta.

Se l'etichetta di un arco (u, v) tra due nodi u e v ha lunghezza k maggiore di 1 l'arco (u, v) è suddiviso in k parti (una per ogni carattere dell'etichetta) mediante k − 1 nodi impliciti le cui etichette sono la concatenazione dell'etichetta di u con i caratteri dell'etichetta dell'arco (u, v) che precedono il nodo implicito stesso.

Ad esempio, nella figura, la stringa "da" è etichetta del nodo w mentre la stringa "dabd" è etichetta di un nodo implicito interno all'arco (w, 1).

Matching esatto usando l'albero dei suffissi

Gli alberi dei suffissi risolvono il problema del matching esatto basandosi sui seguenti passi:

1. Costruisci l'albero dei suffissi A del testo T.
2. Confronta i caratteri del pattern P con i caratteri dell'unico cammino in A individuato da essi (ricordiamo che le etichette degli archi uscenti da un nodo interno iniziano con caratteri distinti) fino a che il pattern non sia finito oppure si arrivi ad un carattere del pattern che non compare in nessuna prosecuzione del cammino percorso fino a quel momento. In quest'ultimo caso P non compare in nessuna posizione del testo T.
3. Se si arriva alla fine del pattern allora il pattern è uguale all'etichetta del nodo u (implicito o esplicito) a cui si e arrivati e quindi P è prefisso di tutti i suffissi associati alle foglie del sottoalbero radicato in u. Le posizioni di inizio di tali suffissi (che sono memorizzate nelle foglie) sono quindi tutte e sole le posizioni in cui P occorre in T. Tali posizioni vengono quindi collezionate percorrendo il sottoalbero radicato in u.

La costruzione dell'albero dei suffissi si può fare in tempo $O(n)$. Quindi il primo passo richiede tempo $O(n)$.

Nel secondo passo, per ogni carattere del pattern viene effettuato un solo confronto se siamo in un nodo implicito (e quindi vi è una sola possibile continuazione del cammino) e al più tanti confronti quanti sono gli archi uscenti se siamo in un nodo esplicito. Siccome i primi caratteri delle etichette degli archi uscenti da un nodo esplicito sono tutti distinti e l'alfabeto è prefissato il numero di confronti risulta in ogni caso minore od uguale al numero di caratteri dell'alfabeto che è una costante. Dunque è richiesto un tempo costante per ogni carattere del pattern ed il secondo passo si esegue in tempo $O(m)$. Il terzo passo richiede tempo proporzionale al numero di nodi del sottoalbero radicato nel vertice u.

Se nel testo T vi sono k occorrenze del pattern, tale sottoalbero ha esattamente k foglie. Siccome ogni nodo interno ha almeno due archi uscenti, il numero di nodi interni è minore o uguale a k − 1 (uguale solo se ogni nodo interno ha esattamente due archi uscenti e quindi l'albero e un albero binario). Dunque il terzo passo richiede tempo $O(k)$. Siccome k ≤ n il tempo totale richiesto è $O(n+m)$, uguale a quello richiesto da altri algoritmi di pattern matching. Ma la distribuzione del lavoro è molto diversa. In altri algoritmi il tempo totale è diviso in un tempo $O(m)$ per preelaborare il pattern P ed un tempo $O(n)$ per cercare tutte le occorrenze del pattern P nel testo T. Invece usando l'albero dei suffissi si spende un tempo $O(n)$ per preelaborare il testo T e quindi soltanto tempo $O(m+k)$ per trovare tutte le k occorrenze di un qualsiasi pattern P nel testo T.

Il vantaggio risulta chiaro nel caso in cui si debbano effettuare molte ricerche con pattern diversi in un unico grande testo.

Un metodo ingenuo per costruire l'albero dei suffissi

Un algoritmo diretto per costruire l'albero dei suffissi di una stringa S allo scopo di approfondire il concetto di albero dei suffissi e sviluppare l'intuizione su di esso è il seguente. Questo algoritmo ingenuo inizia la costruzione dell'albero dei suffissi con un solo arco per il suffisso S[1, n]$ (l'intera stringa); quindi aggiunge uno alla volta i suffissi S[i, n]$ per i = 2, ..., n+1 (essendo il +1 dovuto al simbolo $). Indichiamo con $A_{i}$ l'albero intermedio che contiene i suffissi che iniziano nelle posizioni da 1 a i. L'albero $A_{1}$ consiste di un unico arco etichettato con la stringa S[1, n]$ che congiunge la radice ad una foglia numerata 1. Ogni albero $A_{i+1}$ viene costruito a partire da $A_{i}$ nel seguente modo:

1. Partendo dalla radice di $A_{i}$ cerca il più lungo cammino dalla radice ad un nodo (implicito od esplicito) la cui etichetta è prefisso del suffisso S[i+1, n]$ da aggiungere. Tale ricerca si effettua partendo dal cammino nullo (che inizia e termina nella radice e che ha la stringa nulla come etichetta) ed estendendolo, finché è possibile, aggiungendo uno alla volta i caratteri del suffisso S[i+1, n]$. Il cammino che si ottiene in questo modo è unico in quanto il carattere successivo di un nodo implicito è unico e le etichette degli archi uscenti da un nodo esplicito iniziano con caratteri distinti. Inoltre l'estensione deve terminare prima della fine del suffisso S[i+1, n]$ in quanto la presenza della sentinella $ ci assicura che il suffisso S[i+1, n]$ non è prefisso di nessuno dei prefissi più lunghi inseriti precedentemente nell'albero.
2. Se il nodo a cui si arriva è un nodo implicito tale nodo implicito viene sostituito con un nodo esplicito spezzando l'arco che lo contiene in due archi (e l'etichetta in due etichette).
3. A questo punto il nodo u a cui siamo arrivati è un nodo esplicito con etichetta il prefisso S[i+1, j] di S[i+1, n]$ e tale che, nell'albero, non ci sia nessun nodo con etichetta S[i+1, j+1]. Quindi tutti gli archi uscenti da u hanno etichette che iniziano con un carattere diverso dal carattere S[j+1]. Aggiungiamo un nuovo arco (u, i+1) con etichetta S[j+1, n]$ che congiunge il nodo u con una nuova foglia numerata i+1. A questo punto l'albero contiene un unico cammino dalla radice alla foglia i+1 la cui etichetta è il suffisso S[i+1, n]$ ed abbiamo quindi ottenuto l'albero successivo $A_{i+1}$.

Assumendo che la dimensione dell'alfabeto sia limitata da una costante, l'algoritmo ingenuo richiede tempo $O(n^{2})$. Nel caso in cui il numero di simboli |Σ| dell'alfabeto Σ non sia limitato da una costante la complessita è $O(n^{2}|\Sigma |)$, che si può ridurre ad $O(n^{2}\log {|\Sigma |})$ usando un metodo efficiente per cercare l'arco su cui proseguire in corrispondenza dei nodi espliciti.

Un'animazione della costruzione dell'albero dei suffissi per la stringa "dabdac" con questo algoritmo ingenuo è la seguente:

Costruzione dell'albero dei suffissi per la stringa "dabdac" con un algoritmo ingenuo

L'algoritmo di Ukkonen

Il primo a scoprire un algoritmo per la costruzione dell'albero dei suffissi in tempo lineare è stato Weiner nel 1973. Per l'originalità e l'importanza del risultato tale algoritmo venne dichiarato "algoritmo dell'anno". Negli anni successivi tale algoritmo ricevette sempre meno attenzione, probabilmente perché risulta difficile da capire e da implementare correttamente. Qualche anno dopo Ukkonen ha proposto un algoritmo completamente diverso. Esso richiede meno memoria di quello di Weiner ed inoltre è più semplice da capire partendo, nella descrizione, da un algoritmo molto inefficiente ($O(n^{3})$) a cui si applicano poi dei trucchi per ridurre la complessità in modo da renderlo lineare.

Alberi dei suffissi impliciti

L'algoritmo di Ukkonen costruisce una successione di alberi dei suffissi impliciti, l'ultimo dei quali viene poi trasformato in un vero albero dei suffissi per la stringa S$. La definizione di albero dei suffissi implicito I per una stringa S è la stessa di albero dei suffissi da cui viene però rimossa la condizione che il cammino relativo ad ogni suffisso della stringa S termini in una foglia ed inoltre si considera anche il suffisso nullo. Quindi l'albero dei suffissi implicito esiste per ogni stringa S, anche quelle aventi dei suffissi che sono prefissi di altri suffissi e per le quali non esiste un albero dei suffissi esplicito. Semplicemente, se un suffisso è prefisso di un altro suffisso, nell'albero dei suffissi implicito il cammino relativo a tale suffisso termina in un nodo interno (implicito od esplicito) nel cammino relativo al suffisso di cui esso è prefisso.

La relazione tra alberi dei suffissi impliciti ed alberi dei suffissi espliciti è chiarita dalla seguente asserzione: l'albero dei suffissi implicito di una stringa S si ottiene dall'albero dei suffissi per la stringa S$ togliendo il simbolo sentinella $ da tutte le etichette che lo contengono, eliminando gli eventuali archi la cui etichetta si riduce alla stringa nulla e la foglia corrispondente (essi sono sicuramente archi che terminano in una foglia) ed eliminando infine gli eventuali nodi interni espliciti aventi un solo arco uscente. Anche se un albero dei suffissi implicito può non avere una foglia per ogni suffisso della stringa S esso contiene ugualmente tutti i suffissi di S (compreso il suffisso nullo) come etichette di qualche nodo (implicito o esplicito). L'unico problema è che se tale cammino non termina in una foglia non vi è alcuna indicazione del punto in cui tale cammino termina. Naturalmente, se nessun suffisso (escluso quello nullo) è prefisso di un altro suffisso, l'albero dei suffissi implicito e l'albero dei suffissi esplicito coincidono.

Descrizione astratta dell'algoritmo di Ukkonen

L'algoritmo di Ukkonen costruisce un albero dei suffissi implicito $I_{i}$ per ogni prefisso S[1, i] della stringa S$ di lunghezza n+1 partendo da $I_{0}$ e incrementando i di uno finché non si arrivi a costruire $I_{n+1}$. Siccome nessun suffisso della stringa S$ è prefisso di un altro suffisso l'albero dei suffissi implicito $I_{n+1}$ coincide con l'albero dei suffissi A della stringa S$. In realtà, per ottenere A da $I_{n+1}$ è richiesta una trasformazione finale dovuta al fatto che per gli alberi dei suffissi impliciti si usa una rappresentazione leggermente diversa da quella usata per gli alberi dei suffissi.

La descrizione astratta dell'algoritmo di Ukkonen è quindi la seguente:

 UKKONEN(S)
   /* Precondizione: S stringa di lunghezza n. */
   "Aggiungi ad S la sentinella ottenendo la stringa S $ di lunghezza n+1."
   "Costruisci $I_{0}$."
   for i ← 0 to n do
     /* Estensione da Ii ad Ii+1. */
     for j ← 1 to i + 1 do
       "Cerca la fine del cammino corrispondente al suffisso S[j, i]
        della sottostringa S[1, i] di cui $I_{i}$ è l'albero dei suffissi
        implicito e, se necessario, estendi tale cammino aggiungendo
        il carattere S[i+1] in modo tale che il suffisso S[j, i+1] di
        S[1, i+1] sia rappresentato nell'albero."

La costruzione di $I_{0}$ è facile. $I_{0}$ ha soltanto la radice e nessun arco uscente. In esso è rappresentato l'unico suffisso del prefisso nullo S[1, 0], il suffisso nullo appunto. Vediamo quindi come eseguire l'estensione da $I_{i}$ ad $I_{i+1}$ ed in particolare come si effettua l'estensione di un suffisso S[j, i] di S[1, i] nel suffisso S[j, i+1] di S[1, i+1].

Di seguito l'estensione da $I_{i}$ ad $I_{i+1}$ ed in particolare come si effettua l'estensione di un suffisso S[j, i] di S[1, i] nel suffisso S[j, i+1] di S[1, i+1].

Abbiamo tre casi possibili:

• Caso 1: nell'albero corrente il cammino etichettato S[j, i] termina in una foglia numerata j. In questo caso il nuovo carattere S[i+1] viene aggiunto all'etichetta dell'ultimo arco di tale cammino (quello che termina nella foglia).
• Caso 2: nell'albero corrente il cammino etichettato S[j, i] termina in un nodo u interno (implicito o esplicito) ma nessun cammino che parte da u inizia con il carattere S[i+1]. In questo caso viene creata una nuova foglia etichettata j connessa al nodo u con un arco etichettato con il carattere S[i+1]. Nel caso in cui u sia un nodo implicito, prima di fare ciò, il nodo u viene sostituito con un nodo esplicito che suddivide in due parti l'arco a cui esso appartiene.
• Caso 3: nell'albero corrente il cammino etichettato S[j, i] termina in un nodo u interno (implicito o esplicito) e almeno un cammino che parte da u inizia con il carattere S[i+1]. In questo caso il suffisso S[j, i+1] è già presente nell'albero e non occorre fare niente.

Dopo aver esteso tutti i suffissi di S[1, i] siamo sicuri che nell'albero ottenuto sono rappresentati tutti i suffissi di S[1, i+1]. Infatti ogni suffisso non nullo di S[1, i+1] è estensione di un suffisso di S[1, i] ed il suffisso nullo è sempre rappresentato in ogni albero dei suffissi implicito.

Un'animazione della costruzione dell'albero dei suffissi per la stringa "adaadac$" con questo algoritmo astratto è la seguente:

Costruzione dell'albero dei suffissi per la stringa "adaadac$" con l'algoritmo astratto di Ukkonen

Implementazione e miglioramento dell'efficienza

Nell'algoritmo astratto, dopo che sia stato trovato il nodo (implicito o esplicito) dove termina il suffisso S[j, i] nell'albero corrente, l'estensione di S[j, i] con il carattere successivo S[i+1] richiede tempo costante in tutti e tre i casi 1, 2 e 3. Quindi, un punto chiave nell'implementazione dell'algoritmo di Ukkonen è trovare un metodo veloce per trovare i nodi in cui finiscono i suffissi S[j, i]. In una implementazione ingenua possiamo trovare il nodo in cui termina il suffisso S[j, i] in tempo $O(i-j+1)$ partendo dalla radice dell'albero. Sommando su tutti i e j si ottiene un tempo $O(i^{2})$ per calcolare $I_{i+1}$ a partire da $I_{i}$ e sommando su tutti gli i si ottiene un tempo totale $O(n^{3})$ per calcolare $I_{n+1}$.

Questo algoritmo sembra quindi folle poiché la costruzione ingenua dell'albero dei suffissi richiede tempo $O(n^{2})$. Ma con alcuni trucchi implementativi si riesce a ridurre la complessità ad $O(n)$.

Primo miglioramento: suffix link

Sia α una stringa ed x un carattere. Se in un albero dei suffissi (implicito o esplicito) esiste un nodo interno esplicito u con etichetta xα ed un nodo interno esplicito s(u) la cui etichetta è α, allora un suffix link tra u ad s(u) è semplicemente un puntatore da u ad s(u). Vedere figura precedente.

Se, durante la fase i-esima, per estendere il suffisso S[j, i], viene creato un nuovo nodo interno (non foglia) con etichetta xα (ovviamente con xα prefisso di S[j, i]) allora o nell'albero corrente esiste già un nodo interno esplicito con etichetta α oppure tale nodo verrà creato immediatamente dopo con l'estensione del suffisso successivo S[j+1, i].

Dimostrazione: un nuovo nodo interno v con etichetta S[j, i] = xα viene creato soltanto se il suffisso S[j, i] viene esteso con il caso 2 quando nell'albero corrente il cammino etichettato S[j, i] termina in un nodo interno implicito e tale cammino continua con un carattere c diverso da S[i+1]. Quindi, nell'albero corrente, il cammino di etichetta S[j+1, i] = α ha una continuazione che inizia con il carattere c. Dunque il nodo w con etichetta S[j+1, i] = α è un nodo interno (esplicito o implicito). Se w è esplicito s(v) = w. Altrimenti, se w è implicito, il cammino di etichetta S[j+1, i] = α che termina nel nodo w può continuare soltanto con il carattere c. Quindi, nel passo successivo, l'estensione del suffisso S[j+1, i] sostituisce il nodo implicito w con un nodo esplicito per cui s(v) = w.

Altri progetti

Altri progetti

• Wikimedia Commons

• Wikimedia Commons contiene immagini o altri file su albero dei suffissi

Collegamenti esterni

Implementazioni

• Pattern matching con gli alberi dei suffissi, su math.unipd.it. URL consultato il 6 febbraio 2015 (archiviato dall'url originale il 6 febbraio 2015).