Pregunta 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 comienzan a hacer un uso excesivo de la simbología matemática. Lo más cercano a una buena explicación que he encontrado es Búsqueda rápida de cadenas con árboles de sufijos, 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 Stack Overflow 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 (n2), como se señala en la mayoría de las explicaciones, ya que necesitamos pasar por todos los prefijos, entonces necesitamos 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 ese es lo que estoy teniendo 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 completado DO# código fuente. 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 sufijo, y he implementado el algoritmo en JavaScript. Gist está abajo. Debería estar libre de errores. Volcarlo en un archivo js, npm install chalk desde la misma ubicación, y luego ejecutar 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


949
2018-02-26 11:30


origen


Respuestas:


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. Por lo tanto, allí es 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 simples caracteres. En cambio, cada borde está etiquetado con un par de enteros [from,to]. Estos son punteros en el texto. En este sentido, cada edge 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 sufijos de un cadena particularmente simple, una cadena sin caracteres repetidos:

abc

El algoritmo funciona en pasos, de izquierda a derecha. Ahi esta un paso para cada personaje de la cuerda. 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 el izquierda, y primero inserta solo el caracter simple 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 el subcadena que comienza en la posición 0 y termina en el final actual. yo usa el simbolo # significar el 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 b) Nuestro objetivo en cada paso es insertar todos los sufijos hasta la posición actual. Nosotros hacemos esto por

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

En nuestra representación, esto parece

enter image description here

Y lo que significa es:

Observamos dos cosas:

  • La representación del borde para ab es lo mismo como 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, porque consta de solo dos punteros en el texto, independientemente de cuántos caracteres representa

A continuación, incrementamos la posición nuevamente y actualizamos el árbol añadiendo un c a cada borde existente e insertando una nueva ventaja 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 insertando un nuevo borde para el personaje final se puede hacer en O (1) hora. 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 cualquier repetición. Ahora vemos una cadena más realista:

abcabxabcd

Empieza con abc como en el ejemplo anterior, entonces ab se repite y seguido por x, y entonces abc se repite seguido por d.

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

Etapa 4: Nos movemos # a la posición 4. Esto actualiza implícitamente todas las existentes bordes a esto:

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

