javascript - Algoritmo del árbol de sufijos de Ukkonen en inglés sencillo


Me siento un poco grueso en este punto. He pasado varios días tratando de entender completamente la construcción del árbol de sufijos, pero debido a que no tengo conocimientos matemáticos, muchas de las explicaciones me eluden cuando empiezan a hacer un uso excesivo de la simbología matemática. Lo más parecido a una buena explicación que he encontrado es Fast String Searching With Suffix Trees , pero 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 sería invaluable para muchos otros además de mí, estoy seguro.

Como 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 iterar a través de cada prefijo P de una cadena dada T
  • Necesito iterar a través de cada sufijo S en el prefijo P y agregar eso al árbol
  • Para agregar el sufijo S al árbol, necesito iterar a través de 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 descendientes cuando 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 2 ), como se señala en la mayoría de las explicaciones, ya que necesitamos pasar por todos los prefijos, luego tenemos que pasar por cada sufijo para cada prefijo. El algoritmo de Ukkonen es aparentemente único debido a la técnica de puntero de sufijo que usa, aunque creo que eso es lo que tengo problemas para entender.

También estoy teniendo problemas para entender:

  • exactamente cuándo y cómo se asigna, usa y cambia el "punto activo"
  • qué está pasando con el aspecto de canonización del algoritmo
  • Por qué las implementaciones que he visto necesitan para "arreglar" las variables de delimitación que están utilizando

Aquí está el código fuente completo de C # . 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 de la salida. El código fuente y el resultado de la 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 árboles de sufijos y he implementado el algoritmo en JavaScript . Gist está abajo. Debería estar libre de errores. Viértalo en un archivo js, npm install chalk en la misma ubicación y luego ejecútelo con node.js para ver 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



Answers


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 lo extiende al algoritmo completo.

Primero, unas pocas declaraciones preliminares.

  1. Lo que estamos construyendo es básicamente como un trie de búsqueda. Entonces, hay un nodo raíz, los bordes que salen de él conducen a nuevos nodos y otros bordes que salen de ellos, y así sucesivamente

  2. Pero : a diferencia de un trie de búsqueda, las etiquetas de borde no son caracteres únicos. En cambio, cada borde está etiquetado con 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 toma solo O (1) espacio (dos punteros).

Principio básico

Me gustaría primero demostrar cómo crear el árbol de sufijo 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 personaje de la cadena . Cada paso puede implicar 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).

Entonces, comenzamos desde la izquierda , y primero insertamos solo el caracter 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 referirme al final actual , que está en la posición 1 (justo después de a ).

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

Y lo que significa es esto:

Ahora pasamos 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 la -edge existente a ab
  • insertando un nuevo borde para b

En nuestra representación, esto parece

Y lo que significa es:

Observamos dos cosas:

  • La representación del borde para ab es la misma que solía ser en el árbol inicial: [0,#] . Su significado ha cambiado automáticamente porque actualizamos la posición actual # de 1 a 2.
  • Cada borde consume O (1) espacio, 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 nuevo borde para el nuevo sufijo c .

En nuestra representación, esto parece

Y lo que significa es:

Observamos:

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

Primera extensión: repeticiones simples

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

abcabxabcd

Comienza con abc como en el ejemplo anterior, luego ab se repite y seguido por 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, presentamos dos variables más (además de # ), que por supuesto han estado ahí 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 era (root,'\0x',0) , es decir, active_node era el nodo raíz, active_edge se especificaba 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 era que el número de sufijos que teníamos que insertar activamente al final de cada paso era 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 . Esto 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 el medio de un borde más largo, pero no nos molesta eso. Simplemente dejamos las cosas como están.
  • Establecemos el punto activo en (root,'a',1) . Eso significa que el punto activo está ahora en algún lugar en el medio del borde saliente del nodo raíz que comienza con, específicamente, después de la posición 1 en ese borde. Observamos que el borde se especifica 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 ya se encontró que el sufijo final que necesitamos insertar ya existe en el árbol , el árbol en sí no se cambia 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, además de actualizar las variables (que son todas de longitud fija, entonces esto es O (1)), no se hizo 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 se ha mantenido , y dado que hemos progresado 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 detrás de la a en lo que ahora es el borde abcab ) e insertamos el carácter final actual b . Pero: una vez más, resulta que b también está presente en ese mismo borde.

Entonces, nuevamente, no cambiamos el árbol. Nosotros simplemente:

  • Actualice el punto activo a (root,'a',2) (mismo nodo y borde que antes, pero ahora señalamos detrás de b )
  • Incremente el remainder a 3 porque aún 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 ab ya se encontró, actualizamos el punto activo y ni siquiera intentamos insertar b . ¿Por qué? Porque si ab está en el árbol, cada sufijo del mismo (incluido b ) también debe estar en el árbol. Tal vez solo implícitamente , 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 , debemos insertar abx , bx y x . El punto activo nos dice dónde termina ab , por lo que solo tenemos que saltar 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 los bordes siguen siendo punteros en el texto, por lo que se puede dividir e insertar un nodo interno en el tiempo O (1).

Así que hemos tratado con abx y el remainder decremento en 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 sigue siendo 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 punto activo triple (root,'b',1) indica que la siguiente inserción debe hacerse en el borde bcabx , detrás de 1 carácter, es decir, detrás de b . Podemos identificar el punto de inserción en el 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, entonces lo insertamos dividiendo el borde:

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

Pero hay una cosa más que debemos hacer. Llamaremos a esta 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. Esto es lo que obtenemos, el sufijo link se representa como un borde punteado:

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

Como podemos ver, en el paso actual se hicieron todos los insertos restantes.

Continuamos con el paso 7 configurando # = 7, que automáticamente agrega 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 descubrimos que ya está allí. Así que finalizamos 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) e incrementamos el remainder sin hacer nada más, porque b ya está presente. Sin embargo, notamos (en O (1) tiempo) que el punto activo está ahora al final de un borde. Reflejamos esto volviendo a establecerlo 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: usar enlaces de sufijos

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 de 3 pasos atrás) insertando d en el punto activo.

