Algoritmo de Ukkonen

En ciencias de la computación, el algoritmo de Ukkonen es un algoritmo on-line, con tiempo de computación lineal, para construir un árbol de sufijos de una cadena . Este algoritmo fue propuesto por Esko Ukkonen en 1995.

Anteriormente existían dos algoritmos capaces de construir el árbol de sufijos de una cadena en tiempo lineal, estos son el algoritmo de Weiner (1973) y el algoritmo de McCreight (1976). Pero el algoritmo de Ukkonen se destaca por ser más sencillo y por tener la característica de ser en línea.

Explicación del Algoritmo editar

Para explicar el algoritmo de Ukkonen partiremos de una implementación ingenua de este algoritmo que es   a la cual se le hacen sucesivas mejoras hasta obtener el  .

Sea   el árbol de sufijos implícito de la cadena  , con   desde   hasta  , el algoritmo de Ukkonen aplicado a la cadena   de longitud  , construye sucesivamente  . La ejecución del algoritmo de Ukkonen se divide en   fases, en la fase   se construye   modificando  , como el último carácter de   es   se cumple que   es el árbol de sufijos de  .

Cada fase   es a su vez dividida en   extensiones. En la extensión  -ésima de la fase   se busca el final del camino desde la raíz etiquetado con la subcadena   y se "extiende" dicho camino con el carácter  .

Reglas de extensión editar

A continuación se especifica cómo se realizan las extensiones.

Sea   un sufijo de  . En la extensión  , el algoritmo encuentra el final de   y lo extiende con el carácter   de acuerdo a una de las siguientes reglas:

Regla 1: (Extensión en una hoja)

El camino de   termina en una hoja. El carácter   es añadido al final de la etiqueta de la arista incidente en dicha hoja.

Regla 2: (Extensión en una arista o nodo interno)

El camino de   no termina en una hoja, pero ningún camino desde el final de   inicia con el carácter  . En este caso una nueva arista etiquetada con   es creada desde el final de  , dicha arista incide en una nueva hoja etiquetada con  . Si   termina en el interior de una arista, debe crearse además un nuevo nodo que corte dicha arista en el final de  .

Regla 3: (El carácter c ya aparece, no hay que hacer nada) Algún camino desde el final de   inicia con el carácter  . No es necesario hacer nada.

Suffix links editar

Definición: Sea un   nodo interno con etiqueta   donde   denota un carácter y   denota un string posiblemente vacío, si existe otro nodo   con etiqueta  , entonces un puntero de   a   es llamado un suffix link y se denota  .

Obsérvese que la definición no tiene sentido cuando   es la raíz, pues esta no está etiquetada con una cadena de la forma  .

Lema: Si al final de una fase, la cadena   pertenece al árbol, entonces la cadena   también pertenece.

Demostración: Si   se insertó en la extensión   de alguna fase  , en la extensión   de dicha fase se insertó  .

Teorema: Si un nuevo nodo interno   con etiqueta   es añadido al árbol en la extensión   de la fase  , entonces se tendrá uno de los siguientes casos:

  • El camino etiquetado   termina en un nodo interno.
  • En la extensión   un nodo interno al final del camino a será creado.

Demostración: Un nuevo nodo es creado en la extensión   de la fase   solamente cuando la extensión ocurre en una arista (regla 2). Por tanto el camino etiquetado con   continua con un carácter   distinto de  . Al inicio de la extensión  , por el lema anterior, se cumple que hay un camino etiquetado con   en el árbol y este continua con el carácter  , (y posiblemente con otros caracteres). Si el camino etiquetado con   continua con otros caracteres además de  , entonces este ya termina en un nodo interno (primera situación del teorema). Por otra parte si el camino etiquetado con   continua solamente con el carácter  , entonces en la extensión  , se aplicará la regla 2 y se creará un nodo interno al final de dicho camino (segunda situación del teorema).

Corolario: Al final de cada fase todos los nodos internos exceptuando la raíz tendrán un suffix link hacia otro nodo interno.

Usando los Suffix links para construir Ti+1 editar

Recordemos que en la extensión   de la fase   el algoritmo localiza el sufijo   de   con  , y luego realiza la extensión adecuada en dicho punto. Los suffix links se utilizarán para acortar el camino a la hora de localizar   en el árbol. Las primera extensión se puede realizar macheando el string   en el árbol, sin la ayuda de suffix links. Para realizar la extensión  , debemos analizar los posibles casos donde ocurrió la extensión  .

  • Si   ocurrió en un nodo interno   (distinto de la raíz), este estará etiquetado con el string   y tendrá un suffix link hacia un nodo   etiquetado con el string   (por ser un nodo interno distinto de la raíz, creado en una extensión anterior a la extensión   de la fase  ). Por tanto la extensión   se realizará en el nodo  .
  • Si   ocurrió en una hoja  , sea   el padre de  , y sea   la etiqueta de la arista  . Si   es la raíz, la extensión   se debe realizar macheando la cadena   desde la raíz. Por otra parte si   no es la raíz, entonces tiene un suffix link hacia el nodo  , para realizar la extensión  , basta machear la cadena   a partir de  .

-Si   ocurrió en una arista, sea   el nodo creado para partir dicha arista, sea   el padre   y sea   la etiqueta de la arista  . La extensión   se realiza de forma análoga al caso anterior.

Obsérvese que la extensión   no puede ocurrir en la raíz pues esta no es la última extensión de la fase.

Skip/count trick editar