Antes de hacer esto, presentamos dos variables más (además de #), que por supuesto han estado allí todo el tiempo, pero no hemos utilizado ellos hasta el momento:

  • los punto activoque es un triple (active_node,active_edge,active_length)
  • los 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 digamos:

  • En el simple abc ejemplo, 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 la única ventaja que insertamos en cada paso se insertó en el nodo raíz como una borde recién creado. Pronto veremos por qué es necesario un triple para representar esta información
  • los remainder siempre se estableció en 1 al comienzo de cada paso. El significado de esto era que la cantidad de sufijos que teníamos que insertar activamente al final de cada paso fue 1 (siempre solo el personaje final).

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

  • Nosotros no haga inserte un borde nuevo [4,#] en el nodo raíz. En cambio nosotros simplemente tenga en cuenta que el sufijo a ya está en nuestro árbol. Termina en el medio de un borde más largo, pero no estamos molesto por eso. Simplemente dejamos las cosas como están.
  • Nosotros establecer el punto activo a (root,'a',1). Eso significa que el activo punto ahora está en algún lugar en el medio del borde saliente del nodo raíz que comienza con a, específicamente, después de la posición 1 en ese borde. Nosotros observe que el borde se especifica simplemente por su primer personaje a. Eso es suficiente porque puede haber solo uno borde comenzando con cualquier personaje en particular (confirme que esto es cierto después de leer toda la descripción).
  • También incrementamos remainder, entonces al comienzo del próximo paso será 2.

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

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

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

  • los a sufijo del paso anterior nunca ha sido correctamente insertado. Entonces tiene se mantuvoy como hemos progresado uno paso, ahora ha crecido desde a a ab.
  • Y tenemos que 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 es ahora el abcab borde), e inserte el personaje final actual b. Pero: Nuevamente, resulta que b es también ya está presente en ese mismo borde.

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

  • Actualiza el punto activo a (root,'a',2) (mismo nodo y borde como antes, pero ahora señalamos detrás del b)
  • Incrementar el remainder a 3 porque todavía no hemos adecuadamente insertado el borde final del paso anterior, y no insertamos el borde final actual tampoco.

Para ser claros: tuvimos que insertar ab y b en el paso actual, pero porque ab ya se encontró, actualizamos el punto activo y lo hicimos ni siquiera intento insertar b. ¿Por qué? Porque si ab está en el árbol, cada sufijo de eso (incluyendo b) debe estar en el árbol, también. Tal vez solo implícitamente, pero debe estar allí, debido a la forma en que hemos construido el árbol hasta ahora.

Procedemos a paso 6 al incrementar #. El árbol es actualizado automáticamente a:

Porque remainder es 3, tenemos que insertar abx, bx y x. El punto activo nos dice dónde ab termina, entonces solo necesitamos saltar allí e insertar el x. En efecto, x todavía no está allí, entonces dividir el abcabx borde e inserte un nodo interno:

Las representaciones de los bordes siguen siendo punteros en el texto, por lo que dividir e insertar un nodo interno se puede hacer en O (1) vez.

Así que hemos tratado con abx y decremento remainder a 2. Ahora nosotros necesita insertar el siguiente sufijo restante, bx. Pero antes de hacer eso necesitamos actualizar el punto activo. La regla para esto, después de dividir e insertando un borde, se llamará Regla 1 a continuación, y se aplica siempre que active_node es root (aprenderemos la regla 3 para otros casos más abajo). 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   necesidad de insertar, es decir b
  • active_length se reduce en 1

Por lo tanto, el nuevo punto activo triple (root,'b',1) indica que el El siguiente inserto debe hacerse en el bcabx borde, detrás de 1 personaje, es decir, detrás b. Podemos identificar el punto de inserción en el tiempo O (1) y verificar si x ya está presente o no. Si estaba presente, nosotros terminaría el paso actual y dejaría todo como está. Pero x no está presente, entonces lo insertamos dividiendo el borde:

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

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

Si dividimos un borde e insertamos un nuevo nodo, y si eso es no la   primer nodo creado durante el paso actual, conectamos el   nodo insertado y el nuevo nodo a través de un puntero especial, un sufijo   enlazar. Más adelante veremos por qué es útil. Esto es lo que obtenemos, el   el sufijo link se representa como un borde punteado:

Todavía tenemos que insertar el sufijo final del paso actual, x. Desde el active_length componente del nodo activo ha caído a 0, la inserción final se hace en la raíz directamente. Como no hay borde de salida 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.

Procedemos a paso 7 configurando #= 7, que agrega automáticamente el siguiente carácter, a, a todos los bordes de las hojas, como siempre. Luego intentamos insertar el nuevo final carácter al punto activo (la raíz), y encontrar que está allí ya. Así que finalizamos el paso actual sin insertar nada y actualizar el punto activo a (root,'a',1).

En paso 8, #= 8, agregamos b, y como se vio antes, esto solo significa que actualizamos el punto activo a (root,'a',2) e incrementar remainder sin hacer cualquier otra cosa, 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 al volver a configurarlo para (node1,'\0x',0). Aquí, yo uso node1 para referirse al nodo interno el ab el borde termina en.

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

Segunda extensión: usar enlaces de sufijos

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

Ahora en paso #= 10, remainder is 4, y entonces primero tenemos que insertar abcd (que permanece de 3 pasos atrás) insertando d en el activo punto.

Intentando insertar d en el punto activo provoca una división de borde en O (1) vez:

los active_node, desde donde 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 esa no es la raíz   nodo, seguimos el enlace de sufijo saliendo de ese nodo, si hay   cualquiera, y restablecer el active_node al nodo al que apunta. Si hay   sin sufijo, configuramos el active_nodea la raíz active_edge   y active_length permanece inalterable.

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

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

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

Observamos: Los enlaces de sufijo nos permiten restablecer el punto activo para que podamos   puede hacer el siguiente inserción restante en O (1) esfuerzo. Mira el   gráfico de arriba para confirmar que de hecho nodo en la etiqueta ab está vinculado a   el 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 nosotros necesita seguir la regla 3 para reiniciar el punto activo nuevamente. Desde el corriente active_node (rojo arriba) no tiene un enlace de sufijo, reiniciamos a 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 personaje, es decir, detrás c. Esto causa otra división:

Y dado que esto implica la creación de un nuevo nodo interno, seguimos regla 2 y establecer un nuevo enlace de sufijo desde el interno creado previamente nodo:

(Estoy usando Graphviz Dot para estos pequeños gráficos El nuevo enlace de sufijo hizo que dot reorganizara el existente bordes, así que verifique con cuidado para confirmar que lo único que fue insertado arriba es un nuevo enlace de sufijo).

Con este, remainder se puede establecer en 1 y desde el active_node es raíz, utilizamos la regla 1 para actualizar el punto activo a (root,'d',0). Esta significa que la inserción final del paso actual es insertar un solo d en la raíz:

Ese fue el último paso y hemos terminado. Hay varios final observaciones, aunque:

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

  • Pero no trata con a) ningún sufijo restante de anterior pasos, yb) con el último carácter del paso actual.

  • remainder nos dice cuántos insertos adicionales necesitamos 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 hacer el inserto. Importante: Cada inserción es hecho en O (1) vez desde que el punto activo nos dice exactamente dónde ir, y tenemos que agregar solo un solo carácter en el activo punto. ¿Por qué? Porque los otros personajes son contenido implícitamente (de lo contrario, el punto activo no estaría donde está).

  • Después de cada inserción, disminuimos remainder y sigue el sufijo link si hay alguno. Si no, vamos a la raíz (regla 3). Si nosotros ya están en la raíz, modificamos el punto activo usando la regla 1. En en cualquier caso, solo toma O (1) vez.

  • Si, durante una de estas inserciones, encontramos que el personaje que queremos insertar ya está allí, no hacemos nada y terminamos paso actual, incluso si remainder> 0. La razón es que cualquier inserciones que quedan serán sufijos de la que acabamos de intentar hacer. Por lo tanto, son todos implícito en el árbol actual. El hecho ese remainder> 0 se asegura de que tratemos con los sufijos restantes luego.

  • ¿Qué pasa si al final del algoritmo remainder> 0? Este será el caso cada vez que el final del texto es una subcadena que se produjo en algún lugar antes. En ese caso, debemos agregar un carácter adicional al final de la cadena que no ha ocurrido antes. En el literatura, generalmente el signo de dólar $ se usa como un símbolo para ese. ¿Por que importa? -> Si más tarde usamos el árbol de sufijos completado para buscar sufijos, debemos aceptar coincidencias solo si terminar en una hoja. De lo contrario, obtendríamos muchas coincidencias espurias, porque hay muchos instrumentos de cuerda implícitamente contenidos en el árbol que no son sufijos reales de la cadena principal. Forzando remainder ser 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 último paso 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 es n caracteres de longitud, obviamente hay n pasos (o n + 1 si agregamos el signo de dólar). En cada paso, no hacemos nada (excepto actualizando las variables), o hacemos remainder insertos, cada uno tomando O (1) hora. Ya que remainder indica cuántas veces no hemos hecho nada en los pasos anteriores, y se reduce para 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 he explicado correctamente: Puede suceder que sigamos un enlace de sufijo, actualizamos el activo señalar, y luego encontrar que es active_length componente no trabajar bien con el nuevo active_node. Por ejemplo, considere una situación Me gusta esto:

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

