string suffix - Algoritmo dell'albero del suffisso di Ukkonen in inglese semplice




tree c++ (6)

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. Altrimenti è necessario aggiungere un nuovo nodo all'albero del suffisso nel punto attivo, eseguire il fallback alla corrispondenza più breve successiva e ricontrollare.

Nota 1: i puntatori del suffisso forniscono un collegamento alla corrispondenza più breve successiva per ciascun nodo.

Nota 2: quando aggiungi un nuovo nodo e un fallback, aggiungi un nuovo puntatore del suffisso per il nuovo nodo. La destinazione di questo puntatore del suffisso sarà il nodo nel punto attivo abbreviato. Questo nodo sarà già esistente o creato alla successiva iterazione di questo ciclo di fallback.

Nota 3: la parte di canonizzazione consente semplicemente di risparmiare tempo nel controllo del punto attivo. Ad esempio, supponi di aver sempre usato origin = 0 e appena cambiato prima e ultima. Per controllare il punto attivo dovresti seguire l'albero del suffisso ogni volta lungo tutti i nodi intermedi. Ha senso memorizzare nella cache il risultato di seguire questo percorso registrando solo la distanza dall'ultimo nodo.

Puoi dare un esempio di codice di cosa intendi per "fissare" le variabili di delimitazione?

Avvertenza sulla salute: ho trovato anche questo algoritmo particolarmente difficile da capire, quindi ti prego di capire che questa intuizione potrebbe non essere corretta in tutti i dettagli importanti ...

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 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).


Ciao ho provato a implementare l'implementazione spiegata sopra in ruby, per favore controlla. Sembra che funzioni bene.

l'unica differenza nell'implementazione è che, ho provato a usare l'oggetto edge invece di usare solo i simboli.

è anche presente su 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

r significa che la stringa deve essere trattata come una stringa raw, il che significa che tutti i codici di escape saranno ignorati.

Per un esempio:

'\n' sarà trattato come un carattere di nuova riga, mentre r'\n' sarà trattato come i caratteri \ seguiti da n .

Quando è presente un prefisso 'r' o 'R' , un carattere che segue una barra rovesciata è incluso nella stringa senza modifiche e tutte le barre retroverse sono lasciate nella stringa. Ad esempio, la stringa letterale r"\n" composta da due caratteri: una barra rovesciata e una 'n' minuscola. Le virgolette possono essere sfuggite con una barra rovesciata, ma la barra inversa rimane nella stringa; ad esempio, r"\"" è un letterale stringa valido composto da due caratteri: una barra rovesciata e una virgoletta doppia; r"\" non è un letterale stringa valido (anche una stringa non valida può terminare con un numero dispari di barre retroverse). In particolare, una stringa non può terminare in una singola barra rovesciata (poiché la barra rovesciata sfuggirebbe al seguente carattere di citazione). Si noti inoltre che una singola barra rovesciata seguita da una nuova riga viene interpretata come quei due caratteri come parte della stringa, non come una continuazione di riga. .

Fonte: letterali stringa Python





string algorithm language-agnostic suffix-tree