¿Cómo funcionan los Suffix Trees?

Question

Estoy revisando el capítulo de estructuras de datos en The Algorithm Design Manual y encontré árboles de sufijos.

Los ejemplos de estados:

de entrada:

XYZXYZ$ 
YZXYZ$ 
    ZXYZ$ 
    XYZ$ 
    YZ$ 
    Z$ 
     $ 

Salida:

que no soy capaz de entender cómo ese árbol se genera a partir de la cadena de entrada dada. Los árboles de sufijos se utilizan para encontrar una subcadena dada en una cadena determinada, pero ¿cómo ayuda el árbol dado a eso? Entiendo otro ejemplo dado de un trie que se muestra a continuación, pero si el trie de abajo se compacta con un árbol de sufijo, ¿cómo se vería?

Answer 1

Los algoritmos eficientes estándar para la construcción de un árbol de sufijos son definitivamente no trivial. El principal algoritmo para hacerlo se llama algoritmo de Ukkonen y es una modificación del algoritmo ingenuo con dos optimizaciones adicionales. Probablemente sea mejor que lea this earlier question para obtener detalles sobre cómo construirlo.

Puede construir árboles de sufijo utilizando los algoritmos de inserción estándar en radix tries para insertar cada sufijo en el árbol, pero al hacerlo wlil tomar tiempo O (n 2 ), que puede ser costoso para las grandes cadenas.

En cuanto a la búsqueda rápida de subcadenas, recuerde que un árbol de sufijos es un trie comprimido de todos los sufijos de la cadena original (más algún marcador especial de fin de cadena). Si una cadena S es una subcadena de la cadena inicial T y tienes un trie de todos los sufijos de T, entonces podrías hacer una búsqueda para ver si T es un prefijo de cualquiera de las cadenas en ese trie. Si es así, entonces T debe ser una subcadena de S, ya que todos sus caracteres existen en secuencia en algún lugar de T. El algoritmo de búsqueda de subcadena del árbol de sufijos es precisamente esta búsqueda aplicada al trie comprimido, donde se siguen los bordes apropiados en cada paso.

Espero que esto ayude!

Answer 2

Un árbol de sufijo básicamente simplemente compacta corridas de letras juntas cuando no hay opciones para hacer. Por ejemplo, si mira el lado derecho del trie en su pregunta, después de haber visto un w, en realidad solo hay dos opciones: was y when. En el trie, el as en was y el hen en when cada uno tiene un nodo para cada letra. En un árbol de sufijos, que había puesto los dos juntos en nodos que mantienen as y hen, por lo que el lado derecho de su trie se convertiría en:

Answer 3

no soy capaz de entender cómo ese árbol se genera a partir de la cadena de entrada dada.

Básicamente crea un patricia trie con todos los sufijos que ha enumerado. Al insertar en un archivo patricia, busca en la raíz de un niño comenzando con el primer carácter de la cadena de entrada, si existe, continúa hacia abajo del árbol, pero si no lo hace, entonces crea un nuevo nodo fuera de la raíz.La raíz tendrá tantos hijos como caracteres únicos en la cadena de entrada ($, a, e, h, i, n, r, s, t, w). Puede continuar ese proceso para cada carácter en la cadena de entrada.

Los árboles de sufijo se utilizan para encontrar una subcadena dada en una cadena dada, pero ¿cómo ayuda el árbol dado a eso?

Si está buscando una subcadena "gallina", entonces comience la búsqueda desde la raíz de un niño que comienza con "h". Si la longitud de la cadena de "h" en el niño continúa procesando el niño "h" hasta que haya llegado al final de la cadena o si hay una falta de coincidencia de caracteres en la cadena de entrada y la cadena "h" infantil. Si empareja todo el niño "h", es decir, ingresa "gallina" que coincide con "él" en el niño "h" y luego pasa a los niños de "h" hasta llegar a "n", si no encuentra un niño comenzando con "n", entonces la subcadena no existe.

Compact Suffix Trie code:

└── (black) 
    ├── (white) as 
    ├── (white) e 
    │ ├── (white) eir 
    │ ├── (white) en 
    │ └── (white) ere 
    ├── (white) he 
    │ ├── (white) heir 
    │ ├── (white) hen 
    │ └── (white) here 
    ├── (white) ir 
    ├── (white) n 
    ├── (white) r 
    │ └── (white) re 
    ├── (white) s 
    ├── (white) the 
    │ ├── (white) their 
    │ └── (white) there 
    └── (black) w 
     ├── (white) was 
     └── (white) when 

Suffix Tree code:

String = the$their$there$was$when$ 
End of word character = $ 
└── (0) 
    ├── (22) $ 
    ├── (25) as$ 
    ├── (9) e 
    │ ├── (10) ir$ 
    │ ├── (32) n$ 
    │ └── (17) re$ 
    ├── (7) he 
    │ ├── (2) $ 
    │ ├── (8) ir$ 
    │ ├── (31) n$ 
    │ └── (16) re$ 
    ├── (11) ir$ 
    ├── (33) n$ 
    ├── (18) r 
    │ ├── (12) $ 
    │ └── (19) e$ 
    ├── (26) s$ 
    ├── (5) the 
    │ ├── (1) $ 
    │ ├── (6) ir$ 
    │ └── (15) re$ 
    └── (29) w 
     ├── (24) as$ 
     └── (30) hen$