algorithm - que - ¿Cómo y cuándo crear un enlace de sufijo en el árbol de sufijos?

sufijos que forman adjetivos

Question

¿Podría alguien darme un ejemplo sobre cómo y cuándo crear un enlace de sufijo en el árbol de sufijos?

Si mi cadena es ABABABC , pero use un ejemplo diferente si eso es mejor.

Espero dar algunas fotos para ilustrar cada paso.

muy apreciado.

Answer 1

Para entender esto, primero recuerde que hay tres tipos de nodos en un árbol de sufijos:

• La raíz
• Nodos internos
• Nodos de la hoja

En el gráfico siguiente, que es el árbol de ABABABC de ABABABC , el círculo amarillo es la raíz , los grises, los azules y los verdes son nodos internos , y los pequeños negros son las hojas.

Hay dos cosas importantes a tener en cuenta:

• Los nodos internos siempre tienen más de 1 borde saliente . Es decir, los nodos internos marcan aquellas partes del árbol donde se produce la ramificación .

• La bifurcación ocurre dondequiera que esté involucrada una cadena repetida , y solo allí. Para cualquier nodo interno X, la cadena que va de la raíz a X debe haber ocurrido en la cadena de entrada al menos tantas veces como bordes salientes de X.

Ejemplo: la cadena que conduce al nodo azul es ABAB . De hecho, esta cadena aparece dos veces en la cadena de entrada: en la posición 0 y en la posición 2. Y es por eso que existe el nodo azul.

Ahora acerca de los enlaces de sufijo:

1. Si la cadena que lleva a algún nodo interno X tiene más de 1 carácter, la misma cadena menos el primer carácter (llame a esto s _-1 ) también debe estar en el árbol (después de todo, es un árbol de sufijos, por lo que el sufijo de cualquiera de sus cuerdas debe estar en el árbol, también).

   Ejemplo: Sea s = ABAB , la cadena que conduce al nodo azul. Luego, después de eliminar el primer carácter, s _-1 es BAB . Y de hecho, esa cadena se encuentra en el árbol, también. Conduce al nodo verde.

2. Si alguna cadena s conduce a un nodo interno, su versión abreviada s _{-1 también} debe conducir a un nodo interno (llámelo X _-1 ). ¿Por qué? Debido a que s debe aparecer al menos dos veces en la cadena de entrada, por lo que s _-1 debe aparecer al menos tantas veces (porque es parte de s : donde aparece s , también debe aparecer s _-1 ). Pero si s _-1 aparece varias veces en la cadena de entrada, entonces debe haber un nodo interno para ello.

3. En cualquiera de estas situaciones, un enlace especial que conecta X a X _-1 es un enlace de sufijo.

Nota: Debido a (1) y (2) anteriores, cada nodo interno X que tiene una etiqueta de raíz a X de más de 1 carácter debe tener un enlace de sufijo a exactamente otro nodo interno.

Ejemplo:

Este es el mismo árbol de sufijos que antes; Las líneas de puntos indican los enlaces de sufijo. Si comienza en el nodo azul y sigue los enlaces de sufijo desde allí (de azul a verde, al primer gris y al segundo gris) y observa las cadenas que van desde la raíz a cada nodo, verá esto:

 ABAB   ->    BAB    ->    AB    ->    B
(blue)      (green)     (gray1)     (gray2)

Es por esto que se llaman enlaces de sufijo (la secuencia completa se llama cadena de sufijo ).

¿Para qué son buenos?

Son buenos para sorprendentemente muchas cosas. Sin embargo, desempeñan un papel particular en el algoritmo de Ukkonen para la construcción del árbol de sufijos , específicamente en la Regla 3 que se describe allí: Después de insertar el carácter final de algunos sufijos en algún punto X, el algoritmo debe insertar el carácter final del sufijo s _-1 en O (1) tiempo. Para hacer eso, usa el enlace del sufijo para saltar directamente al lugar X _-1 y hace la inserción.

Pero, tenga en cuenta que no es necesario colocar enlaces de sufijo en un árbol de sufijos. No forman parte de la definición de un árbol de sufijos, son solo enlaces especiales utilizados por algunos algoritmos que construyen o usan árboles de sufijos.

Con respecto a los nodos de un solo carácter: ¿Qué sucede si hay un nodo interno X cuya cadena (es decir, la cadena en la ruta de la raíz a la X) consta de un solo carácter? Según la definición anterior, X no tiene un enlace de sufijo. Sin embargo, puede asumir que si tuviera un enlace de sufijo, apuntaría al nodo raíz. Además: si, según la definición anterior, un nodo interno no tiene un enlace de sufijo, debe ser un nodo de un solo carácter, por lo que siempre puede suponer que si no hay un enlace de sufijo en un nodo interno, debe ser un solo enlace. nodo de caracteres y, por lo tanto, el nodo que representa el sufijo s _-1 es el nodo raíz. (En este caso, algunos algoritmos pueden agregar un enlace de sufijo explícito que apunta al nodo raíz). Gracias a j_random_hacker por el comentario sobre esto.