Algoritmo dell’albero del suffisso di Ukkonen in inglese semplice

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 nodes 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

    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 nodes, 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 objective 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

    inserisci la descrizione dell'immagine qui

    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 , 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 triggersmente 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 nodes 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 sum 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).

    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 nodes, eccetto la radice e le foglie sono nodes 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 triggers è maggiore di 0, quindi:

    1. il nodo attivo non è cambiato
    2. la lunghezza triggers è 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 nodes interni appena creati , ma anche i nodes 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 triggers rimangono invariati.

    In questa definizione della Rule 3 consideriamo anche gli inserti dei nodes foglia (non solo i nodes 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 nodes tramite un suffisso link:

      • prima di aggiungere l’ultima lettera c :

      • dopo aver aggiunto l’ultima lettera c :

    2. Se colleghiamo i nodes 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 nodes 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 colbind 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. Giava
    2. C ++

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

    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 nodes: 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.

      inserisci la descrizione dell'immagine qui

    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 nodes 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:

    • Pitone

    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.

    La mia intuizione è la seguente:

    Dopo k iterazioni del ciclo principale hai costruito un albero suffisso che contiene tutti i suffissi della stringa completa che iniziano nei primi k caratteri.

    All’inizio, ciò significa che l’albero del suffisso contiene un singolo nodo radice che rappresenta l’intera stringa (questo è l’unico suffisso che inizia da 0).

    Dopo le iterazioni di len (stringa) hai un albero di suffisso che contiene tutti i suffissi.

    Durante il ciclo il tasto è il punto attivo. La mia ipotesi è che questo rappresenti il ​​punto più profondo nell’albero del suffisso che corrisponde a un suffisso appropriato dei primi k caratteri della stringa. (Penso che sia corretto significa che il suffisso non può essere l’intera stringa.)

    Ad esempio, supponi di aver visto i caratteri “abcabc”. Il punto attivo rappresenterebbe il punto nell’albero corrispondente al suffisso ‘abc’.

    Il punto attivo è rappresentato da (origine, primo, ultimo). Ciò significa che ti trovi attualmente nel punto dell’albero che trovi iniziando dall’origine del nodo e quindi inserendo i caratteri nella stringa [first: last]

    Quando aggiungi un nuovo personaggio, cerchi di vedere se il punto attivo si trova ancora nell’albero esistente. Se è così, hai finito. Otherwise you need to add a new node to the suffix tree at the active point, fallback to the next shortest match, and check again.

    Note 1: The suffix pointers give a link to the next shortest match for each node.

    Note 2: When you add a new node and fallback you add a new suffix pointer for the new node. The destination for this suffix pointer will be the node at the shortened active point. This node will either already exist, or be created on the next iteration of this fallback loop.

    Note 3: The canonization part simply saves time in checking the active point. For example, suppose you always used origin=0, and just changed first and last. To check the active point you would have to follow the suffix tree each time along all the intermediate nodes. It makes sense to cache the result of following this path by recording just the distance from the last node.

    Can you give a code example of what you mean by “fix” bounding variables?

    Health warning: I also found this algorithm particularly hard to understand so please realise that this intuition is likely to be incorrect in all important details…

    Hi i have tried to implement the above explained implementation in ruby , please check it out. it seems to work fine.

    the only difference in the implementation is that , i have tried to use the edge object instead of just using symbols.

    its also present at https://gist.github.com/suchitpuri/9304856

      require 'pry' class Edge attr_accessor :data , :edges , :suffix_link def initialize data @data = data @edges = [] @suffix_link = nil end def find_edge element self.edges.each do |edge| return edge if edge.data.start_with? element end return nil end end class SuffixTrees attr_accessor :root , :active_point , :remainder , :pending_prefixes , :last_split_edge , :remainder def initialize @root = Edge.new nil @active_point = { active_node: @root , active_edge: nil , active_length: 0} @remainder = 0 @pending_prefixes = [] @last_split_edge = nil @remainder = 1 end def build string string.split("").each_with_index do |element , index| add_to_edges @root , element update_pending_prefix element add_pending_elements_to_tree element active_length = @active_point[:active_length] # if(@active_point[:active_edge] && @active_point[:active_edge].data && @active_point[:active_edge].data[0..active_length-1] == @active_point[:active_edge].data[[email protected]_point[:active_edge].data.length-1]) # @active_point[:active_edge].data = @active_point[:active_edge].data[0..active_length-1] # @active_point[:active_edge].edges << Edge.new(@active_point[:active_edge].data) # end if(@active_point[:active_edge] && @active_point[:active_edge].data && @active_point[:active_edge].data.length == @active_point[:active_length] ) @active_point[:active_node] = @active_point[:active_edge] @active_point[:active_edge] = @active_point[:active_node].find_edge(element[0]) @active_point[:active_length] = 0 end end end def add_pending_elements_to_tree element to_be_deleted = [] update_active_length = false # binding.pry if( @active_point[:active_node].find_edge(element[0]) != nil) @active_point[:active_length] = @active_point[:active_length] + 1 @active_point[:active_edge] = @active_point[:active_node].find_edge(element[0]) if @active_point[:active_edge] == nil @remainder = @remainder + 1 return end @pending_prefixes.each_with_index do |pending_prefix , index| # binding.pry if @active_point[:active_edge] == nil and @active_point[:active_node].find_edge(element[0]) == nil @active_point[:active_node].edges << Edge.new(element) else @active_point[:active_edge] = node.find_edge(element[0]) if @active_point[:active_edge] == nil data = @active_point[:active_edge].data data = data.split("") location = @active_point[:active_length] # binding.pry if(data[0..location].join == pending_prefix or @active_point[:active_node].find_edge(element) != nil ) else #tree split split_edge data , index , element end end end end def update_pending_prefix element if @active_point[:active_edge] == nil @pending_prefixes = [element] return end @pending_prefixes = [] length = @active_point[:active_edge].data.length data = @active_point[:active_edge].data @remainder.times do |ctr| @pending_prefixes << data[-(ctr+1)..data.length-1] end @pending_prefixes.reverse! end def split_edge data , index , element location = @active_point[:active_length] old_edges = [] internal_node = (@active_point[:active_edge].edges != nil) if (internal_node) old_edges = @active_point[:active_edge].edges @active_point[:active_edge].edges = [] end @active_point[:active_edge].data = data[0..location-1].join @active_point[:active_edge].edges << Edge.new(data[location..data.size].join) if internal_node @active_point[:active_edge].edges << Edge.new(element) else @active_point[:active_edge].edges << Edge.new(data.last) end if internal_node @active_point[:active_edge].edges[0].edges = old_edges end #setup the suffix link if @last_split_edge != nil and @[email protected]_point[:active_edge].data @last_split_edge.suffix_link = @active_point[:active_edge] end @last_split_edge = @active_point[:active_edge] update_active_point index end def update_active_point index if(@active_point[:active_node] == @root) @active_point[:active_length] = @active_point[:active_length] - 1 @remainder = @remainder - 1 @active_point[:active_edge] = @active_point[:active_node].find_edge(@pending_prefixes.first[index+1]) else if @active_point[:active_node].suffix_link != nil @active_point[:active_node] = @active_point[:active_node].suffix_link else @active_point[:active_node] = @root end @active_point[:active_edge] = @active_point[:active_node].find_edge(@active_point[:active_edge].data[0]) @remainder = @remainder - 1 end end def add_to_edges root , element return if root == nil root.data = root.data + element if(root.data and root.edges.size == 0) root.edges.each do |edge| add_to_edges edge , element end end end suffix_tree = SuffixTrees.new suffix_tree.build("abcabxabcd") binding.pry 

    @jogojapan you brought awesome explanation and visualisation. But as @makagonov mentioned it’s missing some rules regarding setting suffix links. It’s visible in nice way when going step by step on http://brenden.github.io/ukkonen-animation/ through word ‘aabaaabb’. When you go from step 10 to step 11, there is no suffix link from node 5 to node 2 but active point suddenly moves there.

    @makagonov since I live in Java world I also tried to follow your implementation to grasp ST building workflow but it was hard to me because of:

    • combining edges with nodes
    • using index pointers instead of references
    • breaks statements;
    • continue statements;

    So I ended up with such implementation in Java which I hope reflects all steps in clearer way and will reduce learning time for other Java people:

     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 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 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 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); } }); } }