Construcción del árbol de sufijos de Ukkonen – Parte 4

Este artículo es la continuación de los siguientes tres artículos:
Construcción del árbol de sufijos de Ukkonen – Parte 1
Construcción del árbol de sufijos de Ukkonen – Parte 2
Construcción del árbol de sufijos de Ukkonen – Parte 3

Consulte la Parte 1 , la Parte 2 y la Parte 3 antes de ver el artículo actual, donde hemos visto algunos conceptos básicos sobre el árbol de sufijos, el algoritmo de ukkonen de alto nivel, el enlace de sufijo y tres trucos de implementación y algunos detalles sobre activePoint junto con una string de ejemplo » abcabxabcd” donde pasamos por cuatro fases de construcción del árbol de sufijos.

Repasemos esas cuatro fases que ya vimos en la Parte 3 , en términos de truco 2, truco 3 y punto activo.

• activePoint se inicializa en (raíz, NULL, 0), es decir, activeNode es raíz, activeEdge es NULL (para facilitar la comprensión, estamos dando valor de carácter a activeEdge, pero en la implementación del código, será el índice del carácter) y activeLength es CERO .
• La variable global END y la cuenta de sufijo restante se inicializan en CERO

*********************Fase 1*************************** ******
En la Fase 1, leemos el ^primer carácter (a) de la string S

• Establezca FIN en 1
• Incremente el número de sufijo restante en 1 (el número de sufijo restante será 1 aquí, es decir, queda 1 extensión por realizar)
• Ejecute un ciclo que resta SufijoContar veces (es decir, una vez) como se muestra a continuación:
  • Si activeLength es CERO, establezca activeEdge en el carácter actual (aquí activeEdge será ‘a’). Esto es APCFALZ .
  • Verifique si hay un borde que sale de activeNode (que es raíz en esta fase 1) para activeEdge. Si no, crea un borde de hoja. Si está presente, camine hacia abajo. En nuestro ejemplo, se crea el borde de la hoja (Regla 2).
  • Una vez que se realiza la extensión, disminuya el resto de SuffixCount en 1
  • En este punto, activePoint es (raíz, a, 0)

Al final de la fase 1, el número restante de sufijos es CERO (todos los sufijos se agregan explícitamente).
La Figura 20 en la Parte 3 es el árbol resultante después de la fase 1.

*********************Fase 2*************************** ******
En la Fase 2, leemos ^el segundo carácter (b) de la string S

• Establezca END en 2 (Esto hará la extensión 1)
• Incremente el número de sufijo restante en 1 (el número de sufijo restante será 1 aquí, es decir, queda 1 extensión por realizar)
• Ejecute un ciclo que resta SufijoContar veces (es decir, una vez) como se muestra a continuación:
• Si activeLength es CERO, establezca activeEdge en el carácter actual (aquí activeEdge será ‘b’). Esto es APCFALZ .
• Verifique si hay un borde que sale de activeNode (que es raíz en esta fase 2) para activeEdge. Si no, crea un borde de hoja. Si está presente, camine hacia abajo. En nuestro ejemplo, se crea el borde de la hoja.
• Una vez que se realiza la extensión, disminuya el resto de SuffixCount en 1
• En este punto, activePoint es (raíz, b, 0)

Al final de la fase 2, el número restante de sufijos es CERO (todos los sufijos se agregan explícitamente).
La Figura 22 en la Parte 3 es el árbol resultante después de la fase 2.

*********************Fase 3*************************** ******
En la Fase 3, leemos ^el tercer carácter (c) de la string S

• Establezca END en 3 (esto hará las extensiones 1 y 2)
• Incremente el número de sufijo restante en 1 (el número de sufijo restante será 1 aquí, es decir, queda 1 extensión por realizar)
• Ejecute un ciclo que resta SufijoContar veces (es decir, una vez) como se muestra a continuación:
• Si activeLength es CERO, establezca activeEdge en el carácter actual (aquí activeEdge será ‘c’). Esto es APCFALZ .
• Verifique si hay un borde que sale de activeNode (que es raíz en esta fase 3) para activeEdge. Si no, crea un borde de hoja. Si está presente, camine hacia abajo. En nuestro ejemplo, se crea el borde de la hoja.
• Una vez que se realiza la extensión, disminuya el resto de SuffixCount en 1
• En este punto, activePoint es (raíz, c, 0)

Al final de la fase 3, el número restante de sufijos es CERO (todos los sufijos se agregan explícitamente).
La Figura 25 en la Parte 3 es el árbol resultante después de la fase 3.

********************Fase 4*************************** ******
En la Fase 4, leemos el ^4º carácter (a) de la string S

