El algoritmo de Ukkonen

En informática , el algoritmo de Ukkonen es un algoritmo en línea de tiempo lineal para la construcción de á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, agregando caracteres sucesivos hasta completar el árbol. Esta suma ordenada de caracteres le confiere al algoritmo de Ukkonen su propiedad de "en línea". El algoritmo original presentado por Peter Weiner en 1973 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 en 1976, que va desde el sufijo más largo hasta el más corto. ^{[ 3 ]}

Al generar un árbol de sufijos usando 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á ninguna arista con la etiqueta $ (o cualquier otro carácter de terminación) ni ningún nodo interno con una sola arista que salga de él.

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

• El árbol de sufijos implícitos T _i+1 se construye sobre el árbol de sufijos implícitos T _i .
• En cualquier momento dado, el algoritmo de Ukkonen construye el árbol de sufijos para los caracteres vistos hasta el momento y, por lo tanto, tiene una 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 por cada carácter de la cadena de 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 el camino 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 el camino desde la raíz etiquetado como S[j...i] termina en una arista no hoja (es decir, hay más caracteres después de S[i] en el camino) y el siguiente carácter no es S[i+1], entonces se crea una nueva arista 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) una arista no hoja.
3. Si el camino 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 el camino) y el siguiente carácter es S[i+1] (que ya está en el árbol), no haga nada.

Un punto importante a tener en cuenta es que desde un nodo dado (raíz o interno), habrá una y solo una arista que comience con un carácter. No habrá más de una arista que salga de un mismo nodo comenzando con el mismo carácter.

La implementación ingenua para generar un árbol de sufijos requiere ^una complejidad temporal de O(n²) o incluso O(n³) en ^notación O grande , donde n es la longitud de la cadena . Aprovechando diversas técnicas algorítmicas, Ukkonen redujo esta complejidad a O ( n ) (lineal) para alfabetos de tamaño constante, y a O ( n log n ) en general, igualando el rendimiento en tiempo de ejecución de los dos algoritmos anteriores.

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. Construir${\displaystyle T_{1}}$para S[1]agregando el primer carácter de la cadena. Se aplica la regla 2, que crea un nuevo nodo hoja.
3. Construir${\displaystyle T_{2}}$para S[1..2]agregando sufijos de xa( xay a). 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 hoja.
4. Construir${\displaystyle T_{3}}$para S[1..3]agregando sufijos de xab( xab, aby b). 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 hoja.
5. Construir${\displaystyle T_{4}}$para S[1..4]agregando sufijos de xabx( xabx, abx, bxy x). Se aplica la regla 1, que extiende la etiqueta de ruta en el borde de hoja existente. Se aplica la regla 3, no hacer nada.
6. Construcciones${\displaystyle T_{5}}$para S[1..5]agregando sufijos de xabxa( xabxa, abxa, bxa, xay a). Se aplica la regla 1, que extiende la etiqueta de ruta en el borde de hoja existente. Se aplica la regla 3, no hacer nada.
7. Construcciones${\displaystyle T_{6}}$para S[1..6]agregando sufijos de xabxac( xabxac, abxac, bxac, xac, acy c). 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 hoja (en este caso, se crean tres nuevos bordes de hoja y dos nuevos nodos internos).

• Explicación detallada en lenguaje sencillo
• Búsqueda rápida de cadenas con árboles de sufijos. Tutorial de Mark Nelson. Incluye un ejemplo de implementación escrito en C++.
• Implementación en C con explicación detallada.
• Diapositivas de la presentación de Guy Blelloch
• Página principal de Ukkonen
• Proyecto de indexación de textos (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