string - array - suffix tree c++




Algoritmo dell'albero del suffisso di Ukkonen in inglese semplice (4)

Mi sento un po 'grosso a questo punto. Ho passato giorni a cercare di avvolgere completamente la mia testa attorno alla costruzione dell'albero del suffisso, ma poiché non ho uno sfondo matematico, molte delle spiegazioni mi sfuggono mentre iniziano a fare un uso eccessivo della simbologia matematica. Il più vicino ad una buona spiegazione che ho trovato è Fast String Searching With Suffix Trees , ma egli glossa su vari punti e alcuni aspetti dell'algoritmo rimangono poco chiari.

Una spiegazione dettagliata di questo algoritmo qui su Stack Overflow sarebbe inestimabile per molti altri oltre a me, ne sono sicuro.

Per riferimento, ecco il documento di Ukkonen sull'algoritmo: http://www.cs.helsinki.fi/u/ukkonen/SuffixT1withFigs.pdf

La mia comprensione di base, finora:

  • Ho bisogno di scorrere ogni prefisso P di una data stringa T
  • Ho bisogno di scorrere ogni suffisso S nel prefisso P e aggiungerlo all'albero
  • Per aggiungere il suffisso S all'albero, ho bisogno di scorrere ogni carattere in S, con le iterazioni consistenti nel camminare su un ramo esistente che inizia con lo stesso set di caratteri C in S e potenzialmente dividere un bordo in nodi discendenti quando io raggiungere un carattere diverso nel suffisso, OPPURE se non vi era alcun bordo corrispondente da calpestare. Quando non viene trovato alcun bordo corrispondente che cammina per C, viene creato un nuovo bordo foglia per C.

L'algoritmo di base sembra essere O (n 2 ), come indicato nella maggior parte delle spiegazioni, poiché è necessario scorrere tutti i prefissi, quindi è necessario scorrere ciascuno dei suffissi per ciascun prefisso. L'algoritmo di Ukkonen è apparentemente unico a causa della tecnica del puntatore suffisso che usa, anche se penso che sia quello che ho difficoltà a capire.

Ho anche difficoltà a capire:

  • esattamente quando e come il "punto attivo" è assegnato, utilizzato e modificato
  • cosa sta succedendo con l'aspetto della canonizzazione dell'algoritmo
  • Perché le implementazioni che ho visto devono "aggiustare" le variabili che stanno usando

Ecco il codice sorgente C # completo. Funziona non solo correttamente, ma supporta la canonizzazione automatica e rende un grafico di testo dall'aspetto più gradevole all'output. Il codice sorgente e l'output del campione sono a:

https://gist.github.com/2373868

Aggiornamento 2017-11-04

Dopo molti anni ho trovato un nuovo uso per gli alberi dei suffissi e ho implementato l'algoritmo in JavaScript . Gist è sotto. Dovrebbe essere privo di bug. npm install chalk in un file js, npm install chalk dalla stessa posizione, quindi esegui node.js per vedere un po 'di output colorato. C'è una versione ridotta nello stesso Gist, senza alcun codice di debug.

https://gist.github.com/axefrog/c347bf0f5e0723cbd09b1aaed6ec6fc6


Grazie per il tutorial ben spiegato da @jogojapan , ho implementato l'algoritmo in Python.

Un paio di problemi minori menzionati da @jogojapan si rivelano più sofisticati di quanto mi aspettassi e devono essere trattati con molta attenzione. Mi è costato diversi giorni per avere la mia implementazione abbastanza robusta (suppongo). I problemi e le soluzioni sono elencati di seguito:

  1. End with Remainder > 0 Risulta che questa situazione può verificarsi anche durante la fase di unfolding , non solo alla fine dell'intero algoritmo. Quando ciò accade, possiamo lasciare il resto, actnode, actedge e actlength immutati , terminare il passaggio di unfolding corrente e iniziare un altro passo continuando a piegare o spiegare a seconda se il prossimo char nella stringa originale si trova sul percorso corrente o non.

  2. Salta i nodi: quando seguiamo un collegamento suffisso, aggiorna il punto attivo e poi scopri che il suo componente active_length non funziona bene con il nuovo active_node. Dobbiamo andare avanti nel posto giusto per dividere o inserire una foglia. Questo processo potrebbe non essere così semplice perché durante lo spostamento l'actlength e l'actedge continuano a cambiare fino in fondo, quando si deve tornare al nodo radice , il recto e l' actlength potrebbero essere sbagliati a causa di quei movimenti. Abbiamo bisogno di variabili aggiuntive per mantenere tali informazioni.

Gli altri due problemi sono stati in qualche modo indicati da @managonov

  1. Dividi potrebbe degenerare Quando provi a dividere un bordo, a volte troverai che l'operazione di divisione è proprio su un nodo. In questo caso abbiamo solo bisogno di aggiungere una nuova foglia a quel nodo, prendila come operazione standard di divisione del bordo, il che significa che i collegamenti dei suffissi, se ce ne sono, dovrebbero essere mantenuti in modo corrispondente.

  2. Collegamenti a suffisso nascosto C'è un altro caso speciale che è dovuto al problema 1 e al problema 2 . A volte abbiamo bisogno di saltare su diversi nodi al punto giusto per la divisione, potremmo superare il punto giusto se ci muoviamo confrontando la stringa resto e le etichette del percorso. In tal caso il link del suffisso verrà ignorato involontariamente, se ce ne dovrebbe essere. Questo potrebbe essere evitato ricordando il punto giusto quando vai avanti. Il suffisso link dovrebbe essere mantenuto se il nodo split esiste già, o anche il problema 1 si verifica durante una fase di unfolding.

Infine, la mia implementazione in Python è la seguente:

Suggerimenti: include una funzione di stampa dell'albero naif nel codice sopra, che è molto importante durante il debug . Mi ha risparmiato un sacco di tempo ed è comodo per individuare casi speciali.


