Algoritmo para la construcción de árboles de sufijos.
En informática , el algoritmo de Ukkonen es un algoritmo en línea de tiempo lineal para construir árboles de sufijos , propuesto por Esko Ukkonen en 1995. [1] El algoritmo comienza con un árbol de sufijos implícito que contiene el primer carácter de la cadena. Luego recorre la cadena y agrega caracteres sucesivos hasta completar el árbol. Esta adición ordenada de caracteres le da al algoritmo de Ukkonen su propiedad "en línea". El algoritmo original presentado por Peter Weiner avanzaba hacia atrás desde el último carácter al primero, desde el sufijo más corto al más largo. [2] Edward M. McCreight encontró un algoritmo más simple , que va del sufijo más largo al más corto. [3]
Árbol de sufijos implícitos
Al generar un árbol de sufijos utilizando el algoritmo de Ukkonen, veremos un árbol de sufijos implícito en pasos intermedios dependiendo de los caracteres de la cadena S. En los árboles de sufijos implícitos, no habrá ningún borde con la etiqueta $ (o cualquier otro carácter de terminación) ni ningún nodo interno con solo un borde sale de él.
Descripción de alto nivel del algoritmo de Ukkonen.
El algoritmo de Ukkonen construye un árbol de sufijos implícito Ti para cada prefijo S[1...i] de S (siendo S la cadena de longitud n). Primero construye T 1 usando el primer carácter, luego T 2 usando el segundo carácter, luego T 3 usando el tercer carácter, ..., T n usando el enésimo carácter. Puede encontrar las siguientes características en un árbol de sufijos que utiliza el algoritmo de Ukkonen:
El árbol de sufijos implícitos Ti +1 se construye sobre el árbol de sufijos implícitos Ti .
En cualquier momento dado, el algoritmo de Ukkonen construye el árbol de sufijos para los caracteres vistos hasta ahora y por eso tiene propiedad en línea , lo que permite que el algoritmo tenga un tiempo de ejecución de O(n).
El algoritmo de Ukkonen se divide en n fases (una fase para cada carácter de la cadena de longitud n).
Cada fase i+1 se divide además en extensiones i+1, una para cada uno de los sufijos i+1 de S[1...i+1].
La extensión de sufijos consiste en agregar el siguiente carácter al árbol de sufijos creado hasta ahora. En la extensión j de la fase i+1, el algoritmo encuentra el final de S[j...i] (que ya está en el árbol debido a la fase i anterior) y luego extiende S[j...i] para estar seguro. el sufijo S[j...i+1] está en el árbol. Hay tres reglas de extensión:
Si la ruta desde la raíz etiquetada S[j...i] termina en el borde de una hoja (es decir, S[i] es el último carácter en el borde de la hoja), entonces el carácter S[i+1] simplemente se agrega al final de la etiqueta en el borde de esa hoja.
si la ruta desde la raíz etiquetada S[j...i] termina en un borde que no es una hoja (es decir, hay más caracteres después de S[i] en la ruta) y el siguiente carácter no es S[i+1], entonces Se crea un nuevo borde de hoja con la etiqueta S[i+1] y el número j a partir del carácter S[i+1]. También se creará un nuevo nodo interno si S[1...i] termina dentro (entre) de un borde que no es una hoja.
Si la ruta desde la raíz etiquetada S[j..i] termina en un borde que no es una hoja (es decir, hay más caracteres después de S[i] en la ruta) y el siguiente carácter es S[i+1] (ya en el árbol ), hacer nada.
Un punto importante a tener en cuenta es que desde un nodo determinado (raíz o interno), habrá una y sólo una arista a partir de un carácter. No habrá más de una arista saliendo de cualquier nodo que comience con el mismo carácter.
tiempo de ejecución
La implementación ingenua para generar un árbol de sufijos en el futuro requiere complejidad temporal O ( n 2 ) o incluso O ( n 3 ) en notación O grande , donde n es la longitud de la cadena. Al explotar una serie de técnicas algorítmicas, Ukkonen redujo este tiempo a O ( n ) (lineal), para alfabetos de tamaño constante, y O ( n log n ) en general, igualando el rendimiento en tiempo de ejecución de los dos algoritmos anteriores.
Ejemplo del algoritmo de Ukkonen
Árbol de sufijos final utilizando el algoritmo de Ukkonen (ejemplo).
Para ilustrar mejor cómo se construye un árbol de sufijos usando el algoritmo de Ukkonen, podemos usar el siguiente ejemplo:
S=xabxac
Comience con un nodo raíz vacío.
Construya T 1 para S[1] agregando el primer carácter de la cadena. Se aplica la regla 2, que crea un nuevo nodo hoja.
Construya T 2 para S[1...2] agregando sufijos de xa (xa y a). Se aplica la regla 1, que extiende la etiqueta de ruta en el borde de la hoja existente. Se aplica la regla 2, que crea un nuevo nodo hoja.
Construya T 3 para S[1...3] añadiendo los sufijos de xab (xab, ab y b). Se aplica la regla 1, que extiende la etiqueta de ruta en el borde de la hoja existente. Se aplica la regla 2, que crea un nuevo nodo hoja.
Construya T 4 para S[1...4] agregando sufijos de xabx (xabx, abx, bx y x). Se aplica la regla 1, que extiende la etiqueta de ruta en el borde de la hoja existente. Se aplica la regla 3, no hagas nada.
Construye T 5 para S[1...5] añadiendo sufijos de xabxa (xabxa, abxa, bxa, xa y a). Se aplica la regla 1, que extiende la etiqueta de ruta en el borde de la hoja existente. Se aplica la regla 3, no hagas nada.
Construye T 6 para S[1...6] agregando sufijos de xabxac (xabxac, abxac, bxac, xac, ac y c). Se aplica la regla 1, que extiende la etiqueta de ruta en el borde de la hoja existente. Se aplica la regla 2, que crea un nuevo nodo de hoja (en este caso, se crean tres nuevos bordes de hoja y dos nuevos nodos internos).
Referencias
^ Ukkonen, E. (1995). «Construcción online de árboles de sufijos» (PDF) . Algorítmica . 14 (3): 249–260. CiteSeerX 10.1.1.10.751 . doi :10.1007/BF01206331. S2CID 6027556.