Intentar insertar d en el punto activo provoca una división de bordes en O (1) tiempo:

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 hay alguno, y reiniciamos el nodo active_node al nodo al que apunta. Si no hay un 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:

Dado que 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 justo en el nodo derecho y en el borde, por lo 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 bordes, y debido a la regla 2 , debemos crear un enlace de sufijo desde el nodo previamente insertado al nuevo:

Observamos: los enlaces de sufijo nos permiten restablecer el punto activo para que podamos hacer la siguiente inserción restante en O (1) esfuerzo. Mire el gráfico anterior para confirmar que, de hecho, 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 no ha terminado aún. remainder ahora es 2, y debemos seguir la regla 3 para restablecer el punto activo nuevamente. Como el actual active_node (rojo arriba) no tiene un sufijo, lo restablecemos a root. 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 dado que 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 dot reorganizara los bordes existentes, así que revise cuidadosamente para confirmar que lo único que se insertó arriba es un nuevo enlace de sufijo).

Con esto, el remainder se puede establecer en 1 y dado que el active_node es la raíz, 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 única d en la raíz:

Ese fue el último paso y hemos terminado. Sin embargo, hay varias observaciones finales :

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

  • Pero no trata con a) los sufijos restantes de los pasos anteriores, y b) con el último carácter del paso actual.

  • remainder nos dice cuántos insertos adicionales tenemos que hacer. Estas inserciones corresponden uno a uno a los sufijos finales de la cadena que termina en la posición actual # . Consideramos uno después del otro y hacemos el inserto. Importante: cada inserción se realiza en O (1) vez, ya que el punto activo nos dice exactamente dónde ir, y necesitamos agregar solo 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, disminuimos el remainder y seguimos el vínculo 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 usando la regla 1. En cualquier caso, solo toma O (1) vez.

  • 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 las inserciones que queden serán sufijos del que acabamos de intentar. Por lo tanto, están todos implícitos en el árbol actual. El hecho de que remainder > 0 nos asegure que tratemos con los sufijos restantes más tarde.

  • ¿Qué pasa si al final del algoritmo remainder > 0? Este será el caso siempre que el final del texto sea una subcadena que haya ocurrido en algún lugar anteriormente. En ese caso, debemos agregar un carácter adicional al final de la cadena que no haya ocurrido antes. En la literatura, generalmente el signo de dólar $ se usa como un símbolo para eso. ¿Por que importa? -> Si más adelante usamos el árbol de sufijos completado para buscar sufijos, debemos aceptar coincidencias solo si terminan en una hoja . De lo contrario, obtendríamos muchas coincidencias falsas, ya que hay muchas cadenas implícitas 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 garantizar que todos los sufijos terminen en un nodo hoja. Sin embargo, si queremos usar el árbol para buscar subcadenas generales , no solo sufijos de la cadena principal, este paso final no es necesario, tal como lo sugiere el comentario de OP a continuación.

  • Entonces, ¿cuál es la complejidad de todo el algoritmo? Si el texto tiene n caracteres de longitud, obviamente hay n pasos (o n + 1 si agregamos el signo de dólar). En cada paso, no hacemos nada (salvo actualizar las variables), o hacemos insertos de remainder , cada uno teniendo O (1) vez. Como el remainder indica cuántas veces no hemos hecho nada en los pasos anteriores, y se reduce para cada inserción que hagamos 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 he explicado correctamente: puede suceder que sigamos un enlace de sufijo, actualicemos el punto activo y luego descubramos 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 f en el borde defg . Ahora supongamos que realizamos las actualizaciones necesarias y ahora seguimos 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, la d -edge que sale del nodo verde es de , por lo que tiene solo 2 caracteres. Para encontrar el punto activo correcto, obviamente necesitamos seguir ese borde hasta el nodo azul y restablecerlo 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 suceder que para encontrar el punto activo correcto, no solo tengamos que 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 O (n 2 ) oculta, porque en cada paso el remainder generalmente es 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. La razón es que, si realmente tenemos que ajustar el punto activo (por ejemplo, de verde a azul como se active_length anteriormente), eso nos lleva a un nuevo nodo que tiene su propio enlace de sufijo, y active_length se reducirá. A medida que seguimos por la cadena de enlaces de sufijo hacemos las inserciones restantes, active_length solo puede disminuir, y la cantidad de ajustes de punto activo que podemos hacer en el camino no puede ser mayor que active_length en un momento dado. Dado que active_length nunca puede ser mayor que el remainder , y el remainder es O (n) no solo en cada paso, sino que la suma total de incrementos que se han hecho en el remainder del proceso es O (n) también, el número de los ajustes activos del punto también están limitados por O (n).




