Algoritmo de Ukkonen
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 *online*, 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.
como el árbol de sufijos implícito que representa todos los sufijos de
El algoritmo, aplicado a una cadena
La inclusión del carácter especial
En la extensión *j*-ésima de la fase
, el algoritmo busca el punto final del camino desde la raíz etiquetado con la subcadena
y, si es necesario, extiende dicho camino con el carácter
La extensión de los caminos se realiza según las siguientes reglas, aplicadas al sufijo
es el carácter a agregar: La extensión de los caminos se realiza según las siguientes reglas, aplicadas al sufijo
es el carácter a agregar: Regla 1: Extensión en Hoja Si el camino para
se añade al final de la etiqueta de la arista incidente en esa hoja.
Regla 2: Extensión en Arista o Nodo Interno Si el camino para
no termina en una hoja y ningún camino desde el punto final de
, se crea una nueva arista etiquetada con
termina en el interior de una arista existente, se crea un nuevo nodo para dividir la arista en el punto final de
Regla 3: Extensión Implícita Si algún camino desde el punto final de
ya se inicia con el carácter
, no es necesario realizar ninguna acción, ya que el sufijo
ya está representado en el árbol.
Los *enlaces de sufijos* son una estructura clave para la eficiencia del algoritmo: Definición: Sea
, entonces se define un *enlace de sufijo*
Los enlaces de sufijos facilitan la localización rápida de sufijos en el árbol, optimizando las operaciones de extensión.
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
) 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:
