Sufijo árbol y Tries. ¿Cuál es la diferencia?

81

Estoy leyendo sobre los Triescomúnmente conocidos como árboles de prefijos y Suffix Trees.
Aunque he encontrado el código para un, Trieno puedo encontrar un ejemplo para un Suffix Tree. También tengo la sensación de que el código que construye a Triees el mismo que el de a Suffix Treecon la única diferencia de que en el primer caso almacenamos prefijos pero en el segundo sufijos.
¿Es esto cierto? ¿Alguien puede ayudarme a aclarar esto en mi cabeza? ¡Un código de ejemplo sería de gran ayuda!

Cratylus
fuente
1
TL; DR El árbol de sufijos de una cadena es una patricia trie de todos sus sufijos. Lo único especial es que las etiquetas de los bordes son subcadenas de la cadena original, por lo que se pueden representar como un par de índices y solo ocupan espacio constante. Por eso también se puede construir en tiempo lineal.
Niklas B.

Respuestas:

66

Un árbol de sufijos se puede ver como una estructura de datos construida sobre un trie donde, en lugar de simplemente agregar la cadena en sí al trie, también agregaría todos los sufijos posibles de esa cadena. Como ejemplo, si quisiera indexar la cadena banana en un árbol de sufijos, debería construir un trie con las siguientes cadenas:

banana
anana
nana
ana
na
a

Una vez hecho esto, puede buscar cualquier n-grama y ver si está presente en su cadena indexada. En otras palabras, la búsqueda de n-gramas es una búsqueda de prefijos de todos los posibles sufijos de su cadena.

Esta es la forma más sencilla y lenta de construir un árbol de sufijos. Resulta que hay muchas variantes más sofisticadas en esta estructura de datos que mejoran el espacio y el tiempo de construcción o ambos. No estoy lo suficientemente versado en este dominio como para dar una descripción general, pero puede comenzar por buscar matrices de sufijos o estructuras de datos avanzadas de esta clase (lecciones 16 y 18).

Esta respuesta también hace un trabajo maravilloso al explicar una variante de esta estructura de datos.

Ze Blob
fuente
Esto es lo que sospechaba. El trie se usa para construir el árbol de sufijos y es por eso que la mayoría de los libros de texto solo proporcionan código para los intentos. Pero esta es la implementación del peor de los casos, ¿eh?
Cratylus
@Cratylus Los árboles de sufijo son más útiles en cadenas muy grandes (por ejemplo, indexando todas las obras de Shakespeare) donde el espacio O (n ^ 2) y el tiempo de construcción simplemente no lo van a cortar. Afortunadamente, esos límites se pueden reducir bastante.
Ze Blob
8

Si imagina un Trie en el que pone los sufijos de alguna palabra, podrá consultar las subcadenas de la cadena muy fácilmente. Esta es la idea principal detrás del árbol de sufijos, es básicamente un "sufijo trie".

Pero usando este enfoque ingenuo, construir este árbol para una cadena de tamaño n sería O (n ^ 2) y tomaría mucha memoria.

Dado que todas las entradas de este árbol son sufijos de la misma cadena, comparten mucha información, por lo que existen algoritmos optimizados que te permiten crearlos de manera más eficiente. El algoritmo de Ukkonen, por ejemplo, le permite crear un árbol de sufijos en línea en complejidad de tiempo O (n).

Juan Lopes
fuente
2
¿Estás diciendo que los árboles de sufijos y los intentos de sufijos son lo mismo?
Batman
1

La diferencia es muy sencilla. Un árbol de sufijos tiene menos nodos "ficticios" que el sufijo trie. Estos nodos ficticios son caracteres únicos que aumentan la operación de búsqueda en el árbol.

curioso
fuente
0

Los nodos de Trie tienen enlaces a contextos más cortos, 'Tree' no los tiene. Si los nodos de Tree obtienen un enlace a un contexto más corto, entonces recurre a Trie; o)

Stephan Banev
fuente