En informática , el algoritmo de Ukkonen es un algoritmo en línea de tiempo lineal para construir á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 que se completa el árbol. Esta orden de adición de caracteres le da al algoritmo de Ukkonen su propiedad "en línea". El algoritmo original presentado por Peter Weiner procedió hacia atrás desde el último carácter al primero desde el sufijo más corto hasta el más largo. [2] Edward M. McCreight encontró un algoritmo más simple, pasando del sufijo más largo al más corto. [3]
Árbol de sufijos implícitos
Al generar un árbol de sufijos usando el algoritmo de Ukkonen, veremos un árbol de sufijos implícito en los pasos intermedios dependiendo de los caracteres de la cadena S. En los árboles de sufijos implícitos, no habrá borde con la etiqueta $ (o cualquier otro carácter de terminación) y ningún nodo interno con solo un borde saliendo de él.
Descripción de alto nivel del algoritmo de Ukkonen
El algoritmo de Ukkonen construye un árbol de sufijos implícitos T i para cada prefijo S [l ... i] os S (siendo S la cadena de longitud n). En primer lugar, se basa T 1 utilizando 1 st carácter, entonces T 2 usando 2 nd carácter, entonces T 3 utilizando 3 rd carácter, ..., T n utilizando el n º carácter. Puede encontrar las siguientes características en un árbol de sufijos que utiliza el algoritmo de Ukkonen:
- El árbol de sufijos implícitos T i +1 se construye sobre el árbol de sufijos implícitos T i .
- En un momento dado, el algoritmo de Ukkonen construye el árbol de sufijos para los caracteres vistos hasta ahora y, por lo tanto, tiene 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 para cada carácter de la cadena con longitud n).
- Cada fase i + 1 se divide en extensiones i + 1, una para cada uno de los sufijos i + 1 de S [1 ... i + 1].
La extensión de sufijo se trata de agregar el siguiente carácter en el árbol de sufijos construido hasta ahora. 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 estar seguro el sufijo S [j ... i + 1] está en el árbol. Hay tres reglas de extensión:
- Si la ruta desde la raíz etiquetada S [j ... i] termina en el borde de una hoja (es decir, S [i] es el último carácter en el borde de la hoja), entonces el carácter S [i + 1] se agrega al final de la etiqueta en ese borde de la hoja.
- si la ruta desde la raíz etiquetada S [j ... i] termina en el borde sin hoja (es decir, hay más caracteres después de S [i] en la ruta) y el siguiente carácter no es S [i + 1], entonces un nuevo el borde de la hoja con la etiqueta S [i + 1] y el número j se crea a partir del carácter S [i + 1]. También se creará un nuevo nodo interno si S [1 ... i] termina dentro (en el medio) de un borde sin hoja.
- Si la ruta desde la raíz etiquetada S [j..i] termina en el borde sin hoja (es decir, hay más caracteres después de S [i] en la ruta) y el siguiente carácter es s [i + 1] (ya en el árbol), hacer nada.
Un punto importante a tener en cuenta es que a partir de un nodo dado (raíz o interno), habrá una y solo una arista a partir de un carácter. No habrá más de un borde saliendo de cualquier nodo, comenzando con el mismo carácter.
Tiempo de ejecución
La implementación ingenua para generar un árbol de sufijos en el futuro requiere una complejidad de tiempo O ( n 2 ) o incluso O ( n 3 ) en notación O grande , donde n es la longitud de la cadena. Al explotar una serie de técnicas algorítmicas, Ukkonen redujo esto a tiempo O ( n ) (lineal), para alfabetos de tamaño constante, y O ( n log n ) en general, igualando el rendimiento en tiempo de ejecución de los dos algoritmos anteriores.
Ejemplo de algoritmo de Ukkonen
Para ilustrar mejor cómo se construye un árbol de sufijos usando el algoritmo de Ukkonen, podemos usar el siguiente ejemplo:
S = xabxac
- Comience con un nodo raíz vacío.
- Construya T 1 para S [1] agregando el primer carácter de la cadena. Se aplica la regla 2, que crea un nuevo nodo hoja.
- Construya T 2 para S [1 ... 2] agregando sufijos de xa (xa y a). Se aplica la regla 1, que extiende la etiqueta de la ruta en el borde de la hoja existente. Se aplica la regla 2, que crea un nuevo nodo hoja.
- Construya T 3 para S [1 ... 3] agregando sufijos de xab (xab, ab y b). Se aplica la regla 1, que extiende la etiqueta de la ruta en el borde de la hoja existente. Se aplica la regla 2, que crea un nuevo nodo hoja.
- Construya T 4 para S [1 ... 4] agregando sufijos de xabx (xabx, abx, bx y x). Se aplica la regla 1, que extiende la etiqueta de la ruta en el borde de la hoja existente. Se aplica la regla 3, no hagas nada.
- Construye T 5 para S [1 ... 5] agregando sufijos de xabxa (xabxa, abxa, bxa, xa y x). Se aplica la regla 1, que extiende la etiqueta de la ruta en el borde de la hoja existente. Se aplica la regla 3, no hagas nada.
- Construye T 6 para S [1 ... 6] agregando sufijos de xabxac (xabxac, abxac, bxac, xac, ac y c). Se aplica la regla 1, que extiende la etiqueta de la ruta en el borde de la hoja existente. Se aplica la regla 2, que crea un nuevo nodo hoja (en este caso, se crean tres nuevos bordes de ataque y dos nuevos nodos internos).
Referencias
- ^ Ukkonen, E. (1995). "Construcción on-line de árboles de sufijos" (PDF) . Algoritmica . 14 (3): 249–260. CiteSeerX 10.1.1.10.751 . doi : 10.1007 / BF01206331 . S2CID 6027556 .
- ^ Weiner, Peter (1973). "Algoritmos de coincidencia de patrones lineales" (PDF) . 14º Simposio Anual sobre Teoría de la Conmutación y Autómatas (SWAT 1973) . págs. 1-11. CiteSeerX 10.1.1.474.9582 . doi : 10.1109 / SWAT.1973.13 .
- ^ McCreight, Edward Meyers (1976). "Un algoritmo de construcción de árbol de sufijo económico de espacio". Revista de la ACM . 23 (2): 262–272. CiteSeerX 10.1.1.130.8022 . doi : 10.1145 / 321941.321946 . S2CID 9250303 .
enlaces externos
- Explicación detallada en inglés sencillo
- Búsqueda rápida de cadenas con árboles de sufijos Tutorial de Mark Nelson. Tiene un ejemplo de implementación escrito con C ++.
- Implementación en C con explicación detallada
- Diapositivas de la conferencia de Guy Blelloch
- Página de inicio de Ukkonen
- Proyecto de indexación de texto (construcción en tiempo lineal de árboles de sufijos de Ukkonen)
- Implementación en C Parte 1 Parte 2 Parte 3 Parte 4 Parte 5 Parte 6