Algoritmo de Ukkonen

Summarize Timeline Top Qs Fact Check

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.