• Establezca END en 4 (esto hará las extensiones 1, 2 y 3)
• Incremente el número de sufijo restante en 1 (el número de sufijo restante será 1 aquí, es decir, queda 1 extensión por realizar)
• Ejecute un ciclo que resta SufijoContar veces (es decir, una vez) como se muestra a continuación:
• Si activeLength es CERO, establezca activeEdge en el carácter actual (aquí activeEdge será ‘a’). Esto es APCFALZ .
• Verifique si hay un borde que sale de activeNode (que es raíz en esta fase 3) para activeEdge. Si no, crea un borde de hoja. Si está presente, camine hacia abajo (El truco 1 – saltar/contar). En nuestro ejemplo, el borde ‘a’ está presente saliendo de activeNode (es decir, raíz). No es necesario caminar hacia abajo ya que activeLength < edgeLength. Incrementamos activeLength de cero a 1 ( APCFER3 ) y detenemos cualquier procesamiento adicional (Regla 3).
• En este punto, activePoint es (root, a, 1) y restingSuffixCount permanece establecido en 1 (sin cambios allí)

Al final de la fase 4, el número de sufijos restantes es 1 (un sufijo ‘a’, el último, no se agrega explícitamente en el árbol, pero está implícitamente en el árbol).
La Figura 28 en la Parte 3 es el árbol resultante después de la fase 4.

Revisando las primeras cuatro fases completadas ^, continuaremos construyendo el árbol y veremos cómo va.

********************Fase 5*************************** ******
En la fase 5, leemos el quinto ^carácter (b) de la string S

• Establezca END en 5 (esto hará las extensiones 1, 2 y 3). Consulte la Figura 29 que se muestra a continuación.
• Incremente el número de sufijos restantes en 1 (el número de sufijos restantes será 2 aquí, es decir, quedan 2 extensiones por realizar, que son las extensiones 4 y 5. Se supone que la extensión 4 debe agregar el sufijo «ab» y la extensión 5 debe agregar el sufijo «b» en árbol)
• Ejecute un ciclo que resta SufijoCuenta veces (es decir, dos veces) como se muestra a continuación:
• Verifique si hay un borde que sale de activeNode (que es raíz en esta fase 3) para activeEdge. Si no, crea un borde de hoja. Si está presente, camine hacia abajo. En nuestro ejemplo, el borde ‘a’ está presente saliendo de activeNode (es decir, raíz).
• Haga una caminata hacia abajo (El truco 1 – saltar/contar) si es necesario. En la fase 5 actual, no es necesario caminar hacia abajo ya que activeLength < edgeLength. Aquí activePoint es (root, a, 1) para la extensión 4 (remainingSuffixCount = 2)
• Compruebe si el carácter actual de la string S (que es ‘b’) ya está presente después del punto activo. En caso afirmativo, no más procesamiento (regla 3). Lo mismo ocurre en nuestro ejemplo, por lo que incrementamos activeLength de 1 a 2 ( APCFER3 ) y nos detenemos aquí (Regla 3).
• En este punto, activePoint es (raíz, a, 2) y el número de sufijos restante permanece establecido en 2 (sin cambios en el número de sufijos restantes)

At the end of phase 5, remainingSuffixCount is 2 (Two suffixes, ‘ab’ and ‘b’, the last two, are not added explicitly in tree, but they are in tree implicitly).

********************Fase 6*************************** ******
En la fase 6, leemos el sexto ^carácter (x) de la string S

• Establezca END en 6 (esto hará las extensiones 1, 2 y 3)
  
• Incremente el número de sufijos restantes en 1 (el número de sufijos restantes será 3 aquí, es decir, quedan 3 extensiones por realizar, que son las extensiones 4, 5 y 6 para los sufijos «abx», «bx» y «x» respectivamente)
• Ejecute un ciclo restante de SufijoContador veces (es decir, tres veces) como se muestra a continuación:
• Mientras que la extensión 4, el punto activo es (raíz, a, 2) que apunta a ‘b’ en el borde que comienza con ‘a’.
• En la extensión 4, el carácter actual ‘x’ de la string S no coincide con el siguiente carácter en el borde después de activePoint, por lo que este es el caso de la regla de extensión 2. Por lo tanto, aquí se crea un borde de hoja con la etiqueta de borde x. También aquí el recorrido termina en medio de un borde, por lo que también se crea un nuevo Node interno al final de activePoint.
• Disminuya el RestanteSuffixCount en 1 (de 3 a 2) como sufijo «abx» agregado en el árbol.

Now activePoint will change after applying rule 2. Three other cases, (APCFER3, APCFWD and APCFALZ) where activePoint changes, are already discussed in Part 3.

Cambio de activePoint para la regla de extensión 2 (APCFER2):
Caso 1 (APCFER2C1): , luego disminuya activeLength en 1 y activeEdge se establecerá como “S[i – RestingSuffixCount + 1]”, donde i es el número de fase actual. ¿Puedes ver por qué este cambio en activePoint? Mire la extensión actual que acabamos de discutir anteriormente para la fase 6 (i = 6) nuevamente donde agregamos el sufijo «abx». ActiveLength es 2 y activeEdge es ‘a’. Ahora, en la próxima extensión, debemos agregar el sufijo «bx» en el árbol, es decir, la etiqueta de la ruta en la próxima extensión debe comenzar con ‘b’. Entonces, ‘b’ (el quinto ^carácter en la string S) debe ser el borde activo para la siguiente extensión y el índice de b será «i – restanteSuffixCount + 1» (6 – 2 + 1 = 5). activeLength se reduce en 1 porque activePoint se acerca a la raíz en 1 de longitud después de cada extensión.
Qué pasará Este caso ya está atendido por la APCFALZ .

