string - El algoritmo del árbol de sufijos de Ukkonen en inglés simple

algorithm language-agnostic

Question

Me siento un poco grueso en este punto. He pasado días tratando de envolver por completo mi cabeza alrededor de la construcción del árbol de sufijos, pero debido a que no tengo una base matemática, muchas de las explicaciones se me escapan cuando comienzan a usar la simbología matemática en forma excesiva. Lo más cercano a una buena explicación que he encontrado es la búsqueda rápida de cadenas con árboles de sufijos , pero él pasa por alto varios puntos y algunos aspectos del algoritmo siguen sin estar claros.

Una explicación paso a paso de este algoritmo aquí en Stack Overflow sería invaluable para muchos otros además de mí, estoy seguro.

Para referencia, aquí está el artículo de Ukkonen sobre el algoritmo: http://www.cs.helsinki.fi/u/ukkonen/SuffixT1withFigs.pdf

Mi entendimiento básico, hasta ahora:

• Necesito recorrer cada prefijo P de una cadena dada T
• Necesito iterar a través de cada sufijo S en el prefijo P y agregarlo al árbol
• Para agregar el sufijo S al árbol, debo recorrer cada carácter en S, con las iteraciones que consisten en caminar por una rama existente que comienza con el mismo conjunto de caracteres C en S y potencialmente dividir un borde en nodos descendentes cuando yo alcanzar un carácter diferente en el sufijo, O si no había un borde coincidente para caminar hacia abajo. Cuando no se encuentra un borde coincidente para bajar hacia C, se crea un nuevo borde de hoja para C.

El algoritmo básico parece ser O (n ² ), como se señala en la mayoría de las explicaciones, ya que necesitamos pasar por todos los prefijos, luego debemos pasar por cada uno de los sufijos para cada prefijo. El algoritmo de Ukkonen es aparentemente único debido a la técnica de puntero de sufijo que utiliza, aunque creo que eso es lo que me cuesta entender.

También estoy teniendo problemas para entender:

• exactamente cuándo y cómo se asigna, utiliza y cambia el "punto activo"
• ¿Qué está pasando con el aspecto de canonización del algoritmo?
• Por qué las implementaciones que he visto necesitan "arreglar" las variables de límite que están usando

Aquí está el código fuente de C # completado. No solo funciona correctamente, sino que también admite la canonización automática y ofrece un gráfico de texto de aspecto más agradable. El código fuente y la salida de muestra están en:

https://gist.github.com/2373868

Actualización 2017-11-04

Después de muchos años, he encontrado un nuevo uso para los árboles de sufijos y he implementado el algoritmo en JavaScript . La esencia está abajo. Debe estar libre de errores. Volcarlo en un archivo js, npm install chalk desde la misma ubicación, y luego ejecuta con node.js para ver algunos resultados coloridos. Hay una versión simplificada en el mismo Gist, sin ningún código de depuración.

https://gist.github.com/axefrog/c347bf0f5e0723cbd09b1aaed6ec6fc6

Answer 1

El siguiente es un intento de describir el algoritmo de Ukkonen mostrando primero lo que hace cuando la cadena es simple (es decir, no contiene ningún carácter repetido), y luego extendiéndola al algoritmo completo.

Primero, unas pocas declaraciones preliminares.

1. Lo que estamos construyendo, es básicamente como una búsqueda. Así que hay un nodo raíz, los bordes salen de él, lo que lleva a nuevos nodos, y otros bordes salen de esos, y así sucesivamente.

2. Pero : a diferencia de en una búsqueda, las etiquetas de borde no son caracteres individuales. En su lugar, cada borde se etiqueta utilizando un par de enteros [from,to] . Estos son punteros en el texto. En este sentido, cada borde lleva una etiqueta de cadena de longitud arbitraria, pero solo ocupa espacio O (1) (dos punteros).

Principio básico

Primero me gustaría demostrar cómo crear el árbol de sufijos de una cadena particularmente simple, una cadena sin caracteres repetidos:

abc

El algoritmo funciona en pasos, de izquierda a derecha . Hay un paso para cada carácter de la cadena . Cada paso puede involucrar más de una operación individual, pero veremos (ver las observaciones finales al final) que el número total de operaciones es O (n).

