Algoritmo de Ukkonen

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, añadiendo caracteres sucesivos hasta que el árbol está completo. Esta adición ordenada de caracteres le da al algoritmo de Ukkonen su propiedad "en línea". El algoritmo original presentado por Peter Weiner procedía hacia atrás desde el último carácter hasta el primero, desde el sufijo más corto hasta el más largo. ^[2] Edward M. McCreight encontró un algoritmo más simple , que iba desde el sufijo más largo hasta el 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 en la cadena S. En los árboles de sufijos implícitos, no habrá ningún borde con etiqueta $ (o cualquier otro carácter de terminación) y ningún nodo interno con un solo borde que salga de él.

Descripción de alto nivel del algoritmo de Ukkonen.

El algoritmo de Ukkonen construye un árbol de sufijos implícito T _i para cada prefijo S[1...i] de S (siendo S la cadena de longitud n). Primero construye T ₁ utilizando el ^primer carácter, luego T ₂ utilizando el segundo ^carácter , luego T ₃ utilizando el tercer ^carácter , ..., T _n utilizando el enésimo ^carácter . Puedes encontrar las siguientes características en un árbol de sufijos que utiliza el algoritmo de Ukkonen:

• El árbol de sufijos implícitos T _i+1 se construye sobre el árbol de sufijos implícitos T _i .
• En cualquier momento, el algoritmo de Ukkonen construye el árbol de sufijos para los caracteres vistos hasta el momento y, por lo tanto, 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 con longitud n).
• Cada fase i+1 se divide a su vez en i+1 extensiones, una para cada uno de los i+1 sufijos de S[1...i+1].

La extensión de sufijos consiste en añadir el siguiente carácter al árbol de sufijos construido hasta el momento. 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 asegurarse de que el sufijo S[j...i+1] esté en el árbol. Hay tres reglas de extensión:

1. Si la ruta desde la raíz etiquetada S[j...i] termina en un borde de hoja (es decir, S[i] es el último carácter en el borde de hoja), entonces el carácter S[i+1] simplemente se agrega al final de la etiqueta en ese borde de hoja.
2. Si la ruta desde la raíz etiquetada S[j...i] termina en una arista 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 una nueva arista de hoja con etiqueta S[i+1] y número j comenzando desde el carácter S[i+1]. También se creará un nuevo nodo interno si S[1...i] termina dentro (en medio) de una arista que no es una hoja.
3. 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), no haga nada.

Un punto importante a tener en cuenta es que desde un nodo determinado (raíz o interno), habrá una única arista que comience con un carácter. No habrá más de una arista que salga 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 una complejidad temporal de O ( n ² ) o incluso de O ( n ³ ) en notación O grande , donde n es la longitud de la cadena. Al explotar una serie de técnicas algorítmicas, Ukkonen redujo esto a tiempo 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 finales utilizando el algoritmo de Ukkonen (ejemplo).

Para ilustrar mejor cómo se construye un árbol de sufijos utilizando el algoritmo de Ukkonen, podemos considerar la cadena S = xabxac.

1. Comience con un nodo raíz vacío.
2. Construya agregando el primer carácter de la cadena. Se aplica la regla 2, que crea un nuevo nodo de hoja. ${\displaystyle T_{1}}$S[1]
3. Construya para agregando los sufijos ( y ). Se aplica la regla 1, que extiende la etiqueta de ruta en el borde de hoja existente. Se aplica la regla 2, que crea un nuevo nodo de hoja. ${\displaystyle T_{2}}$S[1..2]xaxaa
4. Construya para agregando los sufijos ( , y ). Se aplica la regla 1, que extiende la etiqueta de ruta en el borde de hoja existente. Se aplica la regla 2, que crea un nuevo nodo de hoja. ${\displaystyle T_{3}}$S[1..3]xabxababb
5. Construya para agregando los sufijos ( , , y ). Se aplica la regla 1, que extiende la etiqueta de ruta en el borde de la hoja existente. Se aplica la regla 3, no haga nada. ${\displaystyle T_{4}}$S[1..4]xabxxabxabxbxx
6. Construcciones para mediante la adición de sufijos de ( , , , y ). Se aplica la regla 1, que extiende la etiqueta de ruta en el borde de la hoja existente. Se aplica la regla 3, no hacer nada. ${\displaystyle T_{5}}$S[1..5]xabxaxabxaabxabxaxaa
7. Construye para añadiendo sufijos de ( , , , y ). Se aplica la regla 1, que extiende la etiqueta de ruta en el borde de 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). ${\displaystyle T_{6}}$S[1..6]xabxacxabxacabxacbxacxacacc

Referencias

1. Ukkonen, E. (1995). "Construcción en línea de árboles de sufijos" (PDF) . Algorithmica . 14 (3): 249–260. CiteSeerX  10.1.1.10.751 . doi :10.1007/BF01206331. S2CID  6027556.
2. Weiner, Peter (1973). "Algoritmos de coincidencia de patrones lineales" (PDF) . 14.º Simposio anual sobre conmutación y teoría de autómatas (SWAT 1973) . pp. 1–11. CiteSeerX 10.1.1.474.9582 . doi :10.1109/SWAT.1973.13. 
3. McCreight, Edward Meyers (1976). "Un algoritmo de construcción de árboles de sufijos con economía espacial". Revista de la ACM . 23 (2): 262–272. CiteSeerX 10.1.1.130.8022 . doi :10.1145/321941.321946. S2CID  9250303. 

Enlaces externos

• Explicación detallada en un lenguaje sencillo.
• Búsqueda rápida de cadenas con árboles de sufijos Tutorial de Mark Nelson. Incluye un ejemplo de implementación escrito con C++.
• Implementación en C con explicación detallada
• Diapositivas de la conferencia de Guy Blelloch
• Página de inicio de Ukkonen
• Proyecto de indexación de texto (construcción de árboles de sufijos en tiempo lineal de Ukkonen)
• Implementación en C Parte 1 Parte 2 Parte 3 Parte 4 Parte 5 Parte 6