Algoritmo de Ukkonen

En ciencias de la computación, el algoritmo de Ukkonen es un algoritmo en línea de tiempo de computación lineal, diseñado para la construcción eficiente de un árbol de sufijos para una cadena $S$ . Propuesto por Esko Ukkonen en 1995, se distingue por su enfoque incremental y su relativa simplicidad en comparación con soluciones anteriores.

Previamente, existían dos algoritmos capaces de construir árboles de sufijos en tiempo lineal: el algoritmo de Weiner (1973) y el algoritmo de McCreight (1976). No obstante, el algoritmo de Ukkonen destaca por su naturaleza en línea, permitiendo el procesamiento de la cadena de entrada de manera progresiva, carácter a carácter, sin requerir la totalidad de la cadena al inicio.

Fundamentos del algoritmo

El algoritmo de Ukkonen se basa en la construcción iterativa de árboles de sufijos *implícitos*. Para una cadena $S[1..i]$ , se define $T_{i}$ como el árbol de sufijos implícito que representa todos los sufijos de $S[1..i]$ . El algoritmo, aplicado a una cadena $S\$$ de longitud $n$ , construye sucesivamente $T_{1},T_{2},...,T_{n}$ . La ejecución se divide en $n$ fases, donde la fase $i+1$ genera $T_{i+1}$ a partir de $T_{i}$ . La inclusión del carácter especial $\$$ al final de $S$ garantiza que $T_{n}$ represente el árbol de sufijos completo de $S$ .

Cada fase $i+1$ se subdivide en $i+1$ extensiones. En la extensión *j*-ésima de la fase $i+1$ , el algoritmo busca el punto final del camino desde la raíz etiquetado con la subcadena $S[j...i]$ y, si es necesario, extiende dicho camino con el carácter $S[i+1]$ .

Reglas de Extensión

La extensión de los caminos se realiza según las siguientes reglas, aplicadas al sufijo $S[j..i]=a$ de $S[1..i]$ en la extensión *j*, donde $c=S[i+1]$ es el carácter a agregar:

Regla 1: Extensión en Hoja

Si el camino para $a$ termina en una hoja, el carácter $c$ se añade al final de la etiqueta de la arista incidente en esa hoja.

Explicación: Imagina que llegaste al final de una rama en el árbol. Esta regla dice que, si quieres añadir el nuevo carácter `c`, simplemente lo "pegas" al final de esa rama. Por ejemplo, si tienes la palabra "ana" representada en el árbol y quieres añadir la letra "n" para formar "anan", simplemente añades la "n" al final de la rama que representa "ana".

Regla 2: Extensión en Arista o Nodo Interno

Si el camino para $a$ no termina en una hoja y ningún camino desde el punto final de $a$ se inicia con el carácter $c$ , se crea una nueva arista etiquetada con $c$ desde el punto final de $a$ . Esta nueva arista incide en una nueva hoja etiquetada con $j$ . Si $a$ termina en el interior de una arista existente, se crea un nuevo nodo para dividir la arista en el punto final de $a$ .

Explicación: Ahora imagina que no llegaste al final de una rama, sino que te encuentras en medio de una rama o en un punto donde se dividen varias ramas. Si no ves ninguna rama que empiece con el nuevo carácter `c`, entonces tienes que crear una nueva rama que salga desde ese punto y esté etiquetada con `c`. Si estás en medio de una rama existente, primero tienes que crear un nuevo punto de división (un nodo) para poder empezar la nueva rama con `c`.

Regla 3: Extensión Implícita

Si algún camino desde el punto final de $a$ ya se inicia con el carácter $c$ , no es necesario realizar ninguna acción, ya que el sufijo $S[j...i+1]$ ya está representado en el árbol.

Explicación: En este caso, ¡tienes suerte! El nuevo carácter `c` ya está presente en el árbol, saliendo desde el punto donde te encuentras. Esto significa que el sufijo que querías añadir ya está representado en el árbol, así que no tienes que hacer nada.

Enlaces de Sufijos (Suffix Links)

Los *enlaces de sufijos* son una estructura clave para la eficiencia del algoritmo:

