Comprendere l'algoritmo di Ukkonen per gli alberi di suffisso

Sto lavorando con l'algoritmo di Ukkonen per la creazione di alberi di suffisso, ma non sto capendo alcune parti della spiegazione dell'autore per la sua complessità di tempo lineare.Comprendere l'algoritmo di Ukkonen per gli alberi di suffisso

ho imparato l'algoritmo e hanno codificato, ma la carta che sto usando come la principale fonte di informazioni (muggito linked) è un pò di confusione in alcune parti in modo non è davvero chiaro per me il motivo per cui l'algoritmo è lineare .

Qualsiasi aiuto? Grazie.

link di carta di Ukkonen: http://www.cs.helsinki.fi/u/ukkonen/SuffixT1withFigs.pdf

fonte

2009-08-20 Vinicius Pinto

A chiunque trovi questa domanda: ne è uscita una simile [qui] (http://stackoverflow.com/q/9452701/777186) e stiamo creando una descrizione dell'algoritmo come risposta Stackoverflow [qui] (http://stackoverflow.com/a/9513423/777186). – jogojapan

trovare una copia di Gusfield di string algorithms textbook. Ha la migliore esposizione della costruzione dell'albero dei suffissi che ho visto. La linearità è una conseguenza sorprendente di una serie di ottimizzazioni dell'algoritmo di alto livello.

fonte

2009-08-29 15:18:45

Esiste una versione animata di questo algo ukkonen? Scusa non ho potuto capire la natura costante della funzione di "aggiornamento". Ho provato anche gusfield, la carta di ukkonen e google: D – Seeker

Mi piacerebbe vedere un'animazione per costruire un suffisso generalizzato in tempo lineare. Generalmente la spiegazione basata sul testo non si adatta alla mia mente .. :) – Abhi

Il capitolo di Gusfields sugli alberi dei suffissi ha questa caratteristica fastidiosa, che usa diverse stringhe per illustrare i diversi passaggi - in modo da perdere il quadro generale. – maasha

Comprendere l'algoritmo di Ukkonen per gli alberi di suffisso

risposta

Problemi correlati