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

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

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

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

Regla 1: Extensión en Hoja

Si el camino para ${\displaystyle a}$  termina en una hoja, el carácter ${\displaystyle 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 ${\displaystyle a}$  no termina en una hoja y ningún camino desde el punto final de ${\displaystyle a}$  se inicia con el carácter ${\displaystyle c}$ , se crea una nueva arista etiquetada con ${\displaystyle c}$  desde el punto final de ${\displaystyle a}$ . Esta nueva arista incide en una nueva hoja etiquetada con ${\displaystyle j}$ . Si ${\displaystyle a}$  termina en el interior de una arista existente, se crea un nuevo nodo para dividir la arista en el punto final de ${\displaystyle 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 ${\displaystyle a}$  ya se inicia con el carácter ${\displaystyle c}$ , no es necesario realizar ninguna acción, ya que el sufijo ${\displaystyle 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.

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

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

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

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.

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 ${\displaystyle O(n)}$ , donde ${\displaystyle 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 ${\displaystyle O(n^{2})}$  o ${\displaystyle 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.

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.

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

• Implementación en Java
• Implementación en C#
• Presentación de Guy Blelloch