Caso 2 (APCFER2C2): , luego siga el enlace del sufijo desde el ActiveNode actual. El nuevo Node (que puede ser el Node raíz u otro Node interno) al que apunta el enlace del sufijo será el Node activo para la próxima extensión. Sin cambios en activeLength y activeEdge. ¿Puedes ver por qué este cambio en activePoint? Esto se debe a que: si dos Nodes están conectados por un enlace de sufijo, entonces las etiquetas en todas las rutas que descienden desde esos dos Nodes, comenzando con el mismo carácter, serán exactamente iguales y, por lo tanto, para dos puntos similares correspondientes en esas rutas, activeEdge y activeLength serán ser el mismo y los dos Nodes serán el Node activo. Mire la Figura 18 en la Parte 2. Digamos que en la fase i y la extensión j, se agregó el sufijo ‘xAabcdedg’ en el árbol. En ese punto, digamos que ActivePoint era (Node-V, a, 7), es decir, el punto ‘g’. Entonces, para la próxima extensión j+1, agregaríamos el sufijo ‘Aabcdefg’ y para eso necesitamos atravesar ^2ndla ruta que se muestra en la Figura 18. Esto se puede hacer siguiendo el enlace de sufijo desde el ActiveNode v actual. El enlace de sufijo nos lleva a la ruta a recorrer en algún lugar entre [Node s(v)] debajo de la cual la ruta es exactamente igual a como estaba debajo del activeNode v anterior. Como se dijo anteriormente, «activePoint se acerca a la raíz por longitud 1 después de cada extensión», esta reducción en la longitud ocurrirá sobre el Node s (v) pero debajo de s (v), sin ningún cambio. Entonces, cuando activeNode no es raíz en la extensión actual, entonces para la próxima extensión, solo cambia activeNode (sin cambios en activeEdge y activeLength).

• En este punto de la extensión 4, el punto activo actual es (raíz, a, 2) y según APCFER2C1 , el nuevo punto activo para la próxima extensión 5 será (raíz, b, 1)
• El siguiente sufijo que se agregará es ‘bx’ (con el sufijo restante 2).
• El carácter actual ‘x’ de la string S no coincide con el siguiente carácter en el borde después de activePoint, por lo que este es el caso de la regla de extensión 2. Por lo tanto, aquí se crea un borde de hoja con la etiqueta de borde x. También aquí el recorrido termina en medio de un borde, por lo que también se crea un nuevo Node interno al final de activePoint.
  El enlace de sufijo también se crea desde el Node interno anterior (de la extensión 4) al nuevo Node interno creado en la extensión 5 actual.
• Disminuya el RestanteSuffixCount en 1 (de 2 a 1) como sufijo «bx» agregado en el árbol.

• En este punto de la extensión 5, el punto activo actual es (raíz, b, 1) y, según APCFER2C1 , el nuevo punto activo para la próxima extensión 6 será (raíz, x, 0)
• El siguiente sufijo que se agregará es ‘x’ (con el número de sufijo restante 1).
• En la próxima extensión 6, el carácter x no coincidirá con ningún borde existente desde la raíz, por lo que se creará un nuevo borde con la etiqueta x desde el Node raíz. Además, el enlace de sufijo del Node interno de la extensión anterior va a la raíz (ya que no se creó ningún Node interno nuevo en la extensión 6 actual).
• Disminuya el RestanteSuffixCount en 1 (de 1 a 0) como sufijo «x» agregado en el árbol

This completes the phase 6.
Note that phase 6 has completed all its 6 extensions (Why? Because the current character c was not seen in string so far, so rule 3, which stops further extensions never got chance to get applied in phase 6) and so the tree generated after phase 6 is a true suffix tree (i.e. not an implicit tree) for the characters ‘abcabx’ read so far and it has all suffixes explicitly in the tree.

Mientras se construía el árbol de arriba, se notaron los siguientes hechos:

• Un Node interno recién creado en la extensión i, apunta a otro Node interno o raíz (si activeNode es raíz en la extensión i+1) al final de la extensión i+1 mediante un enlace de sufijo (Cada Node interno DEBE tener un enlace de sufijo que apunte a otro Node interno o raíz)
• El enlace de sufijo proporciona un atajo mientras busca el final de la etiqueta de la ruta del siguiente sufijo
• Con un seguimiento adecuado de ActivePoints entre extensiones/fases, se puede evitar un recorrido innecesario desde la raíz.

Pasaremos por el resto de las fases (7 a 11) en la Parte 5 y construiremos el árbol por completo y luego veremos el código para el algoritmo en la Parte 6 .

Referencias :
http://web.stanford.edu/~mjkay/gusfield.pdf
Algoritmo de árbol de sufijos de Ukkonen en inglés simple

Este artículo es una contribución de Anurag Singh . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.