Entender el algoritmo de Ukkonen para árboles de sufijo

Estoy trabajando con el algoritmo de Ukkonen para construir árboles de sufijos, pero no estoy comprendiendo algunas partes de la explicación del autor por su complejidad de tiempo lineal.Entender el algoritmo de Ukkonen para árboles de sufijo

He aprendido el algoritmo y lo he codificado, pero el papel que utilizo como principal fuente de información (enlazado abajo) es un poco confuso en algunas partes, así que no está claro por qué el algoritmo es lineal .

¿Algún ayuda? Gracias.

Enlace al estudio de Ukkonen: http://www.cs.helsinki.fi/u/ukkonen/SuffixT1withFigs.pdf

Fuente

2009-08-20 Vinicius Pinto

Para cualquiera que encuentre esta pregunta: apareció una similar [aquí] (http://stackoverflow.com/q/9452701/777186) y estamos creando una descripción del algoritmo como una respuesta Stackoverflow [aquí] (http://stackoverflow.com/a/9513423/777186). – jogojapan

encontrar una copia de Gusfield de string algorithms textbook. Tiene la mejor exposición de la construcción del árbol de sufijos que he visto. La linealidad es una consecuencia sorprendente de una serie de optimizaciones del algoritmo de alto nivel.

Fuente

2009-08-29 15:18:45

¿Hay una versión animada de este ukkonen algo? Lo siento, no pude entender la naturaleza constante de la función de "actualización". Intenté gusfield, el papel de ukkonen y google también: D – Seeker

Me encantaría ver una animación para construir un árbol de sufijo generalizado en tiempo lineal. En general, la explicación basada en texto no cabe en mi mente ... :) – Abhi

El capítulo de Gusfields sobre árboles de sufijo tiene esta característica molesta, que utiliza diferentes cadenas para ilustrar los diferentes pasos, por lo que se pierde la imagen completa. – maasha

Entender el algoritmo de Ukkonen para árboles de sufijo

Respuesta

Cuestiones relacionadas