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!
algorithm
data-structures
trie
suffix-tree
Cratylus
fuente
fuente
Respuestas:
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:
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.
fuente
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).
fuente
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.
fuente
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)
fuente