Ho cercato di implementare l'albero del suffisso con l'approccio dato nella risposta di jogojapan, ma per alcuni casi non ha funzionato a causa del testo usato per le regole. Inoltre, ho menzionato che nessuno è riuscito a implementare un albero di suffisso assolutamente corretto utilizzando questo approccio. Di seguito scriverò una "panoramica" della risposta di jogojapan con alcune modifiche alle regole. Descriverò anche il caso in cui dimentichiamo di creare collegamenti suffisso importanti .

Altre variabili utilizzate

  1. punto attivo : una tripla (active_node; active_edge; active_length), che mostra da dove dobbiamo iniziare a inserire un nuovo suffisso.
  2. resto - mostra il numero di suffissi che dobbiamo aggiungere esplicitamente . Ad esempio, se la nostra parola è "abcaabca" e resto = 3, significa che dobbiamo elaborare 3 ultimi suffissi: bca , ca e a .

Usiamo un concetto di nodo interno : tutti i nodi, eccetto la radice e le foglie sono nodi interni .

Osservazione 1

Quando il suffisso finale che dobbiamo inserire è già presente nell'albero, l'albero stesso non viene affatto modificato (aggiorniamo solo il active point e il remainder ).

Osservazione 2

Se ad un certo punto active_length è maggiore o uguale alla lunghezza del bordo corrente ( edge_length ), spostiamo il nostro active point verso il basso finché edge_length è strettamente maggiore di active_length .

Ora, ridefiniamo le regole:

Regola 1

Se dopo un inserimento dal nodo attivo = root , la lunghezza attiva è maggiore di 0, quindi:

  1. il nodo attivo non è cambiato
  2. la lunghezza attiva è decrementata
  3. il bordo attivo è spostato a destra (al primo carattere del suffisso successivo che dobbiamo inserire)

Regola 2

Se creiamo un nuovo nodo interno OPPURE facciamo un inseritore da un nodo interno e questo non è il primo nodo interno SUCH al passo corrente, allora colleghiamo il precedente nodo SUCH con QUESTO attraverso un collegamento suffisso .

Questa definizione della Rule 2 è diversa da jogojapan ', in quanto qui prendiamo in considerazione non solo i nodi interni appena creati , ma anche i nodi interni, dai quali facciamo un inserimento.

Regola 3

Dopo un inserimento dal nodo attivo che non è il nodo radice , dobbiamo seguire il link suffisso e impostare il nodo attivo sul nodo a cui punta. Se non esiste un collegamento suffisso, impostare il nodo attivo sul nodo radice . In entrambi i casi, il fronte attivo e la lunghezza attiva rimangono invariati.

In questa definizione della Rule 3 consideriamo anche gli inserti dei nodi foglia (non solo i nodi split).

E infine, l'osservazione 3:

Quando il simbolo che vogliamo aggiungere all'albero è già sul bordo, noi, secondo l' Observation 1 , aggiorniamo solo il active point e il remainder , lasciando l'albero invariato. MA se c'è un nodo interno contrassegnato come bisessante , è necessario connettere quel nodo con il nostro active node corrente tramite un collegamento suffisso.

Diamo un'occhiata all'esempio di un albero di suffisso per cdddcdc se aggiungiamo un suffisso in questo caso e se non lo facciamo:

  1. Se NON connettiamo i nodi tramite un suffisso link:

    • prima di aggiungere l'ultima lettera c :

    • dopo aver aggiunto l'ultima lettera c :

  2. Se colleghiamo i nodi tramite un suffisso link:

    • prima di aggiungere l'ultima lettera c :

    • dopo aver aggiunto l'ultima lettera c :

Sembra che non ci siano differenze significative: nel secondo caso ci sono altri due link suffix. Ma questi collegamenti suffisso sono corretti , e uno di loro - dal nodo blu a quello rosso - è molto importante per il nostro approccio con il punto attivo . Il problema è che se non inseriamo qui un link suffisso, più tardi, quando aggiungiamo alcune nuove lettere all'albero, potremmo omettere di aggiungere alcuni nodi all'albero a causa della Rule 3 , perché, secondo esso, se c'è nessun link suffisso, quindi dobbiamo inserire il active_node nella root.

Quando stavamo aggiungendo l'ultima lettera all'albero, il nodo rosso esisteva già prima di creare un inserto dal nodo blu (il bordo etichettato 'c' ). Dato che c'era un inserto dal nodo blu, lo contrassegniamo come se avessimo bisogno di un suffisso link . Quindi, basandosi sull'approccio a punto attivo , il active node stato impostato sul nodo rosso. Ma non facciamo un inserto dal nodo rosso, poiché la lettera "c" è già sul bordo. Significa che il nodo blu deve essere lasciato senza un suffisso link? No, dobbiamo collegare il nodo blu con quello rosso attraverso un link suffisso. Perché è corretto? Perché l'approccio punto attivo garantisce che arriviamo al posto giusto, cioè al prossimo posto in cui dobbiamo elaborare un inserto di un suffisso più corto .

Infine, ecco le mie implementazioni dell'albero del suffisso:

  1. Java
  2. C++

Spero che questa "panoramica" combinata con la risposta dettagliata di jogojapan aiuterà qualcuno a implementare il proprio Suffix Tree.


Quello che segue è un tentativo di descrivere l'algoritmo di Ukkonen mostrando in primo luogo cosa fa quando la stringa è semplice (cioè non contiene alcun carattere ripetuto), e quindi estendendolo all'algoritmo completo.