Traté de implementar el Suffix Tree 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 usando este enfoque. A continuación escribiré un "resumen" de la respuesta de jogojapan con algunas modificaciones a las reglas. También describiré el caso cuando olvidemos crear enlaces de sufijo 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 remainder = 3, significa que debemos procesar 3 últimos sufijos: bca , ca y a .

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

Observación 1

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

Observación 2

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

Ahora, redefinamos las reglas:

Regla 1

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

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

Regla 2

Si creamos un nuevo nodo interno O hacemos un insertador desde un nodo interno , y este no es el primer nodo interno TAL en el paso actual, entonces vinculamos el anterior SUCHO con ESTO 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 al nodo al que apunta. Si no hay un enlace de sufijo, configure el nodo activo en el nodo raíz . De cualquier forma, el borde activo y la longitud activa permanecen sin cambios.

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

Y finalmente, 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 un enlace de sufijo , debemos conectar ese nodo con nuestro active node actual a través de un enlace de sufijo.

Miremos el ejemplo de un árbol de sufijo 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 HACEMOS conectar 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 sufijo son correctos , y uno de ellos, desde el nodo azul hasta el 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, de acuerdo con ella, si hay no hay un sufijo, entonces debemos poner el active_node en 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 etiquetado como 'c' ). Como había un inserto del nodo azul, lo marcamos como necesitar un enlace de sufijo . Luego, dependiendo del enfoque del 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 sufijo? No, debemos conectar el nodo azul con el rojo a través de un enlace de sufijo. ¿Por qué es correcto? Porque el enfoque de punto activo garantiza que lleguemos a un lugar correcto, es decir, al siguiente lugar donde debemos procesar un inserto de un sufijo más corto .

Finalmente, aquí están mis implementaciones del Suffix Tree:

  1. Java
  2. C ++

Espero que este "resumen" combinado con la respuesta detallada de jogojapan ayude a alguien a implementar su propio Árbol de sufijos.




He tenido bastantes problemas para implementar esta estructura de datos yo mismo. Al final encontré este artículo y logré implementarlo. Una gran ventaja es que tienes un ejemplo paso a paso de una secuencia bastante larga para que puedas ver lo que debes hacer. Por favor, eche un vistazo al artículo y estaré más que feliz de dar consejos cuando sea necesario. Dudo en dar otra explicación completa, ya que hay bastantes por Internet.




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 único nodo raíz que representa la cadena completa (este es el único sufijo que comienza en 0).

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

Durante el ciclo, 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 apropiado de los primeros k caracteres de la cadena. (Creo que correcto significa que el sufijo no puede ser toda la cadena).