Ahora deja que el punto activo sea (red,'d',3), por lo que apunta al lugar detrás de la f sobre el defg borde. Ahora supongamos que hicimos lo necesario actualizaciones y ahora sigue el enlace de 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 salir del nodo verde es de, entonces solo tiene 2 caracteres. Para encontrar el punto activo correcto, obviamente necesidad de seguir ese borde al nodo azul y restablecer a (blue,'f',1).

En un caso particularmente malo, el active_length podría ser tan grande como remainder, que puede ser tan grande como n. Y podría pasar muy bien que para encontrar el punto activo correcto, no solo tenemos que saltar sobre uno nodo interno, pero tal vez muchos, hasta n en el peor de los casos. Hace eso significa que el algoritmo tiene un O oculto2) complejidad, porque en cada paso remainder generalmente es O (n) y los ajustes posteriores al nodo activo después de seguir un enlace de sufijo también podría ser O (n)?

No. La razón es que si realmente tenemos que ajustar el punto activo (por ejemplo, de verde a azul como el anterior), eso nos lleva a un nuevo nodo que tiene su propio enlace de sufijo y active_length será reducido. Como seguimos la cadena de enlaces de sufijo que hacemos los insertos restantes, active_length sólo podemos disminución, y la cantidad de ajustes de punto activo que podemos hacer en el camino no puede ser más grande que active_length en cualquier momento dado. Ya que active_length nunca puede ser más grande que remaindery remainder es O (n) no solo en cada paso, sino en la suma total de incrementos hecho para remainder en el transcurso de todo el proceso es O (n) también, el número de ajustes de puntos activos también está limitado por En).


2164
2018-03-01 09:13



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 importante sufijo enlaces.

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. recordatorio - muestra la cantidad 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, California y un.