Cuando se desea buscar la localización del final de una cadena   en el árbol y se tiene la certeza de que esta se encuentra (como es el caso de las búsquedas que se realizan en las extensiones), no es necesario machear la cadena   carácter a carácter, en estos casos es posible utilizar el skip/count trick que permite realizar la búsqueda en un orden linear respecto al número de nodos del camino.

Sea   el nodo en el que se encuentra el algoritmo, intentando localizar la cadena  , el skip/count trick ejecuta sucesivamente el siguiente procedimiento hasta obtener la posición buscada:

Si S es la cadena vacía, cur es la posición buscada.
Sino (cur,v) es la arista etiqueta L comparte el primer carácter con S (tiene que existir y ser única)
    Si |L|<|S|, la posición buscada es el carácter |S|-ésimo de la arista (cur,v).
    Sino hacer cur=v y eliminar los primeros |L| caracteres de S

Lema: Sea   un suffix link atravesado durante el algoritmo de Ukkonen. En ese momento   está acotada por  .

Demostración: Cuando el link   (es atravesado, todo nodo interno   ancestro de  , con etiqueta   (donde   es un carácter y   una cadena posiblemente vacía) tiene un suffix link hacia un nodo  , etiquetado con  , ancestro de  . Esta correspondencia es además unívoca. El único ancestro que puede tener   sin su correspondiente ancestro para   es la raíz.

Teorema: Usando el skip/count trick, toda fase del algoritmo de Ukkonen toma un tiempo   donde  .

Demostración: hay   extensiones en la fase  , en una extensión el algoritmo sube en el árbol a lo sumo un nodo, atraviesa a lo sumo un suffix link, baja en el árbol cierto número de nodos, aplica la extensión y añada a lo sumo un suffix link. Todas las operaciones distintas del descenso en el árbol toman tiempo constante. Solo necesitamos analizar la suma de los tiempos de realizar los descensos de todas las extensiones en la fase.

Para ello nos centraremos en la profundidad del nodo   donde el algoritmo termina la fase. Al inicio de la fase se parte de la raíz, que tiene profundidad  , como  , en la fase se realizan a lo sumo   descensos de profundidad (cuando se sube al padre o se atraviesa un suffix link), pero la profundidad del   está acotada por  , por tanto el número de aumentos de profundidad está acotado por   ya que  , y como cada descenso en el árbol aumenta la profundidad, el número de descensos en toda la fase está acotado por  . Por tanto el tiempo que toma realizar una fase es  .

Corolario: El algoritmo de Ukkonen puede ser implementado usando suffix links en tiempo  .

Extensiones implícitas editar

Observación: Una vez que la regla 3 aplica en la extensión   de la fase  , la regla 3 aplicará en el resto de las extensiones de la fase  .

Esto es debido a que cuando la regla 3 aplica, es porque la cadena   pertenece al árbol antes de realizar la extensión   y por tanto las cadenas   también pertenecen al árbol, por tanto en las extensiones  , la regla 3 también aplicará.

Observación: La extensión   crea un suffix link solo cuando en la extensión   aplica la regla 2.

Stop Trick editar

Es posible terminar la fase   la primera vez que la regla 3 aplique. Si esto ocurre en la extensión  , se dice que las extensiones   se realizaron de forma implícita.

Observación: Sea   la primera extensión de la fase   en la que la regla 3 aplica, se cumple que las primeras   extensiones de la fase   solo pudieron aplicar las reglas 1 o 2. Ambas reglas determinan una hoja etiquetada con el sufijo de   que se extendió. En la fase   las primeras   extensiones ocurrirán en las hojas determinadas por las primeras j'-1 extensiones de la fase i. Por tanto en las primeras   extensiones de la fase   aplicará la regla 1.

Observación: Cuando la regla 1 aplica en la fase  , en una hoja  , se sustituye la etiqueta   de la arista incidente en la hoja   por  . Esto da lugar a la siguiente mejora.

Pointer Trick editar

Cada vez que una hoja es creada en la fase  , se etiqueta la arista incidente a dicha hoja con el par  , el pointer trick propone etiquetar dicha arista con el par  , donde   es un puntero al número que identifica la fase actual. De esta forma no es necesario hacer nada cuando aplica la regla 1. Como se tiene que las primeras en las primeras   extensiones de la fase   aplicará la regla 1, es posible comenzar la fase   a partir de la extensión  , dejando que las primeras   extensiones, se realicen de forma implícita.

Teorema: El algoritmo de Ukkonen construye el árbol de sufijos de  , con los suffix links con costo espacial y temporal  .

Demostración: El tiempo para realizar todas las extensiones implícitas a lo largo del algoritmo es constante.

Consideremos el índice   correspondiente a la extensión explicita actual, en toda la ejecución del algoritmo de Ukkonen   nunca decrece, aunque sí se mantiene invariante cuando pasa de una fase a la siguiente. Como solo hay   fases, el número de extensiones explícitas está acotado por  . El algoritmo por tanto ejecuta a lo sumo   extensiones explícitas.

Como se explicó anteriormente el costo temporal de una extensión explícita depende del costo temporal de realizar el descenso en el árbol en dicha extensión. Para acotar el número de nodos recorridos en los descensos en el árbol durante el algoritmo de Ukkonen, es importante observar, que el nodo actual no varía cuando el algoritmo cambia de fase, la acotación se efectúa de forma análoga a como se hizo en la demostración del teorema anterior.

Referencias editar

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

Enlaces externos editar