Definición: Sea $v$ un nodo interno con etiqueta $xa$ , donde $x$ es un carácter y $a$ es una cadena (posiblemente vacía). Si existe otro nodo $s(v)$ con etiqueta $a$ , entonces se define un *enlace de sufijo* $(v,s(v))$ como un puntero de $v$ a $s(v)$ .

Los enlaces de sufijos facilitan la localización rápida de sufijos en el árbol, optimizando las operaciones de extensión.

Optimización del Algoritmo

El algoritmo de Ukkonen incorpora técnicas de optimización para alcanzar un tiempo de ejecución lineal:

Skip/Count Trick: Permite recorrer rápidamente las aristas del árbol cuando se conoce la existencia de un camino específico.
Stop Trick: Detiene la fase actual cuando la Regla 3 se aplica, evitando extensiones innecesarias.
Pointer Trick: Mantiene punteros a las hojas creadas, simplificando la aplicación de la Regla 1 en fases posteriores.

Complejidad computacional

Gracias a las reglas de extensión y las técnicas de optimización, el algoritmo de Ukkonen logra construir el árbol de sufijos en tiempo y espacio $O(n)$ , donde $n$ es la longitud de la cadena de entrada. Esta notación, conocida como "Big O", indica que tanto el tiempo que tarda el algoritmo en ejecutarse como la cantidad de memoria que necesita crecen linealmente con la longitud de la cadena de entrada. En otras palabras, si duplicamos la longitud de la cadena, el tiempo de ejecución y la memoria requerida también se duplicarán aproximadamente. Esta eficiencia es crucial para trabajar con textos extensos, ya que algoritmos con complejidades mayores (como $O(n^{2})$ o $O(n\log n)$ ) se volverían prohibitivamente lentos en estos casos. La complejidad lineal del algoritmo de Ukkonen se debe a la combinación inteligente de las reglas de extensión y las técnicas de optimización, que evitan la necesidad de realizar operaciones redundantes y permiten construir el árbol de sufijos de manera incremental y eficiente.

Aplicaciones

El algoritmo de Ukkonen es fundamental en diversas áreas de la informática, gracias a su eficiencia y capacidad para trabajar con cadenas de texto de manera flexible:

Búsqueda de patrones en texto: El algoritmo de Ukkonen permite construir un índice (el árbol de sufijos) que representa todos los sufijos de un texto dado. Una vez construido este índice, la búsqueda de cualquier patrón dentro del texto original se puede realizar de manera muy eficiente. En lugar de comparar el patrón con cada posible posición en el texto, se recorre el árbol de sufijos siguiendo el patrón. Si el patrón existe en el texto, este recorrido tendrá éxito, y la posición del patrón se puede determinar fácilmente. Esto es especialmente útil en aplicaciones como la búsqueda de palabras clave en documentos, la detección de plagio y la búsqueda de patrones en código fuente.

Compresión de datos: Aunque no es un algoritmo de compresión en sí mismo, el algoritmo de Ukkonen puede utilizarse como una herramienta auxiliar en algunos métodos de compresión. Por ejemplo, puede ayudar a identificar patrones repetidos en los datos, que luego pueden ser explotados por un algoritmo de compresión para reducir el tamaño del archivo. Al encontrar repeticiones de secuencias de caracteres, se pueden reemplazar estas secuencias por referencias más cortas, lo que reduce el espacio de almacenamiento necesario.

Análisis de secuencias biológicas (bioinformática): En bioinformática, el algoritmo de Ukkonen es una herramienta valiosa para analizar secuencias de ADN, ARN y proteínas. Estas secuencias pueden ser tratadas como cadenas de texto, y el algoritmo de Ukkonen permite identificar patrones significativos, como genes, motivos proteicos y regiones conservadas. Al construir el árbol de sufijos de una secuencia biológica, los investigadores pueden encontrar rápidamente repeticiones, similitudes con otras secuencias y posibles sitios de unión para proteínas. Esto ayuda a comprender la función de los genes y las proteínas, así como a identificar relaciones evolutivas entre diferentes especies.

Referencias

E. Ukkonen. (1995). On-line construction of suffix trees. Algorithmica 14(3):249-260. PDF | PDF with figures

Enlaces externos

Datos: Q7878334