Por lo tanto, comenzamos desde la izquierda y primero insertamos solo el carácter único a creando un borde desde el nodo raíz (a la izquierda) a una hoja, y etiquetándolo como [0,#] , lo que significa que el borde representa la subcadena comenzando en la posición 0 y terminando en el final actual . Utilizo el símbolo # para indicar el final actual , que está en la posición 1 (justo después de a ).

Así que tenemos un árbol inicial, que se ve así:

Y lo que significa es esto:

Ahora avanzamos a la posición 2 (justo después de b ). Nuestro objetivo en cada paso es insertar todos los sufijos hasta la posición actual . Hacemos esto por

• expandiendo el existente a -edge a ab
• insertando un borde nuevo para b

En nuestra representación esto parece

Y lo que significa es:

Observamos dos cosas:

• La representación de borde para ab es la misma que solía estar en el árbol inicial: [0,#] . Su significado ha cambiado automáticamente porque actualizamos la posición actual # de 1 a 2.
• Cada borde consume espacio O (1), ya que consta de solo dos punteros en el texto, independientemente de cuántos caracteres represente.

A continuación, incrementamos la posición nuevamente y actualizamos el árbol agregando una c a cada borde existente e insertando un borde nuevo para el nuevo sufijo c .

En nuestra representación esto parece

Y lo que significa es:

Observamos:

• El árbol es el árbol de sufijos correcto hasta la posición actual después de cada paso
• Hay tantos pasos como caracteres en el texto.
• La cantidad de trabajo en cada paso es O (1), porque todos los bordes existentes se actualizan automáticamente incrementando # , y la inserción del borde nuevo para el carácter final se puede hacer en O (1). Por lo tanto, para una cadena de longitud n, solo se requiere O (n) tiempo.

Primera extensión: Repeticiones simples.

Por supuesto, esto funciona muy bien solo porque nuestra cadena no contiene ninguna repetición. Ahora nos fijamos en una cadena más realista:

abcabxabcd

Comienza con abc como en el ejemplo anterior, luego se repite ab y se sigue con x , y luego se repite abc seguido de d .

Pasos 1 a 3: Después de los primeros 3 pasos tenemos el árbol del ejemplo anterior:

Paso 4: Movemos # a la posición 4. Esto actualiza implícitamente todos los bordes existentes a esto:

y necesitamos insertar el sufijo final del paso actual, a , en la raíz.

Antes de hacer esto, introducimos dos variables más (además de # ), que por supuesto han estado allí todo el tiempo pero no las hemos usado hasta ahora:

• El punto activo , que es un triple (active_node,active_edge,active_length)
• El remainder , que es un número entero que indica cuántos sufijos nuevos necesitamos insertar

El significado exacto de estos dos se aclarará pronto, pero por ahora solo digamos:

• En el ejemplo abc simple, el punto activo siempre fue (root,''/0x'',0) , es decir, active_node era el nodo raíz, active_edge se especificó como el carácter nulo ''/0x'' , y active_length era cero. El efecto de esto fue que el nuevo borde que insertamos en cada paso se insertó en el nodo raíz como un borde recién creado. Pronto veremos por qué es necesario un triple para representar esta información.
• El remainder siempre se estableció en 1 al comienzo de cada paso. El significado de esto fue que el número de sufijos que tuvimos que insertar activamente al final de cada paso fue 1 (siempre solo el carácter final).

Ahora esto va a cambiar. Cuando insertamos el carácter final actual a en la raíz, notamos que ya hay un borde saliente que comienza con a , específicamente: abca . Aquí es lo que hacemos en tal caso:

• No insertamos un borde nuevo [4,#] en el nodo raíz. En su lugar, simplemente notamos que el sufijo a ya está en nuestro árbol. Termina en medio de un borde más largo, pero eso no nos molesta. Simplemente dejamos las cosas como son.
• Establecemos el punto activo en (root,''a'',1) . Eso significa que el punto activo ahora está en algún lugar en medio del borde saliente del nodo raíz que comienza con, específicamente, después de la posición 1 en ese borde. Notamos que el borde está especificado simplemente por su primer carácter a . Eso es suficiente porque solo puede haber un borde que comience con un carácter particular (confirme que esto es cierto después de leer toda la descripción).
• También incrementamos el remainder , por lo que al comienzo del siguiente paso será 2.

Observación: Cuando se encuentra que el sufijo final que necesitamos insertar ya existe en el árbol , el árbol en sí no se modifica en absoluto (solo actualizamos el punto activo y el remainder ). El árbol ya no es una representación precisa del árbol de sufijos hasta la posición actual , pero contiene todos los sufijos (porque el sufijo final a está contenido implícitamente ). Por lo tanto, aparte de actualizar las variables (que son todas de longitud fija, por lo que es O (1)), no se realizó ningún trabajo en este paso.

Paso 5: Actualizamos la posición actual # a 5. Esto actualiza automáticamente el árbol a esto:

Y como el remainder es 2 , necesitamos insertar dos sufijos finales de la posición actual: ab y b . Esto es básicamente porque:

• El sufijo a del paso anterior nunca se ha insertado correctamente. Así que ha permanecido , y desde que hemos avanzado un paso, ahora ha crecido de a a ab .
• Y necesitamos insertar el nuevo borde final b .

En la práctica, esto significa que vamos al punto activo (que apunta a detrás de la a en lo que ahora es el borde abcab ), e insertamos el carácter final actual b . Pero: de nuevo, resulta que b también está ya presente en ese mismo borde.

Así que, de nuevo, no cambiamos el árbol. Nosotros simplemente:

• Actualice el punto activo a (root,''a'',2) (mismo nodo y borde que antes, pero ahora apuntamos a detrás de la b )
• Incremente el remainder a 3 porque todavía no hemos insertado correctamente el borde final del paso anterior, y tampoco insertamos el borde final actual.

Para ser claros: tuvimos que insertar ab y b en el paso actual, pero como ya se encontró ab , actualizamos el punto activo y ni siquiera intentamos insertar b . ¿Por qué? Porque si ab está en el árbol, todos los sufijos (incluido b ) también deben estar en el árbol. Quizás solo de manera implícita , pero debe estar allí, debido a la forma en que hemos construido el árbol hasta ahora.

Continuamos con el paso 6 incrementando # . El árbol se actualiza automáticamente a:

Como el remainder es 3 , tenemos que insertar abx , bx y x . El punto activo nos dice dónde termina ab , por lo que solo necesitamos saltar allí e insertar la x . De hecho, x aún no está allí, por lo que dividimos el borde abcabx e insertamos un nodo interno:

Las representaciones de borde aún son punteros en el texto, por lo que la división y la inserción de un nodo interno se pueden hacer en O (1).

Así que hemos tratado con abx y reducir el remainder a 2. Ahora necesitamos insertar el siguiente sufijo restante, bx . Pero antes de hacerlo necesitamos actualizar el punto activo. La regla para esto, después de dividir e insertar un borde, se llamará Regla 1 a continuación, y se aplica siempre que el active_node sea ​​raíz (aprenderemos la regla 3 para otros casos más adelante). Aquí está la regla 1:

Después de una inserción desde la raíz,

• active_node permanece root
• active_edge se establece en el primer carácter del nuevo sufijo que necesitamos insertar, es decir, b
• active_length se reduce en 1

Por lo tanto, el nuevo triple de punto activo (root,''b'',1) indica que la siguiente inserción debe realizarse en el borde bcabx , detrás de 1 carácter, es decir, detrás de b . Podemos identificar el punto de inserción en tiempo O (1) y verificar si x ya está presente o no. Si estuviera presente, terminaríamos el paso actual y dejaríamos todo como está. Pero x no está presente, así que lo insertamos dividiendo el borde:

Nuevamente, esto tomó O (1) tiempo y actualizamos el remainder a 1 y el punto activo a (root,''x'',0) como indica la regla 1.

Pero hay una cosa más que tenemos que hacer. Llamaremos a esto Regla 2:

Si dividimos un borde e insertamos un nuevo nodo, y si ese no es el primer nodo creado durante el paso actual, conectamos el nodo previamente insertado y el nuevo nodo a través de un puntero especial, un enlace de sufijo . Más adelante veremos por qué es útil. Aquí está lo que obtenemos, el enlace del sufijo se representa como un borde punteado:

Todavía necesitamos insertar el sufijo final del paso actual, x . Dado que el componente active_length del nodo activo ha caído a 0, la inserción final se realiza directamente en la raíz. Como no hay un borde saliente en el nodo raíz que comienza con x , insertamos un nuevo borde:

Como podemos ver, en el paso actual se realizaron todas las inserciones restantes.

Continuamos con el paso 7 estableciendo # = 7, que agrega automáticamente el siguiente carácter, a , a todos los bordes de las hojas, como siempre. Luego intentamos insertar el nuevo carácter final en el punto activo (la raíz), y encontramos que ya está allí. Así que terminamos el paso actual sin insertar nada y actualizamos el punto activo a (root,''a'',1) .

En el paso 8 , # = 8, agregamos b , y como se vio anteriormente, esto solo significa que actualizamos el punto activo a (root,''a'',2) y al remainder incremento sin hacer nada más, porque b ya está presente. Sin embargo, notamos (en O (1) tiempo) que el punto activo ahora está al final de un borde. Reflejamos esto volviendo a configurarlo en (node1,''/0x'',0) . Aquí, uso node1 para referirme al nodo interno donde termina el borde ab .

Luego, en el paso # = 9 , necesitamos insertar ''c'' y esto nos ayudará a entender el truco final:

Segunda extensión: Uso de enlaces de sufijo.

Como siempre, la # actualización agrega c automáticamente a los bordes de la hoja y vamos al punto activo para ver si podemos insertar ''c''. Resulta que ''c'' ya existe en ese borde, por lo que establecemos el punto activo en (node1,''c'',1) , incrementamos el remainder y no hacemos nada más.

Ahora, en el paso # = 10 , el remainder is 4 , por lo que primero necesitamos insertar abcd (que permanece desde hace 3 pasos) insertando d en el punto activo.

El intento de insertar d en el punto activo provoca una división del borde en el tiempo O (1):

El active_node , desde el cual se inició la división, está marcado en rojo arriba. Aquí está la regla final, Regla 3:

Después de dividir un borde de un active_node que no es el nodo raíz, seguimos el enlace de sufijo que sale de ese nodo, si existe alguno, y restablecemos el nodo active_node al nodo al que apunta. Si no hay un enlace de sufijo, establecemos el active_node en la raíz. active_edge y active_length permanecen sin cambios.

Entonces el punto activo es ahora (node2,''c'',1) , y el node2 está marcado en rojo a continuación:

Como la inserción de abcd está completa, disminuimos el remainder a 3 y consideramos el siguiente sufijo restante del paso actual, bcd . La Regla 3 ha establecido el punto activo solo en el nodo y borde derecho, de modo que la inserción de bcd se puede hacer simplemente insertando su carácter final d en el punto activo.

Hacer esto causa otra división de borde, y debido a la regla 2 , debemos crear un enlace de sufijo desde el nodo insertado previamente al nuevo:

Observamos: los enlaces de sufijo nos permiten restablecer el punto activo para que podamos realizar la próxima inserción restante en el esfuerzo O (1). Mire el gráfico anterior para confirmar que, efectivamente, el nodo en la etiqueta ab está vinculado al nodo en b (su sufijo), y el nodo en abc está vinculado a bc .

El paso actual aún no está terminado. remainder ahora es 2, y debemos seguir la regla 3 para restablecer el punto activo nuevamente. Dado que el active_node actual (rojo arriba) no tiene un enlace de sufijo, restablecemos a la raíz. El punto activo es ahora (root,''c'',1) .

Por lo tanto, la siguiente inserción se produce en el borde saliente del nodo raíz cuya etiqueta comienza con c : cabxabcd , detrás del primer carácter, es decir, detrás de c . Esto causa otra división:

Y como esto implica la creación de un nuevo nodo interno, seguimos la regla 2 y establecemos un nuevo enlace de sufijo desde el nodo interno creado anteriormente:

(Estoy usando Graphviz Dot para estos pequeños gráficos. El nuevo enlace de sufijo hizo que el punto reorganizara los bordes existentes, así que verifique cuidadosamente para confirmar que lo único que se insertó anteriormente es un nuevo enlace de sufijo).

Con esto, el remainder se puede establecer en 1 y dado que el active_node es root, usamos la regla 1 para actualizar el punto activo a (root,''d'',0) . Esto significa que la inserción final del paso actual es insertar una sola d en la raíz:

Ese fue el paso final y hemos terminado. Hay varias observaciones finales , sin embargo:

• En cada paso nos movemos # hacia adelante por 1 posición. Esto actualiza automáticamente todos los nodos de hoja en O (1) tiempo.

• Pero no trata con a) los sufijos restantes de los pasos anteriores, yb) con el carácter final del paso actual.

• remainder nos dice cuántas inserciones adicionales necesitamos hacer. Estas inserciones corresponden de uno a uno a los sufijos finales de la cadena que termina en la posición actual # . Consideramos uno tras otro y hacemos el inserto. Importante: Cada inserción se realiza en O (1), ya que el punto activo nos dice exactamente dónde ir, y debemos agregar un solo carácter en el punto activo. ¿Por qué? Porque los otros personajes están contenidos implícitamente (de lo contrario, el punto activo no estaría donde está).

• Después de cada inserción, decrementamos el remainder y seguimos el enlace del sufijo, si hay alguno. Si no vamos a la raíz (regla 3). Si ya estamos en la raíz, modificamos el punto activo utilizando la regla 1. En cualquier caso, solo toma O (1) tiempo.

• Si, durante una de estas inserciones, encontramos que el carácter que queremos insertar ya está allí, no hacemos nada y finalizamos el paso actual, incluso si el remainder > 0. La razón es que cualquier inserto que quede será un sufijo del que acabamos de hacer. Por lo tanto, todos están implícitos en el árbol actual. El hecho de que el remainder > 0 asegure que tratemos los sufijos restantes más adelante.

• ¿Qué pasa si al final del algoritmo el remainder > 0? Este será el caso siempre que el final del texto sea una subcadena que haya ocurrido antes en algún lugar. En ese caso, debemos agregar un carácter adicional al final de la cadena que no haya ocurrido antes. En la literatura, usualmente el signo de dólar $ se usa como un símbolo para eso. ¿Por que importa? -> Si luego utilizamos el árbol de sufijos completado para buscar sufijos, debemos aceptar coincidencias solo si terminan en una hoja . De lo contrario, obtendríamos muchas coincidencias espurias, porque hay muchas cadenas implícitamente contenidas en el árbol que no son sufijos reales de la cadena principal. Forzar que el remainder sea ​​0 al final es esencialmente una forma de asegurar que todos los sufijos terminen en un nodo hoja. Sin embargo, si queremos usar el árbol para buscar subcadenas generales , no solo los sufijos de la cadena principal, este último paso no es necesario, como lo sugiere el comentario del OP a continuación.

• Entonces, ¿cuál es la complejidad de todo el algoritmo? Si el texto tiene una longitud de n caracteres, obviamente hay n pasos (o n + 1 si agregamos el signo de dólar). En cada paso no hacemos nada (aparte de actualizar las variables), o hacemos inserciones remainder , cada una de las cuales toma O (1). Como el remainder indica cuántas veces no hemos hecho nada en los pasos anteriores, y se reduce por cada inserción que hacemos ahora, el número total de veces que hacemos algo es exactamente n (o n + 1). Por lo tanto, la complejidad total es O (n).

• Sin embargo, hay una pequeña cosa que no expliqué adecuadamente: puede suceder que sigamos un enlace de sufijo, actualicemos el punto activo y luego encontremos que su componente active_length no funciona bien con el nuevo active_node . Por ejemplo, considere una situación como esta:

(Las líneas discontinuas indican el resto del árbol. La línea de puntos es un enlace de sufijo).

Ahora, deje que el punto activo sea (red,''d'',3) , por lo que apunta al lugar detrás de la f en el borde del borde. Ahora suponga que hicimos las actualizaciones necesarias y ahora siga el enlace del sufijo para actualizar el punto activo de acuerdo con la regla 3. El nuevo punto activo es (green,''d'',3) . Sin embargo, el d -edge que sale del nodo verde es de , por lo que solo tiene 2 caracteres. Para encontrar el punto activo correcto, obviamente debemos seguir ese borde hasta el nodo azul y restablecer a (blue,''f'',1) .

En un caso particularmente malo, active_length podría ser tan grande como el remainder , que puede ser tan grande como n. Y podría muy bien suceder que para encontrar el punto activo correcto, no solo necesitamos saltar sobre un nodo interno, sino quizás muchos, hasta n en el peor de los casos. ¿Eso significa que el algoritmo tiene una complejidad oculta de O (n ² ), porque en cada paso el remainder es generalmente O (n), y los ajustes posteriores al nodo activo después de seguir un enlace de sufijo también podrían ser O (n)?

No. El motivo es que si de hecho tenemos que ajustar el punto activo (p. Ej., De verde a azul, como se active_length anteriormente), eso nos lleva a un nuevo nodo que tiene su propio enlace de sufijo y se reducirá el valor de active_length . A medida que seguimos la cadena de enlaces de sufijos, hacemos las inserciones restantes, active_length solo puede disminuir, y la cantidad de ajustes de puntos activos que podemos hacer en el camino no puede ser mayor que active_length en un momento dado. Dado que active_length nunca puede ser más grande que el remainder , y el remainder es O (n) no solo en cada paso, sino que la suma total de los incrementos jamás realizados en el remainder a lo largo de todo el proceso es O (n) también, el número de Los ajustes de puntos activos también están limitados por O (n).

Answer 2

Gracias por el tutorial bien explicado de @jogojapan , implementé el algoritmo en Python.

Un par de problemas menores mencionados por @jogojapan resultan ser más sofisticados de lo que esperaba y necesitan ser tratados con mucho cuidado. Me costó varios días conseguir mi implementación lo suficientemente robusta (supongo). Los problemas y soluciones se enumeran a continuación:

1. Termine con el Remainder > 0 Resulta que esta situación también puede ocurrir durante el paso de despliegue , no solo el final de todo el algoritmo. Cuando eso sucede, podemos dejar el resto, actnode, actuado y actlength sin cambios , finalizar el paso de despliegue actual, y comenzar otro paso manteniendo el plegado o despliegue dependiendo de si el siguiente carácter en la cadena original está en la ruta actual o no.

2. Leap Over Nodes: cuando seguimos un enlace de sufijo, actualizamos el punto activo y luego encontramos que su componente active_length no funciona bien con el nuevo active_node. Tenemos que avanzar hacia el lugar correcto para dividir, o insertar una hoja. Es posible que este proceso no sea tan sencillo, ya que durante el movimiento la longitud de actividad y la actividad cambian continuamente, cuando tiene que regresar al nodo raíz , la acción y la longitud de acción podrían ser incorrectas debido a esos movimientos. Necesitamos variables adicionales para mantener esa información.

Los otros dos problemas han sido señalados de alguna manera por @managonov

3. La división podría degenerar Cuando se intenta dividir un borde, en algún momento encontrará que la operación de división está justo en un nodo. En ese caso, solo necesitamos agregar una nueva hoja a ese nodo, tómela como una operación de división de borde estándar, lo que significa que los enlaces de sufijo, si hay alguno, se deben mantener de manera correspondiente.

4. Enlaces de sufijo ocultos Hay otro caso especial en el que incurren el problema 1 y el problema 2 . A veces necesitamos saltar sobre varios nodos al punto correcto para dividir, podríamos superar el punto correcto si nos movemos comparando la cadena restante y las etiquetas de ruta. En ese caso, el enlace del sufijo se descuidará involuntariamente, si hubiera alguno. Esto podría evitarse recordando el punto correcto al avanzar. El enlace del sufijo debe mantenerse si el nodo dividido ya existe, o incluso el problema 1 ocurre durante un paso de despliegue.

Finalmente, mi implementación en Python es la siguiente:

• Python

Sugerencias: incluye una función de impresión de árbol ingenua en el código anterior, que es muy importante durante la depuración . Me ahorró mucho tiempo y es conveniente para localizar casos especiales.

Answer 3

Intenté implementar el Árbol de sufijos con el enfoque dado en la respuesta de jogojapan, pero no funcionó en algunos casos debido a la redacción utilizada para las reglas. Además, he mencionado que nadie logró implementar un árbol de sufijos absolutamente correcto utilizando este enfoque. A continuación escribiré una "descripción general" de la respuesta de jogojapan con algunas modificaciones a las reglas. También describiré el caso cuando olvidemos crear enlaces con sufijos importantes .

Variables adicionales utilizadas

1. punto activo : un triple (active_node; active_edge; active_length), que muestra desde donde debemos comenzar a insertar un nuevo sufijo.
2. resto : muestra el número de sufijos que debemos agregar explícitamente . Por ejemplo, si nuestra palabra es ''abcaabca'', y el resto = 3, significa que debemos procesar 3 últimos sufijos: bca , ca y a .

Usemos el concepto de un nodo interno : todos los nodos, excepto la raíz y las hojas son nodos internos .

Observación 1

Cuando se encuentre que el sufijo final que necesitamos insertar ya existe en el árbol, el árbol en sí no se modifica en absoluto (solo actualizamos el active point y el remainder ).

Observación 2

Si en algún punto active_length es mayor o igual a la longitud del borde actual ( edge_length ), movemos nuestro active point hacia abajo hasta que edge_length sea ​​estrictamente mayor que active_length .

Ahora, vamos a redefinir las reglas:

Regla 1

Si después de una inserción desde el nodo activo = raíz , la longitud activa es mayor que 0, entonces:

1. el nodo activo no se cambia
2. la longitud activa se decrementa
3. el borde activo se desplaza hacia la derecha (al primer carácter del siguiente sufijo que debemos insertar)

Regla 2

Si creamos un nuevo nodo interno O creamos un insertador desde un nodo interno , y este no es el primer nodo interno de TAL en el paso actual, entonces vinculamos el nodo TAL anterior con ESTE a través de un enlace de sufijo .

Esta definición de la Rule 2 es diferente de jogojapan '', ya que aquí tenemos en cuenta no solo los nodos internos recién creados , sino también los nodos internos, desde los cuales hacemos una inserción.

Regla 3

Después de una inserción desde el nodo activo que no es el nodo raíz , debemos seguir el enlace del sufijo y establecer el nodo activo en el nodo al que apunta. Si no hay un enlace de sufijo, establezca el nodo activo en el nodo raíz . De cualquier manera, el borde activo y la longitud activa permanecen sin cambios.

En esta definición de la Rule 3 también consideramos las inserciones de los nodos de hoja (no solo los nodos divididos).

Y finalmente, la Observación 3:

Cuando el símbolo que queremos agregar al árbol ya está en el borde, nosotros, de acuerdo con la Observation 1 , actualizamos solo active point y el remainder , sin modificar el árbol. PERO si hay un nodo interno marcado como que necesita enlace de sufijo , debemos conectar ese nodo con nuestro active node actual a través de un enlace de sufijo.

Veamos el ejemplo de un árbol de sufijos para cdddcdc si agregamos un enlace de sufijo en tal caso y si no lo hacemos:

1. Si NO conectamos los nodos a través de un enlace de sufijo:

   • Antes de agregar la última letra c :
   • después de agregar la última letra c :

2. Si conectamos los nodos a través de un enlace de sufijo:

   • Antes de agregar la última letra c :
   • después de agregar la última letra c :

Parece que no hay una diferencia significativa: en el segundo caso hay dos enlaces de sufijo más. Pero estos enlaces de sufijos son correctos , y uno de ellos, desde el nodo azul al rojo, es muy importante para nuestro enfoque con el punto activo . El problema es que si no ponemos un enlace de sufijo aquí, más adelante, cuando agreguemos algunas letras nuevas al árbol, podríamos omitir agregar algunos nodos al árbol debido a la Rule 3 , porque, según este, si hay no hay un enlace de sufijo, entonces debemos poner el active_node a la raíz.

Cuando estábamos agregando la última letra al árbol, el nodo rojo ya existía antes de que hiciéramos una inserción desde el nodo azul (el borde marcado como ''c'' ). Como había una inserción del nodo azul, lo marcamos como que necesita un enlace de sufijo . Luego, confiando en el enfoque de punto activo , el active node se estableció en el nodo rojo. Pero no hacemos una inserción desde el nodo rojo, ya que la letra ''c'' ya está en el borde. ¿Significa que el nodo azul debe quedar sin un enlace de sufijo? No, debemos conectar el nodo azul con el rojo a través de un enlace de sufijo. ¿Por qué es correcto? Debido a que el enfoque de punto activo garantiza que lleguemos al lugar correcto, es decir, al siguiente lugar donde debemos procesar una inserción de un sufijo más corto .

Finalmente, aquí están mis implementaciones del Árbol de Sufijo:

1. Java
2. C++

Espero que esta "visión general" combinada con la respuesta detallada de jogojapan ayude a alguien a implementar su propio árbol de sufijos.

Answer 4

Mi intuición es la siguiente:

Después de k iteraciones del bucle principal, ha construido un árbol de sufijos que contiene todos los sufijos de la cadena completa que comienzan en los primeros k caracteres.

Al principio, esto significa que el árbol de sufijos contiene un solo nodo raíz que representa la cadena completa (este es el único sufijo que comienza en 0).

Después de las iteraciones len (cadena), tiene un árbol de sufijos que contiene todos los sufijos.

Durante el bucle la clave es el punto activo. Supongo que esto representa el punto más profundo en el árbol de sufijos que corresponde a un sufijo adecuado de los primeros k caracteres de la cadena. (Creo que correcto significa que el sufijo no puede ser la cadena completa).

Por ejemplo, supongamos que has visto los caracteres ''abcabc''. El punto activo representaría el punto en el árbol correspondiente al sufijo ''abc''.

El punto activo está representado por (origen, primero, último). Esto significa que se encuentra actualmente en el punto del árbol al que comienza al iniciar el origen del nodo y luego ingresando los caracteres en la cadena [primero: último]

Cuando agrega un nuevo carácter, observa si el punto activo todavía está en el árbol existente. Si es así, has terminado. De lo contrario, debe agregar un nuevo nodo al árbol de sufijos en el punto activo, retroceder a la siguiente coincidencia más corta y volver a verificar.

Nota 1: Los punteros de sufijo proporcionan un enlace a la siguiente coincidencia más corta para cada nodo.

Nota 2: cuando agrega un nuevo nodo y retrocede, agrega un nuevo puntero de sufijo para el nuevo nodo. El destino para este puntero de sufijo será el nodo en el punto activo acortado. Este nodo ya existirá o se creará en la próxima iteración de este bucle de reserva.

Nota 3: La parte de canonización simplemente ahorra tiempo al verificar el punto activo. Por ejemplo, supongamos que siempre ha utilizado origin = 0 y que acaba de cambiar primero y último. Para verificar el punto activo, tendría que seguir el árbol de sufijos cada vez a lo largo de todos los nodos intermedios. Tiene sentido almacenar en caché el resultado de seguir esta ruta al registrar solo la distancia desde el último nodo.

¿Puede dar un ejemplo de código de lo que quiere decir con "arreglar" las variables de límite?

Advertencia de salud: también encontré este algoritmo particularmente difícil de entender, así que tenga en cuenta que es probable que esta intuición sea incorrecta en todos los detalles importantes ...

Answer 5

@jogojapan trajiste asombrosa explicación y visualización. Pero, como mencionó @makagonov, faltan algunas reglas con respecto a la configuración de enlaces de sufijo. Es visible de una manera agradable al pasar paso a paso en http://brenden.github.io/ukkonen-animation/ través de la palabra ''aabaaabb''. Cuando se pasa del paso 10 al paso 11, no hay un vínculo de sufijo del nodo 5 al nodo 2, pero el punto activo se mueve de repente allí.

@makagonov ya que vivo en el mundo de Java, también intenté seguir su implementación para comprender el flujo de trabajo de construcción de ST, pero fue difícil para mí debido a:

• combinando aristas con nodos
• utilizando punteros de índice en lugar de referencias
• rompe declaraciones;
• continuar las declaraciones;

Así que terminé con una implementación en Java que espero que refleje todos los pasos de manera más clara y reduzca el tiempo de aprendizaje para otras personas de Java:

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
public class ST {
public class Node {
private final int id;
private final Map<Character, Edge> edges;
private Node slink;
public Node(final int id) {
this.id = id;
this.edges = new HashMap<>();
}
public void setSlink(final Node slink) {
this.slink = slink;
}
public Map<Character, Edge> getEdges() {
return this.edges;
}
public Node getSlink() {
return this.slink;
}
public String toString(final String word) {
return new StringBuilder()
.append("{")
.append("/"id/"")
.append(":")
.append(this.id)
.append(",")
.append("/"slink/"")
.append(":")
.append(this.slink != null ? this.slink.id : null)
.append(",")
.append("/"edges/"")
.append(":")
.append(edgesToString(word))
.append("}")
.toString();
}
private StringBuilder edgesToString(final String word) {
final StringBuilder edgesStringBuilder = new StringBuilder();
edgesStringBuilder.append("{");
for(final Map.Entry<Character, Edge> entry : this.edges.entrySet()) {
edgesStringBuilder.append("/"")
.append(entry.getKey())
.append("/"")
.append(":")
.append(entry.getValue().toString(word))
.append(",");
}
if(!this.edges.isEmpty()) {
edgesStringBuilder.deleteCharAt(edgesStringBuilder.length() - 1);
}
edgesStringBuilder.append("}");
return edgesStringBuilder;
}
public boolean contains(final String word, final String suffix) {
return !suffix.isEmpty()
&& this.edges.containsKey(suffix.charAt(0))
&& this.edges.get(suffix.charAt(0)).contains(word, suffix);
}
}
public class Edge {
private final int from;
private final int to;
private final Node next;
public Edge(final int from, final int to, final Node next) {
this.from = from;
this.to = to;
this.next = next;
}
public int getFrom() {
return this.from;
}
public int getTo() {
return this.to;
}
public Node getNext() {
return this.next;
}
public int getLength() {
return this.to - this.from;
}
public String toString(final String word) {
return new StringBuilder()
.append("{")
.append("/"content/"")
.append(":")
.append("/"")
.append(word.substring(this.from, this.to))
.append("/"")
.append(",")
.append("/"next/"")
.append(":")
.append(this.next != null ? this.next.toString(word) : null)
.append("}")
.toString();
}
public boolean contains(final String word, final String suffix) {
if(this.next == null) {
return word.substring(this.from, this.to).equals(suffix);
}
return suffix.startsWith(word.substring(this.from,
this.to)) && this.next.contains(word, suffix.substring(this.to - this.from));
}
}
public class ActivePoint {
private final Node activeNode;
private final Character activeEdgeFirstCharacter;
private final int activeLength;
public ActivePoint(final Node activeNode,
final Character activeEdgeFirstCharacter,
final int activeLength) {
this.activeNode = activeNode;
this.activeEdgeFirstCharacter = activeEdgeFirstCharacter;
this.activeLength = activeLength;
}
private Edge getActiveEdge() {
return this.activeNode.getEdges().get(this.activeEdgeFirstCharacter);
}
public boolean pointsToActiveNode() {
return this.activeLength == 0;
}
public boolean activeNodeIs(final Node node) {
return this.activeNode == node;
}
public boolean activeNodeHasEdgeStartingWith(final char character) {
return this.activeNode.getEdges().containsKey(character);
}
public boolean activeNodeHasSlink() {
return this.activeNode.getSlink() != null;
}
public boolean pointsToOnActiveEdge(final String word, final char character) {
return word.charAt(this.getActiveEdge().getFrom() + this.activeLength) == character;
}
public boolean pointsToTheEndOfActiveEdge() {
return this.getActiveEdge().getLength() == this.activeLength;
}
public boolean pointsAfterTheEndOfActiveEdge() {
return this.getActiveEdge().getLength() < this.activeLength;
}
public ActivePoint moveToEdgeStartingWithAndByOne(final char character) {
return new ActivePoint(this.activeNode, character, 1);
}
public ActivePoint moveToNextNodeOfActiveEdge() {
return new ActivePoint(this.getActiveEdge().getNext(), null, 0);
}
public ActivePoint moveToSlink() {
return new ActivePoint(this.activeNode.getSlink(),
this.activeEdgeFirstCharacter,
this.activeLength);
}
public ActivePoint moveTo(final Node node) {
return new ActivePoint(node, this.activeEdgeFirstCharacter, this.activeLength);
}
public ActivePoint moveByOneCharacter() {
return new ActivePoint(this.activeNode,
this.activeEdgeFirstCharacter,
this.activeLength + 1);
}
public ActivePoint moveToEdgeStartingWithAndByActiveLengthMinusOne(final Node node,
final char character) {
return new ActivePoint(node, character, this.activeLength - 1);
}
public ActivePoint moveToNextNodeOfActiveEdge(final String word, final int index) {
return new ActivePoint(this.getActiveEdge().getNext(),
word.charAt(index - this.activeLength + this.getActiveEdge().getLength()),
this.activeLength - this.getActiveEdge().getLength());
}
public void addEdgeToActiveNode(final char character, final Edge edge) {
this.activeNode.getEdges().put(character, edge);
}
public void splitActiveEdge(final String word,
final Node nodeToAdd,
final int index,
final char character) {
final Edge activeEdgeToSplit = this.getActiveEdge();
final Edge splittedEdge = new Edge(activeEdgeToSplit.getFrom(),
activeEdgeToSplit.getFrom() + this.activeLength,
nodeToAdd);
nodeToAdd.getEdges().put(word.charAt(activeEdgeToSplit.getFrom() + this.activeLength),
new Edge(activeEdgeToSplit.getFrom() + this.activeLength,
activeEdgeToSplit.getTo(),
activeEdgeToSplit.getNext()));
nodeToAdd.getEdges().put(character, new Edge(index, word.length(), null));
this.activeNode.getEdges().put(this.activeEdgeFirstCharacter, splittedEdge);
}
public Node setSlinkTo(final Node previouslyAddedNodeOrAddedEdgeNode,
final Node node) {
if(previouslyAddedNodeOrAddedEdgeNode != null) {
previouslyAddedNodeOrAddedEdgeNode.setSlink(node);
}
return node;
}
public Node setSlinkToActiveNode(final Node previouslyAddedNodeOrAddedEdgeNode) {
return setSlinkTo(previouslyAddedNodeOrAddedEdgeNode, this.activeNode);
}
}
private static int idGenerator;
private final String word;
private final Node root;
private ActivePoint activePoint;
private int remainder;
public ST(final String word) {
this.word = word;
this.root = new Node(idGenerator++);
this.activePoint = new ActivePoint(this.root, null, 0);
this.remainder = 0;
build();
}
private void build() {
for(int i = 0; i < this.word.length(); i++) {
add(i, this.word.charAt(i));
}
}
private void add(final int index, final char character) {
this.remainder++;
boolean characterFoundInTheTree = false;
Node previouslyAddedNodeOrAddedEdgeNode = null;
while(!characterFoundInTheTree && this.remainder > 0) {
if(this.activePoint.pointsToActiveNode()) {
if(this.activePoint.activeNodeHasEdgeStartingWith(character)) {
activeNodeHasEdgeStartingWithCharacter(character, previouslyAddedNodeOrAddedEdgeNode);
characterFoundInTheTree = true;
}
else {
if(this.activePoint.activeNodeIs(this.root)) {
rootNodeHasNotEdgeStartingWithCharacter(index, character);
}
else {
previouslyAddedNodeOrAddedEdgeNode = internalNodeHasNotEdgeStartingWithCharacter(index,
character, previouslyAddedNodeOrAddedEdgeNode);
}
}
}
else {
if(this.activePoint.pointsToOnActiveEdge(this.word, character)) {
activeEdgeHasCharacter();
characterFoundInTheTree = true;
}
else {
if(this.activePoint.activeNodeIs(this.root)) {
previouslyAddedNodeOrAddedEdgeNode = edgeFromRootNodeHasNotCharacter(index,
character,
previouslyAddedNodeOrAddedEdgeNode);
}
else {
previouslyAddedNodeOrAddedEdgeNode = edgeFromInternalNodeHasNotCharacter(index,
character,
previouslyAddedNodeOrAddedEdgeNode);
}
}
}
}
}
private void activeNodeHasEdgeStartingWithCharacter(final char character,
final Node previouslyAddedNodeOrAddedEdgeNode) {
this.activePoint.setSlinkToActiveNode(previouslyAddedNodeOrAddedEdgeNode);
this.activePoint = this.activePoint.moveToEdgeStartingWithAndByOne(character);
if(this.activePoint.pointsToTheEndOfActiveEdge()) {
this.activePoint = this.activePoint.moveToNextNodeOfActiveEdge();
}
}
private void rootNodeHasNotEdgeStartingWithCharacter(final int index, final char character) {
this.activePoint.addEdgeToActiveNode(character, new Edge(index, this.word.length(), null));
this.activePoint = this.activePoint.moveTo(this.root);
this.remainder--;
assert this.remainder == 0;
}
private Node internalNodeHasNotEdgeStartingWithCharacter(final int index,
final char character,
Node previouslyAddedNodeOrAddedEdgeNode) {
this.activePoint.addEdgeToActiveNode(character, new Edge(index, this.word.length(), null));
previouslyAddedNodeOrAddedEdgeNode = this.activePoint.setSlinkToActiveNode(previouslyAddedNodeOrAddedEdgeNode);
if(this.activePoint.activeNodeHasSlink()) {
this.activePoint = this.activePoint.moveToSlink();
}
else {
this.activePoint = this.activePoint.moveTo(this.root);
}
this.remainder--;
return previouslyAddedNodeOrAddedEdgeNode;
}
private void activeEdgeHasCharacter() {
this.activePoint = this.activePoint.moveByOneCharacter();
if(this.activePoint.pointsToTheEndOfActiveEdge()) {
this.activePoint = this.activePoint.moveToNextNodeOfActiveEdge();
}
}
private Node edgeFromRootNodeHasNotCharacter(final int index,
final char character,
Node previouslyAddedNodeOrAddedEdgeNode) {
final Node newNode = new Node(idGenerator++);
this.activePoint.splitActiveEdge(this.word, newNode, index, character);
previouslyAddedNodeOrAddedEdgeNode = this.activePoint.setSlinkTo(previouslyAddedNodeOrAddedEdgeNode, newNode);
this.activePoint = this.activePoint.moveToEdgeStartingWithAndByActiveLengthMinusOne(this.root,
this.word.charAt(index - this.remainder + 2));
this.activePoint = walkDown(index);
this.remainder--;
return previouslyAddedNodeOrAddedEdgeNode;
}
private Node edgeFromInternalNodeHasNotCharacter(final int index,
final char character,
Node previouslyAddedNodeOrAddedEdgeNode) {
final Node newNode = new Node(idGenerator++);
this.activePoint.splitActiveEdge(this.word, newNode, index, character);
previouslyAddedNodeOrAddedEdgeNode = this.activePoint.setSlinkTo(previouslyAddedNodeOrAddedEdgeNode, newNode);
if(this.activePoint.activeNodeHasSlink()) {
this.activePoint = this.activePoint.moveToSlink();
}
else {
this.activePoint = this.activePoint.moveTo(this.root);
}
this.activePoint = walkDown(index);
this.remainder--;
return previouslyAddedNodeOrAddedEdgeNode;
}
private ActivePoint walkDown(final int index) {
while(!this.activePoint.pointsToActiveNode()
&& (this.activePoint.pointsToTheEndOfActiveEdge() || this.activePoint.pointsAfterTheEndOfActiveEdge())) {
if(this.activePoint.pointsAfterTheEndOfActiveEdge()) {
this.activePoint = this.activePoint.moveToNextNodeOfActiveEdge(this.word, index);
}
else {
this.activePoint = this.activePoint.moveToNextNodeOfActiveEdge();
}
}
return this.activePoint;
}
public String toString(final String word) {
return this.root.toString(word);
}
public boolean contains(final String suffix) {
return this.root.contains(this.word, suffix);
}
public static void main(final String[] args) {
final String[] words = {
"abcabcabc$",
"abc$",
"abcabxabcd$",
"abcabxabda$",
"abcabxad$",
"aabaaabb$",
"aababcabcd$",
"ababcabcd$",
"abccba$",
"mississipi$",
"abacabadabacabae$",
"abcabcd$",
"00132220$"
};
Arrays.stream(words).forEach(word -> {
System.out.println("Building suffix tree for word: " + word);
final ST suffixTree = new ST(word);
System.out.println("Suffix tree: " + suffixTree.toString(word));
for(int i = 0; i < word.length() - 1; i++) {
assert suffixTree.contains(word.substring(i)) : word.substring(i);
}
});
}
}

Answer 6

Hola, he intentado implementar la implementación explicada anteriormente en Ruby, por favor, compruebe. Parece que funciona bien.

la única diferencia en la implementación es que, he tratado de usar el objeto de borde en lugar de usar solo símbolos.

también está presente en https://gist.github.com/suchitpuri/9304856

 require ''pry''
class Edge
attr_accessor :data , :edges , :suffix_link
def initialize data
@data = data
@edges = []
@suffix_link = nil
end
def find_edge element
self.edges.each do |edge|
return edge if edge.data.start_with? element
end
return nil
end
end
class SuffixTrees
attr_accessor :root , :active_point , :remainder , :pending_prefixes , :last_split_edge , :remainder
def initialize
@root = Edge.new nil
@active_point = { active_node: @root , active_edge: nil , active_length: 0}
@remainder = 0
@pending_prefixes = []
@last_split_edge = nil
@remainder = 1
end
def build string
string.split("").each_with_index do |element , index|
add_to_edges @root , element
update_pending_prefix element
add_pending_elements_to_tree element
active_length = @active_point[:active_length]
# if(@active_point[:active_edge] && @active_point[:active_edge].data && @active_point[:active_edge].data[0..active_length-1] == @active_point[:active_edge].data[active_length..@active_point[:active_edge].data.length-1])
# @active_point[:active_edge].data = @active_point[:active_edge].data[0..active_length-1]
# @active_point[:active_edge].edges << Edge.new(@active_point[:active_edge].data)
# end
if(@active_point[:active_edge] && @active_point[:active_edge].data && @active_point[:active_edge].data.length == @active_point[:active_length] )
@active_point[:active_node] = @active_point[:active_edge]
@active_point[:active_edge] = @active_point[:active_node].find_edge(element[0])
@active_point[:active_length] = 0
end
end
end
def add_pending_elements_to_tree element
to_be_deleted = []
update_active_length = false
# binding.pry
if( @active_point[:active_node].find_edge(element[0]) != nil)
@active_point[:active_length] = @active_point[:active_length] + 1
@active_point[:active_edge] = @active_point[:active_node].find_edge(element[0]) if @active_point[:active_edge] == nil
@remainder = @remainder + 1
return
end
@pending_prefixes.each_with_index do |pending_prefix , index|
# binding.pry
if @active_point[:active_edge] == nil and @active_point[:active_node].find_edge(element[0]) == nil
@active_point[:active_node].edges << Edge.new(element)
else
@active_point[:active_edge] = node.find_edge(element[0]) if @active_point[:active_edge] == nil
data = @active_point[:active_edge].data
data = data.split("")
location = @active_point[:active_length]
# binding.pry
if(data[0..location].join == pending_prefix or @active_point[:active_node].find_edge(element) != nil )
else #tree split
split_edge data , index , element
end
end
end
end
def update_pending_prefix element
if @active_point[:active_edge] == nil
@pending_prefixes = [element]
return
end
@pending_prefixes = []
length = @active_point[:active_edge].data.length
data = @active_point[:active_edge].data
@remainder.times do |ctr|
@pending_prefixes << data[-(ctr+1)..data.length-1]
end
@pending_prefixes.reverse!
end
def split_edge data , index , element
location = @active_point[:active_length]
old_edges = []
internal_node = (@active_point[:active_edge].edges != nil)
if (internal_node)
old_edges = @active_point[:active_edge].edges
@active_point[:active_edge].edges = []
end
@active_point[:active_edge].data = data[0..location-1].join
@active_point[:active_edge].edges << Edge.new(data[location..data.size].join)
if internal_node
@active_point[:active_edge].edges << Edge.new(element)
else
@active_point[:active_edge].edges << Edge.new(data.last)
end
if internal_node
@active_point[:active_edge].edges[0].edges = old_edges
end
#setup the suffix link
if @last_split_edge != nil and @last_split_edge.data.end_with?@active_point[:active_edge].data
@last_split_edge.suffix_link = @active_point[:active_edge]
end
@last_split_edge = @active_point[:active_edge]
update_active_point index
end
def update_active_point index
if(@active_point[:active_node] == @root)
@active_point[:active_length] = @active_point[:active_length] - 1
@remainder = @remainder - 1
@active_point[:active_edge] = @active_point[:active_node].find_edge(@pending_prefixes.first[index+1])
else
if @active_point[:active_node].suffix_link != nil
@active_point[:active_node] = @active_point[:active_node].suffix_link
else
@active_point[:active_node] = @root
end
@active_point[:active_edge] = @active_point[:active_node].find_edge(@active_point[:active_edge].data[0])
@remainder = @remainder - 1
end
end
def add_to_edges root , element
return if root == nil
root.data = root.data + element if(root.data and root.edges.size == 0)
root.edges.each do |edge|
add_to_edges edge , element
end
end
end
suffix_tree = SuffixTrees.new
suffix_tree.build("abcabxabcd")
binding.pry