In primo luogo, alcune dichiarazioni preliminari.

  1. Quello che stiamo costruendo, è fondamentalmente come un trie di ricerca. Quindi c'è un nodo radice, i bordi che escono da esso portano a nuovi nodi, e altri bordi che escono da questi, e così via

  2. Ma : a differenza di un trie di ricerca, le etichette sui bordi non sono caratteri singoli. Invece, ogni spigolo è etichettato usando una coppia di numeri interi [from,to] . Questi sono puntatori nel testo. In questo senso, ogni spigolo porta un'etichetta di stringa di lunghezza arbitraria, ma prende solo uno spazio O (1) (due puntatori).

Criterio basilare

Vorrei prima dimostrare come creare l'albero del suffisso di una stringa particolarmente semplice, una stringa senza caratteri ripetuti:

abc

L'algoritmo funziona a passi, da sinistra a destra . C'è un passo per ogni carattere della stringa . Ogni passaggio potrebbe coinvolgere più di una singola operazione, ma vedremo (vedere le osservazioni finali alla fine) che il numero totale di operazioni è O (n).

Quindi, partiamo da sinistra , e prima inseriamo solo il singolo carattere a creando un bordo dal nodo radice (a sinistra) a una foglia e etichettandolo come [0,#] , il che significa che il bordo rappresenta la sottostringa iniziando dalla posizione 0 e finendo alla fine attuale . Io uso il simbolo # per indicare la fine corrente , che è in posizione 1 (subito dopo a ).

Quindi abbiamo un albero iniziale, che assomiglia a questo:

E ciò significa:

Ora passiamo alla posizione 2 (subito dopo b ). Il nostro obiettivo in ogni fase è inserire tutti i suffissi fino alla posizione corrente . Lo facciamo da

  • espandendo l'esistente a -edge a ab
  • inserire un nuovo bordo per b

Nella nostra rappresentazione questo sembra

E ciò che significa è:

Osserviamo due cose:

  • La rappresentazione del bordo per ab è la stessa di una volta nell'albero iniziale: [0,#] . Il suo significato è cambiato automaticamente perché abbiamo aggiornato la posizione corrente # da 1 a 2.
  • Ogni spigolo consuma spazio O (1), poiché consiste solo di due puntatori nel testo, indipendentemente dal numero di caratteri che rappresenta.

Quindi incrementiamo nuovamente la posizione e aggiorniamo l'albero aggiungendo un c a ogni bordo esistente e inserendo un nuovo bordo per il nuovo suffisso c .

Nella nostra rappresentazione questo sembra

E ciò che significa è:

Osserviamo:

  • L'albero è l'albero del suffisso corretto fino alla posizione corrente dopo ogni passaggio
  • Ci sono tanti passaggi quanti sono i caratteri nel testo
  • La quantità di lavoro in ogni fase è O (1), poiché tutti i bordi esistenti vengono aggiornati automaticamente incrementando # , e l'inserimento di un nuovo bordo per il carattere finale può essere eseguito in O (1). Quindi per una stringa di lunghezza n è richiesto solo O (n).

Prima estensione: ripetizioni semplici

Ovviamente funziona così bene solo perché la nostra stringa non contiene ripetizioni. Ora guardiamo una stringa più realistica:

abcabxabcd

Inizia con abc come nell'esempio precedente, quindi ab viene ripetuto e seguito da x , e quindi abc viene ripetuto seguito da d .

Passaggi da 1 a 3: Dopo i primi 3 passi abbiamo l'albero dell'esempio precedente:

Passaggio 4: spostiamo # in posizione 4. Questo aggiorna implicitamente tutti i bordi esistenti a questo:

e abbiamo bisogno di inserire il suffisso finale del passo corrente, a , alla radice.

Prima di farlo, introduciamo altre due variabili (oltre a # ), che ovviamente sono state sempre presenti ma non le abbiamo finora utilizzate:

  • Il punto attivo , che è una tripla (active_node,active_edge,active_length)
  • Il remainder , che è un numero intero che indica quanti nuovi suffissi dobbiamo inserire

Il significato esatto di questi due diventerà presto chiaro, ma per ora diciamo semplicemente:

  • Nell'esempio abc semplice, il punto attivo era sempre (root,'\0x',0) , cioè active_node era il nodo root, active_edge stato specificato come carattere null '\0x' e active_length era zero. L'effetto di questo è stato che il nuovo edge che abbiamo inserito in ogni fase è stato inserito nel nodo radice come un bordo appena creato. Vedremo presto perché è necessaria una tripla per rappresentare questa informazione.
  • Il remainder è sempre stato impostato su 1 all'inizio di ogni passaggio. Il significato di questo era che il numero di suffissi che dovevamo inserire attivamente alla fine di ogni passo era 1 (sempre solo il carattere finale).

Ora questo cambierà. Quando inseriamo il carattere finale corrente a alla radice, notiamo che esiste già un bordo in uscita che inizia con a , in particolare: abca . Ecco cosa facciamo in questo caso:

  • Non inseriamo un nuovo fronte [4,#] nel nodo radice. Invece notiamo semplicemente che il suffisso a è già nel nostro albero. Finisce nel bel mezzo di un margine più lungo, ma non ne siamo infastiditi. Lasciamo le cose come sono.
  • Impostiamo il punto attivo su (root,'a',1) . Ciò significa che il punto attivo è ora nel bel mezzo del bordo in uscita del nodo radice che inizia con, in particolare, dopo la posizione 1 su quel bordo. Notiamo che il bordo è specificato semplicemente dal suo primo carattere a . Questo è sufficiente perché può esserci un solo margine che inizia con un particolare carattere (conferma che questo è vero dopo aver letto l'intera descrizione).
  • Aumentiamo anche il remainder , quindi all'inizio del prossimo passo sarà 2.

Osservazione: quando il suffisso finale che dobbiamo inserire è già presente nell'albero , l'albero stesso non viene affatto modificato (aggiorniamo solo il punto attivo e il remainder ). L'albero non è più una rappresentazione accurata dell'albero del suffisso fino alla posizione corrente , ma contiene tutti i suffissi (poiché il suffisso finale a è contenuto implicitamente ). Quindi, a parte l'aggiornamento delle variabili (che sono tutte di lunghezza fissa, quindi questo è O (1)), non c'è stato alcun lavoro in questa fase.

Passaggio 5: aggiorniamo la posizione corrente da # a 5. Questo aggiorna automaticamente l'albero a questo:

E poiché remainder è 2 , dobbiamo inserire due suffissi finali della posizione corrente: ab e b . Questo è fondamentalmente perché:

  • Il suffisso del passaggio precedente non è mai stato inserito correttamente. Così è rimasto , e dal momento che abbiamo progredito un passo, ora è cresciuto da a a ab .
  • E abbiamo bisogno di inserire il nuovo bordo finale b .

In pratica ciò significa che andiamo al punto attivo (che indica dietro l' a su quello che ora è il bordo abcab ) e inseriamo il carattere finale corrente b . Ma: Ancora una volta, risulta che b è già presente sullo stesso bordo.

Quindi, ancora una volta, non cambiamo l'albero. Semplicemente:

  • Aggiorna il punto attivo a (root,'a',2) (stesso nodo e bordo come prima, ma ora puntiamo a dietro il b )
  • Incrementa il remainder a 3 perché non abbiamo ancora inserito correttamente il bordo finale del passaggio precedente e non inseriamo neanche il bordo finale corrente.

Per essere chiari: abbiamo dovuto inserire ab e b nel passaggio corrente, ma poiché ab era già stato trovato, abbiamo aggiornato il punto attivo e non abbiamo nemmeno tentato di inserire b . Perché? Perché se ab è nell'albero, anche ogni suffisso di esso (incluso b ) deve essere nell'albero. Forse solo implicitamente , ma deve esserci, a causa del modo in cui abbiamo costruito l'albero finora.

Procediamo al passaggio 6 incrementando # . L'albero viene automaticamente aggiornato a:

Poiché il remainder è 3 , dobbiamo inserire abx , bx e x . Il punto attivo ci dice dove termina ab , quindi abbiamo solo bisogno di saltare lì e inserire la x . Infatti, x non c'è ancora, quindi abbiamo diviso il bordo abcabx e inserito un nodo interno:

Le rappresentazioni dei bordi sono ancora puntatori nel testo, quindi la suddivisione e l'inserimento di un nodo interno possono essere eseguiti in tempo O (1).

Quindi ci siamo occupati di abx e decrement remainder a 2. Ora dobbiamo inserire il prossimo suffisso restante, bx . Ma prima di farlo dobbiamo aggiornare il punto attivo. La regola per questo, dopo aver diviso e inserito un bordo, sarà chiamata di seguito la Regola 1 , e si applica ogni volta che active_node è root (impareremo la regola 3 per altri casi più avanti). Ecco la regola 1:

Dopo un inserimento da root,

  • active_node rimane root
  • active_edge è impostato sul primo carattere del nuovo suffisso che dobbiamo inserire, cioè b
  • active_length è ridotto di 1

Quindi, il nuovo triplo punto attivo (root,'b',1) indica che l'inserto successivo deve essere fatto sul bordo di bcabx , dietro 1 carattere, cioè dietro b . Possiamo identificare il punto di inserimento nel tempo O (1) e verificare se x è già presente o meno. Se fosse presente, finiremmo il passo attuale e lasceremo tutto com'è. Ma x non è presente, quindi lo inseriamo dividendo il bordo:

Di nuovo, questo ha richiesto O (1) tempo e aggiorniamo il remainder su 1 e il punto attivo su (root,'x',0) come afferma la regola 1.

Ma c'è un'altra cosa che dobbiamo fare. Chiameremo questa regola 2:

Se dividiamo un bordo e inseriamo un nuovo nodo, e se questo non è il primo nodo creato durante il passaggio corrente, colleghiamo il nodo inserito in precedenza e il nuovo nodo tramite un puntatore speciale, un collegamento suffisso . Vedremo in seguito perché è utile. Ecco cosa otteniamo, il collegamento del suffisso è rappresentato come un bordo tratteggiato:

Dobbiamo ancora inserire il suffisso finale del passaggio corrente, x . Poiché il componente active_length del nodo attivo è sceso a 0, l'inserto finale viene eseguito direttamente nella radice. Poiché non esiste un fronte in uscita nel nodo radice che inizia con x , inseriamo un nuovo bordo:

Come possiamo vedere, nel passaggio corrente sono stati fatti tutti gli inserti rimanenti.

Procediamo al passaggio 7 impostando # = 7, che aggiunge automaticamente il carattere successivo, a , a tutti i bordi della foglia, come sempre. Quindi proviamo a inserire il nuovo carattere finale nel punto attivo (la radice) e troviamo che è già lì. Quindi terminiamo il passaggio corrente senza inserire nulla e aggiorniamo il punto attivo su (root,'a',1) .

Nel passo 8 , # = 8, aggiungiamo b , e come visto prima, questo significa solo che aggiorniamo il punto attivo a (root,'a',2) e incrementiamo il remainder senza fare altro, perché b è già presente. Tuttavia, notiamo (in O (1) volta) che il punto attivo è ora alla fine di un bordo. Riflettiamo questo impostandolo su (node1,'\0x',0) . Qui, io uso node1 per riferirsi al nodo interno che termina con il bordo ab .

Quindi, al passo # = 9 , dobbiamo inserire 'c' e questo ci aiuterà a capire il trucco finale:

Seconda estensione: utilizzo dei collegamenti suffisso

Come sempre, l'aggiornamento # aggiunge automaticamente c ai bordi della foglia e andiamo al punto attivo per vedere se possiamo inserire "c". Risulta che "c" esiste già a quel bordo, quindi impostiamo il punto attivo su (node1,'c',1) , incrementiamo il remainder e non facciamo nient'altro.

Ora nel passo # = 10 , il remainder is 4 , e quindi dobbiamo prima inserire abcd (che rimane da 3 passi fa) inserendo d nel punto attivo.

Il tentativo di inserire d nel punto attivo causa una divisione del bordo nel tempo O (1):

Il active_node , da cui è stata avviata la divisione, è contrassegnato in rosso sopra. Ecco la regola finale, Regola 3:

Dopo aver diviso un edge da un active_node che non è il nodo root, seguiamo il link suffix che esce da quel nodo, se ce n'è uno, e reimpostiamo il active_node nel nodo a cui punta. Se non esiste alcun suffisso link, impostiamo il active_node nella root. active_edge e active_length rimangono invariati.

Quindi il punto attivo è ora (node2,'c',1) , e node2 è contrassegnato in rosso di seguito:

Poiché l'inserimento di abcd è completo, decrementiamo il remainder a 3 e consideriamo il prossimo suffisso restante del passo corrente, bcd . La Regola 3 ha impostato il punto attivo solo sul nodo e sul bordo destro, in modo che l'inserimento di bcd possa essere fatto semplicemente inserendo il suo carattere finale d nel punto attivo.

In questo modo si crea un altro spacco laterale e, a causa della regola 2 , dobbiamo creare un collegamento suffisso dal nodo precedentemente inserito a quello nuovo:

Osserviamo: i collegamenti suffissi ci permettono di resettare il punto attivo in modo che possiamo fare il prossimo inserto rimanente con O (1) sforzo. Osserva il grafico qui sopra per confermare che effettivamente il nodo all'etichetta ab è collegato al nodo in b (il suo suffisso), e il nodo in abc è collegato a bc .

Il passo attuale non è ancora finito. remainder è ora 2, e dobbiamo seguire la regola 3 per resettare nuovamente il punto attivo. Poiché l' active_node corrente (rosso sopra) non ha alcun suffisso link, abbiamo reimpostato su root. Il punto attivo è ora (root,'c',1) .

Quindi l'inserto successivo si verifica in corrispondenza del bordo in uscita del nodo radice la cui etichetta inizia con c : cabxabcd , dietro il primo carattere, cioè dietro c . Ciò causa un'altra divisione:

E poiché ciò comporta la creazione di un nuovo nodo interno, seguiamo la regola 2 e impostiamo un nuovo suffisso link dal nodo interno creato in precedenza:

(Sto usando Graphviz Dot per questi piccoli grafici.Il nuovo suffisso link ha causato il punto per riorganizzare i bordi esistenti, quindi controlla attentamente per confermare che l'unica cosa che è stata inserita sopra è un nuovo suffisso link.)

Con questo, il remainder può essere impostato su 1 e poiché active_node è root, usiamo la regola 1 per aggiornare il punto attivo su (root,'d',0) . Ciò significa che l'ultimo inserto del passaggio corrente è inserire una sola d alla radice:

Questo è stato il passo finale e abbiamo finito. Ci sono un numero di osservazioni finali , tuttavia:

  • In ogni passo spostiamo # avanti di 1 posizione. Questo aggiorna automaticamente tutti i nodi foglia in tempo O (1).

  • Ma non tratta con a) eventuali suffissi rimasti dai precedenti passaggi, e b) con l'ultimo carattere del passo corrente.

  • remainder ci dice quanti inserti aggiuntivi dobbiamo fare. Questi inserti corrispondono uno-a-uno ai suffissi finali della stringa che termina con la posizione corrente # . Consideriamo uno dopo l'altro e facciamo l'inserto. Importante: ogni inserimento viene eseguito in tempo O (1) poiché il punto attivo ci dice esattamente dove andare, e dobbiamo aggiungere solo un singolo carattere nel punto attivo. Perché? Perché gli altri personaggi sono contenuti implicitamente (altrimenti il ​​punto attivo non sarebbe dove si trova).

  • Dopo ciascun inserto, decrementiamo il remainder e seguiamo il link del suffisso se ce n'è uno. Se no, andiamo alla radice (regola 3). Se siamo già root, modifichiamo il punto attivo usando la regola 1. In ogni caso, richiede solo O (1) tempo.

  • Se, durante uno di questi inserimenti, troviamo che il carattere che vogliamo inserire è già lì, non facciamo nulla e terminiamo il passo corrente, anche se remainder > 0. Il motivo è che tutti gli inserti che rimangono saranno suffissi di quello che abbiamo appena provato a fare. Quindi sono tutti impliciti nell'albero attuale. Il fatto che il remainder > 0 assicuri che in seguito gestiremo i suffissi rimanenti.

  • Cosa succede se alla fine dell'algoritmo remainder > 0? Questo sarà il caso ogni volta che la fine del testo è una sottostringa che si è verificato da qualche parte prima. In tal caso dobbiamo aggiungere un carattere in più alla fine della stringa che non si è mai verificato prima. In letteratura, solitamente il simbolo del dollaro $ viene usato come simbolo per questo. Perché importa? -> Se in seguito utilizziamo l'albero del suffisso completato per cercare i suffissi, dobbiamo accettare le corrispondenze solo se terminano su una foglia . Altrimenti otterremmo molte corrispondenze spurie, perché ci sono molte stringhe implicitamente contenute nell'albero che non sono veri suffissi della stringa principale. Forzare il remainder a 0 alla fine è essenzialmente un modo per assicurarsi che tutti i suffissi finiscano in un nodo foglia. Tuttavia, se vogliamo utilizzare l'albero per cercare sottostringhe generali , non solo suffissi della stringa principale, questo passaggio finale non è in effetti richiesto, come suggerito dal commento dell'OP di seguito.

  • Quindi qual è la complessità dell'intero algoritmo? Se il testo è di lunghezza n caratteri, ci sono ovviamente n passi (o n + 1 se aggiungiamo il simbolo del dollaro). In ogni passo non facciamo nulla (oltre all'aggiornamento delle variabili), o facciamo inserti remainder , ognuno dei quali richiede O (1) tempo. Dato che il remainder indica quante volte non abbiamo fatto nulla nei passaggi precedenti, ed è decrementato per ogni inserto che facciamo ora, il numero totale di volte che facciamo qualcosa è esattamente n (o n + 1). Quindi, la complessità totale è O (n).

  • Tuttavia, c'è una piccola cosa che non ho spiegato correttamente: può succedere che seguiamo un link suffisso, aggiorniamo il punto attivo e poi scopriamo che il suo componente active_length non funziona bene con il nuovo active_node . Ad esempio, considera una situazione come questa:

(Le linee tratteggiate indicano il resto dell'albero. La linea tratteggiata è un collegamento suffisso).

Ora lascia che il punto attivo sia (red,'d',3) , quindi punta al punto dietro la f sul bordo del defg . Ora supponiamo di aver apportato gli aggiornamenti necessari e ora seguiamo il suffisso per aggiornare il punto attivo in base alla regola 3. Il nuovo punto attivo è (green,'d',3) . Tuttavia, il d -edge che esce dal nodo verde è de , quindi ha solo 2 caratteri. Per trovare il punto attivo corretto, dobbiamo ovviamente seguire quel bordo sul nodo blu e resettare a (blue,'f',1) .

In un caso particolarmente grave, active_length potrebbe essere grande quanto il remainder , che può essere grande come n. E potrebbe benissimo accadere che per trovare il punto attivo corretto, non dobbiamo solo saltare sopra un nodo interno, ma forse molti, fino a n nel peggiore dei casi. Ciò significa che l'algoritmo ha una complessità O (n 2 ) nascosta, perché in ogni fase il remainder è generalmente O (n), e le post-rettifiche al nodo attivo dopo aver seguito un suffisso potrebbero essere anche O (n)?

No. La ragione è che se davvero dovessimo aggiustare il punto attivo (ad esempio da verde a blu come sopra), questo ci porta in un nuovo nodo che ha il suo suffisso e la active_length sarà ridotta. Mentre seguiamo la catena di collegamenti dei suffissi che facciamo gli inserti rimanenti, la active_length può solo diminuire e il numero di regolazioni del punto attivo che possiamo fare sulla strada non può essere maggiore di active_length in un dato momento. Poiché active_length non può mai essere più grande del remainder , e il remainder è O (n) non solo in ogni singolo passo, ma la somma totale degli incrementi mai fatti per il remainder nel corso dell'intero processo è anche O (n), il numero di le regolazioni del punto attivo sono anche delimitate da O (n).


@jogojapan hai portato splendide spiegazioni e visualizzazioni. Ma come @makagonov ha menzionato che mancano alcune regole riguardanti l'impostazione dei collegamenti dei suffissi. È visibile in modo carino quando si procede passo dopo passo su http://brenden.github.io/ukkonen-animation/ attraverso la parola 'aabaaabb'. Quando si passa dal punto 10 al passaggio 11, non esiste alcun collegamento suffisso dal nodo 5 al nodo 2, ma il punto attivo si sposta improvvisamente lì.

@ Makagonov da quando vivo nel mondo di Java ho anche provato a seguire la tua implementazione per comprendere il flusso di lavoro ST building, ma è stato difficile per me a causa di:

  • combinando i bordi con i nodi
  • usando indici puntuali invece di riferimenti
  • rompe le dichiarazioni;
  • continuare le dichiarazioni;

Così ho finito con una tale implementazione in Java che spero rispecchi tutti i passaggi in modo più chiaro e ridurrà il tempo di apprendimento per altre persone Java:

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class ST {

  public class Node {
    private final int id;
    private final Map<Character, Edge> edges;
    private Node slink;

    public Node(final int id) {
        this.id = id;
        this.edges = new HashMap<>();
    }

    public void setSlink(final Node slink) {
        this.slink = slink;
    }

    public Map<Character, Edge> getEdges() {
        return this.edges;
    }

    public Node getSlink() {
        return this.slink;
    }

    public String toString(final String word) {
        return new StringBuilder()
                .append("{")
                .append("\"id\"")
                .append(":")
                .append(this.id)
                .append(",")
                .append("\"slink\"")
                .append(":")
                .append(this.slink != null ? this.slink.id : null)
                .append(",")
                .append("\"edges\"")
                .append(":")
                .append(edgesToString(word))
                .append("}")
                .toString();
    }

    private StringBuilder edgesToString(final String word) {
        final StringBuilder edgesStringBuilder = new StringBuilder();
        edgesStringBuilder.append("{");
        for(final Map.Entry<Character, Edge> entry : this.edges.entrySet()) {
            edgesStringBuilder.append("\"")
                    .append(entry.getKey())
                    .append("\"")
                    .append(":")
                    .append(entry.getValue().toString(word))
                    .append(",");
        }
        if(!this.edges.isEmpty()) {
            edgesStringBuilder.deleteCharAt(edgesStringBuilder.length() - 1);
        }
        edgesStringBuilder.append("}");
        return edgesStringBuilder;
    }

    public boolean contains(final String word, final String suffix) {
        return !suffix.isEmpty()
                && this.edges.containsKey(suffix.charAt(0))
                && this.edges.get(suffix.charAt(0)).contains(word, suffix);
    }
  }

  public class Edge {
    private final int from;
    private final int to;
    private final Node next;

    public Edge(final int from, final int to, final Node next) {
        this.from = from;
        this.to = to;
        this.next = next;
    }

    public int getFrom() {
        return this.from;
    }

    public int getTo() {
        return this.to;
    }

    public Node getNext() {
        return this.next;
    }

    public int getLength() {
        return this.to - this.from;
    }

    public String toString(final String word) {
        return new StringBuilder()
                .append("{")
                .append("\"content\"")
                .append(":")
                .append("\"")
                .append(word.substring(this.from, this.to))
                .append("\"")
                .append(",")
                .append("\"next\"")
                .append(":")
                .append(this.next != null ? this.next.toString(word) : null)
                .append("}")
                .toString();
    }

    public boolean contains(final String word, final String suffix) {
        if(this.next == null) {
            return word.substring(this.from, this.to).equals(suffix);
        }
        return suffix.startsWith(word.substring(this.from,
                this.to)) && this.next.contains(word, suffix.substring(this.to - this.from));
    }
  }

  public class ActivePoint {
    private final Node activeNode;
    private final Character activeEdgeFirstCharacter;
    private final int activeLength;

    public ActivePoint(final Node activeNode,
                       final Character activeEdgeFirstCharacter,
                       final int activeLength) {
        this.activeNode = activeNode;
        this.activeEdgeFirstCharacter = activeEdgeFirstCharacter;
        this.activeLength = activeLength;
    }

    private Edge getActiveEdge() {
        return this.activeNode.getEdges().get(this.activeEdgeFirstCharacter);
    }

    public boolean pointsToActiveNode() {
        return this.activeLength == 0;
    }

    public boolean activeNodeIs(final Node node) {
        return this.activeNode == node;
    }

    public boolean activeNodeHasEdgeStartingWith(final char character) {
        return this.activeNode.getEdges().containsKey(character);
    }

    public boolean activeNodeHasSlink() {
        return this.activeNode.getSlink() != null;
    }

    public boolean pointsToOnActiveEdge(final String word, final char character) {
        return word.charAt(this.getActiveEdge().getFrom() + this.activeLength) == character;
    }

    public boolean pointsToTheEndOfActiveEdge() {
        return this.getActiveEdge().getLength() == this.activeLength;
    }

    public boolean pointsAfterTheEndOfActiveEdge() {
        return this.getActiveEdge().getLength() < this.activeLength;
    }

    public ActivePoint moveToEdgeStartingWithAndByOne(final char character) {
        return new ActivePoint(this.activeNode, character, 1);
    }

    public ActivePoint moveToNextNodeOfActiveEdge() {
        return new ActivePoint(this.getActiveEdge().getNext(), null, 0);
    }

    public ActivePoint moveToSlink() {
        return new ActivePoint(this.activeNode.getSlink(),
                this.activeEdgeFirstCharacter,
                this.activeLength);
    }

    public ActivePoint moveTo(final Node node) {
        return new ActivePoint(node, this.activeEdgeFirstCharacter, this.activeLength);
    }

    public ActivePoint moveByOneCharacter() {
        return new ActivePoint(this.activeNode,
                this.activeEdgeFirstCharacter,
                this.activeLength + 1);
    }

    public ActivePoint moveToEdgeStartingWithAndByActiveLengthMinusOne(final Node node,
                                                                       final char character) {
        return new ActivePoint(node, character, this.activeLength - 1);
    }

    public ActivePoint moveToNextNodeOfActiveEdge(final String word, final int index) {
        return new ActivePoint(this.getActiveEdge().getNext(),
                word.charAt(index - this.activeLength + this.getActiveEdge().getLength()),
                this.activeLength - this.getActiveEdge().getLength());
    }

    public void addEdgeToActiveNode(final char character, final Edge edge) {
        this.activeNode.getEdges().put(character, edge);
    }

    public void splitActiveEdge(final String word,
                                final Node nodeToAdd,
                                final int index,
                                final char character) {
        final Edge activeEdgeToSplit = this.getActiveEdge();
        final Edge splittedEdge = new Edge(activeEdgeToSplit.getFrom(),
                activeEdgeToSplit.getFrom() + this.activeLength,
                nodeToAdd);
        nodeToAdd.getEdges().put(word.charAt(activeEdgeToSplit.getFrom() + this.activeLength),
                new Edge(activeEdgeToSplit.getFrom() + this.activeLength,
                        activeEdgeToSplit.getTo(),
                        activeEdgeToSplit.getNext()));
        nodeToAdd.getEdges().put(character, new Edge(index, word.length(), null));
        this.activeNode.getEdges().put(this.activeEdgeFirstCharacter, splittedEdge);
    }

    public Node setSlinkTo(final Node previouslyAddedNodeOrAddedEdgeNode,
                           final Node node) {
        if(previouslyAddedNodeOrAddedEdgeNode != null) {
            previouslyAddedNodeOrAddedEdgeNode.setSlink(node);
        }
        return node;
    }

    public Node setSlinkToActiveNode(final Node previouslyAddedNodeOrAddedEdgeNode) {
        return setSlinkTo(previouslyAddedNodeOrAddedEdgeNode, this.activeNode);
    }
  }

  private static int idGenerator;

  private final String word;
  private final Node root;
  private ActivePoint activePoint;
  private int remainder;

  public ST(final String word) {
    this.word = word;
    this.root = new Node(idGenerator++);
    this.activePoint = new ActivePoint(this.root, null, 0);
    this.remainder = 0;
    build();
  }

  private void build() {
    for(int i = 0; i < this.word.length(); i++) {
        add(i, this.word.charAt(i));
    }
  }

  private void add(final int index, final char character) {
    this.remainder++;
    boolean characterFoundInTheTree = false;
    Node previouslyAddedNodeOrAddedEdgeNode = null;
    while(!characterFoundInTheTree && this.remainder > 0) {
        if(this.activePoint.pointsToActiveNode()) {
            if(this.activePoint.activeNodeHasEdgeStartingWith(character)) {
                activeNodeHasEdgeStartingWithCharacter(character, previouslyAddedNodeOrAddedEdgeNode);
                characterFoundInTheTree = true;
            }
            else {
                if(this.activePoint.activeNodeIs(this.root)) {
                    rootNodeHasNotEdgeStartingWithCharacter(index, character);
                }
                else {
                    previouslyAddedNodeOrAddedEdgeNode = internalNodeHasNotEdgeStartingWithCharacter(index,
                            character, previouslyAddedNodeOrAddedEdgeNode);
                }
            }
        }
        else {
            if(this.activePoint.pointsToOnActiveEdge(this.word, character)) {
                activeEdgeHasCharacter();
                characterFoundInTheTree = true;
            }
            else {
                if(this.activePoint.activeNodeIs(this.root)) {
                    previouslyAddedNodeOrAddedEdgeNode = edgeFromRootNodeHasNotCharacter(index,
                            character,
                            previouslyAddedNodeOrAddedEdgeNode);
                }
                else {
                    previouslyAddedNodeOrAddedEdgeNode = edgeFromInternalNodeHasNotCharacter(index,
                            character,
                            previouslyAddedNodeOrAddedEdgeNode);
                }
            }
        }
    }
  }

  private void activeNodeHasEdgeStartingWithCharacter(final char character,
                                                    final Node previouslyAddedNodeOrAddedEdgeNode) {
    this.activePoint.setSlinkToActiveNode(previouslyAddedNodeOrAddedEdgeNode);
    this.activePoint = this.activePoint.moveToEdgeStartingWithAndByOne(character);
    if(this.activePoint.pointsToTheEndOfActiveEdge()) {
        this.activePoint = this.activePoint.moveToNextNodeOfActiveEdge();
    }
  }

  private void rootNodeHasNotEdgeStartingWithCharacter(final int index, final char character) {
    this.activePoint.addEdgeToActiveNode(character, new Edge(index, this.word.length(), null));
    this.activePoint = this.activePoint.moveTo(this.root);
    this.remainder--;
    assert this.remainder == 0;
  }

  private Node internalNodeHasNotEdgeStartingWithCharacter(final int index,
                                                         final char character,
                                                         Node previouslyAddedNodeOrAddedEdgeNode) {
    this.activePoint.addEdgeToActiveNode(character, new Edge(index, this.word.length(), null));
    previouslyAddedNodeOrAddedEdgeNode = this.activePoint.setSlinkToActiveNode(previouslyAddedNodeOrAddedEdgeNode);
    if(this.activePoint.activeNodeHasSlink()) {
        this.activePoint = this.activePoint.moveToSlink();
    }
    else {
        this.activePoint = this.activePoint.moveTo(this.root);
    }
    this.remainder--;
    return previouslyAddedNodeOrAddedEdgeNode;
  }

  private void activeEdgeHasCharacter() {
    this.activePoint = this.activePoint.moveByOneCharacter();
    if(this.activePoint.pointsToTheEndOfActiveEdge()) {
        this.activePoint = this.activePoint.moveToNextNodeOfActiveEdge();
    }
  }

  private Node edgeFromRootNodeHasNotCharacter(final int index,
                                             final char character,
                                             Node previouslyAddedNodeOrAddedEdgeNode) {
    final Node newNode = new Node(idGenerator++);
    this.activePoint.splitActiveEdge(this.word, newNode, index, character);
    previouslyAddedNodeOrAddedEdgeNode = this.activePoint.setSlinkTo(previouslyAddedNodeOrAddedEdgeNode, newNode);
    this.activePoint = this.activePoint.moveToEdgeStartingWithAndByActiveLengthMinusOne(this.root,
            this.word.charAt(index - this.remainder + 2));
    this.activePoint = walkDown(index);
    this.remainder--;
    return previouslyAddedNodeOrAddedEdgeNode;
  }

  private Node edgeFromInternalNodeHasNotCharacter(final int index,
                                                 final char character,
                                                 Node previouslyAddedNodeOrAddedEdgeNode) {
    final Node newNode = new Node(idGenerator++);
    this.activePoint.splitActiveEdge(this.word, newNode, index, character);
    previouslyAddedNodeOrAddedEdgeNode = this.activePoint.setSlinkTo(previouslyAddedNodeOrAddedEdgeNode, newNode);
    if(this.activePoint.activeNodeHasSlink()) {
        this.activePoint = this.activePoint.moveToSlink();
    }
    else {
        this.activePoint = this.activePoint.moveTo(this.root);
    }
    this.activePoint = walkDown(index);
    this.remainder--;
    return previouslyAddedNodeOrAddedEdgeNode;
  }

  private ActivePoint walkDown(final int index) {
    while(!this.activePoint.pointsToActiveNode()
            && (this.activePoint.pointsToTheEndOfActiveEdge() || this.activePoint.pointsAfterTheEndOfActiveEdge())) {
        if(this.activePoint.pointsAfterTheEndOfActiveEdge()) {
            this.activePoint = this.activePoint.moveToNextNodeOfActiveEdge(this.word, index);
        }
        else {
            this.activePoint = this.activePoint.moveToNextNodeOfActiveEdge();
        }
    }
    return this.activePoint;
  }

  public String toString(final String word) {
    return this.root.toString(word);
  }

  public boolean contains(final String suffix) {
    return this.root.contains(this.word, suffix);
  }

  public static void main(final String[] args) {
    final String[] words = {
            "abcabcabc$",
            "abc$",
            "abcabxabcd$",
            "abcabxabda$",
            "abcabxad$",
            "aabaaabb$",
            "aababcabcd$",
            "ababcabcd$",
            "abccba$",
            "mississipi$",
            "abacabadabacabae$",
            "abcabcd$",
            "00132220$"
    };
    Arrays.stream(words).forEach(word -> {
        System.out.println("Building suffix tree for word: " + word);
        final ST suffixTree = new ST(word);
        System.out.println("Suffix tree: " + suffixTree.toString(word));
        for(int i = 0; i < word.length() - 1; i++) {
            assert suffixTree.contains(word.substring(i)) : word.substring(i);
        }
    });
  }
}




suffix-tree