Usemos un concepto de nodo interno - todos los nodos, excepto el raíz y el 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í no se cambia (solo actualizamos el active point y 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 hasta edge_length es estrictamente mayor que active_length.

Ahora, redefinamos las reglas:

Regla 1

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

  1. nodo activo no ha cambiado
  2. longitud activa está decrementado
  3. 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 hacer un insertador desde nodo internoy este no es el primero TAL  nodo interno en el paso actual, luego vinculamos el anterior TAL nodo con ESTA uno a través de un sufijo link.

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

Regla 3

Después de un inserto de la nodo activo que no es el raíz nodo, debemos seguir el enlace de sufijo y configurar el nodo activo al nodo al que apunta. Si no hay un enlace de sufijo, configure el nodo activo al raíz nodo. De cualquier manera, borde activo y longitud activa permanecer sin cambios.

En esta definición de Rule 3 también consideramos las inserciones 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, de acuerdo con Observation 1, solo actualización active point y remainder, dejando el árbol sin cambios. PERO si hay un nodo interno marcado como que necesita un enlace de sufijo, debemos conectar ese nodo con nuestra corriente active node 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 nosotros NO conecta los nodos a través de un enlace de sufijo:

    • antes de agregar la última letra do:

    • después de agregar la última letra do:

  2. Si nosotros HACER conecta los nodos a través de un enlace de sufijo:

    • antes de agregar la última letra do:

    • después de agregar la última letra do:

Parece que no hay una diferencia significativa: en el segundo caso, hay dos enlaces de sufijo más. Pero estos enlaces de sufijo son correcto, y uno de ellos, desde el nodo azul al rojo, es muy importante para nuestro enfoque con 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 él, si no hay un sufijo de enlace, entonces debemos poner el active_node a la raíz

Cuando estábamos agregando la última letra al árbol, el nodo rojo tenía ya existió antes hicimos un inserto desde el nodo azul (el borde etiquetado 'do') Como había un inserto del nodo azul, lo marcamos como necesitando un enlace de sufijo. Entonces, confiando en el punto activo enfoque, el active node se estableció en el nodo rojo. Pero no hacemos una inserción desde el nodo rojo, ya que la letra 'do' 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 punto activo enfoque garantiza que lleguemos a un lugar correcto, es decir, al siguiente lugar donde debemos procesar un inserto de un corta sufijo.

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.


112
2018-01-29 09:57



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

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

  1. Terminar con Remainder > 0 Resulta que esta situación también puede suceder durante el paso desplegable, no solo el final de todo el algoritmo. Cuando eso sucede, podemos dejar el resto, actnode, actedge y actlength sin alterar, finalice el paso de despliegue actual y comience otro paso manteniendo plegado o desplegado dependiendo de si el siguiente carácter en la cadena original está en la ruta actual o no.

  2. Salto sobre nodos: Cuando seguimos un enlace de sufijo, actualizamos el punto activo y luego descubrimos que su componente active_length no funciona bien con el nuevo active_node. Tenemos que seguir adelante al lugar correcto para dividir o insertar una hoja. Este proceso podría ser no es tan sencillo porque durante la mudanza, la acción y la acción cambian constantemente, cuando tienes que volver a la nodo raíz, el actedge y actlength podría ser incorrecto debido a esos movimientos. Necesitamos variables adicionales para mantener esa información.

    enter image description here

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

  1. Split podría degenerar Cuando intente dividir un borde, en algún momento encontrará que la operación de división es correcta en un nodo. En ese caso, solo necesitamos agregar una nueva hoja a ese nodo, tomarlo como una operación estándar de división de bordes, lo que significa que los enlaces de sufijos si hay alguno, se deben mantener de manera correspondiente.

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

Finalmente, mi implementación en Pitón es como sigue:

Consejos:  Incluye un ingenuo impresión de árbol función en el código anterior, que es muy importante al depurar. Me salvó un montón de   tiempo y es conveniente para localizar casos especiales.


7
2017-08-02 02:35



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 sufijo 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 ...


6
2018-02-26 20:16



Hola, he intentado implementar la implementación explicada anteriormente en ruby, por favor, échale un vistazo. Parece que funciona bien.

la única diferencia en la implementación es que he intentado usar el objeto de borde en lugar de solo usar 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

3
2018-03-02 10:54



@jogojapan trajiste asombrosa explicación y visualización. Pero como @makagonov mencionó, faltan algunas reglas sobre la configuración de enlaces de sufijos. Es visible de una manera agradable cuando se va paso a paso http://brenden.github.io/ukkonen-animation/ a través de la palabra 'aabaaabb'. Cuando pasa del paso 10 al paso 11, no hay un enlace de sufijo desde el 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 traté de seguir tu implementación para comprender el flujo de trabajo de construcción de ST, pero fue difícil para mí debido a:

  • combinando bordes con nodos
  • usar indicadores de índice en lugar de referencias
  • rompe declaraciones;
  • continuar las declaraciones;

Así que terminé con dicha implementación en Java, que espero refleje todos los pasos de una manera más clara y reducirá 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);
        }
    });
  }
}

2
2018-04-21 14:22