Por ejemplo, supongamos que ha visto 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 en el árbol al que se llega comenzando en el origen del nodo y luego introduciendo los caracteres en la cadena [first: last]

Cuando agrega un nuevo personaje, busca ver 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 verificar nuevamente.

Nota 1: los punteros de los sufijos dan un enlace a la siguiente coincidencia más corta para cada nodo.

Nota 2: cuando agrega un nuevo nodo y repliegue, 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 siguiente iteración de este ciclo de retorno.

Nota 3: La parte de canonización simplemente ahorra tiempo al verificar el punto activo. Por ejemplo, supongamos que siempre utilizaste origen = 0, y acabas de cambiar primero y último. Para verificar el punto activo, debe 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 registrando solo la distancia desde el último nodo.

¿Puedes dar un ejemplo de código de lo que quieres decir con variables de límite "corregir"?

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




Gracias por el tutorial bien explicado por @jogojapan , he implementado el algoritmo en Python.

Un par de pequeños problemas mencionados por @jogojapan resulta ser más sofisticada de lo que hubiera esperado, y necesitan ser tratados con mucho cuidado. Me costó varios días para conseguir mi aplicación lo suficientemente robusta (supongo). Los problemas y las soluciones se enumeran a continuación:

  1. Termina conRemainder > 0 Resulta que esta situación también puede ocurrir durante la fase de despliegue , no sólo el final de todo el algoritmo. Cuando eso sucede, podemos dejar el resto, actnode, actedge y actlength sin cambios , poner fin a la etapa de despliegue actual, y empezar un nuevo paso por entre Conservar el plegado o desplegado dependiendo de si el siguiente caracter en la cadena original se encuentra en la ruta actual o no.

  2. Saltar por encima de nodos: Cuando seguimos un enlace sufijo, actualizar el punto activo, y luego encontrar que su componente active_length no funciona bien con la nueva active_node. Tenemos que avanzar en el lugar adecuado para dividir, o insertar una hoja. Este proceso podría ser no tan sencillo , porque durante el movimiento del actlength y actedge seguir cambiando todo el camino, cuando se tiene que mover de nuevo al nodo raíz , el actedge y actlength podría ser incorrecta debido a esos movimientos. Necesitamos variable (s) adicional para mantener esa información.

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

  1. Dividir podría degenerar Al tratar de dividir un borde, en algún momento encontrará la operación de división está justo en un nodo. Ese caso sólo necesitamos agregar una nueva hoja a ese nodo, tomarlo como una operación de división borde estándar, lo que significa que los enlaces sufijo si hay alguna, debe mantenerse correspondientemente.

  2. El sufijo oculto Enlaces Hay otro caso especial que se realicen por el problema 1 y el problema 2 . A veces tenemos que saltar sobre varios nodos hasta el punto correcto para dividir, podríamos superar el punto correcto si nos movemos por comparación de la secuencia restante y las etiquetas de ruta. Ese caso el enlace sufijo se descuida sin querer, si hubiera alguna. Esto podría evitarse por recordar el punto justo cuando se mueve hacia adelante. El enlace sufijo debe mantenerse si el nodo de división ya existe, o incluso el problema 1 sucede durante una etapa de desplegamiento.

Por último, mi implementación en Python es como sigue:

Consejos: Incluye una ingenua impresión árbol de la función en el código anterior, que es muy importante durante la depuración . Me salvó un montón de tiempo y es conveniente para la localización de casos especiales.




Hola yo he tratado de implementar la aplicación anterior se explica en rubí, por favor, comprobar que funciona. Parece que funciona bien.

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

su también 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



@jogojapan que trajo explicación impresionante y visualización. Pero a medida que @makagonov indican que faltan algunas reglas con respecto a establecer vínculos de sufijo. Es visible en buena forma al ir paso a paso en http://brenden.github.io/ukkonen-animation/ través de la palabra 'aabaaabb'. Cuando vaya desde el paso 10 al paso 11, no existe un vínculo sufijo del nodo 5 al nodo 2, pero el punto activo de repente se mueve allí.

@makagonov ya que vivo en el mundo Java también traté de seguir su aplicación para captar el flujo de trabajo de construcción ST pero era difícil para mí debido a:

  • la combinación de bordes con nodos
  • el uso de punteros de índice en lugar de referencias
  • rompe declaraciones;
  • continue;

Así que terminé con dicha aplicación en Java que espero que refleja todos los pasos de forma más clara y reducirá el tiempo de aprendizaje para otras personas 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);
        }
    });
  }
}