algorithm - suffix array
Árbol de sufijos y Tries. ¿Cuál es la diferencia? (3)
Estoy leyendo acerca de los Tries comúnmente conocidos como árboles de prefijo y árboles de Suffix Trees .
Aunque he encontrado el código para un Trie no puedo encontrar un ejemplo para un Suffix Tree . También tengo la sensación de que el código que crea un Trie es el mismo que el de un Suffix Tree con la única diferencia de que en el primer caso almacenamos prefijos pero en los últimos sufijos.
¿Es esto cierto? ¿Alguien puede ayudarme a aclarar esto en mi cabeza? ¡Un código de ejemplo sería de gran ayuda!
La diferencia es muy simple. Un árbol de sufijo 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
Si imagina un Trie en el que coloca los sufijos de algunas palabras, podrá consultar las subcadenas de la cadena con mucha facilidad. Esta es la idea principal detrás del árbol de sufijos, básicamente es 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á mucha memoria.
Como todas las entradas de este árbol son sufijos de la misma cadena, comparten mucha información, por lo que existen algoritmos optimizados que le permiten crearlos de manera más eficiente. El algoritmo de Ukkonen, por ejemplo, le permite crear un árbol de sufijos en línea con una complejidad de tiempo O (n).
Un árbol de sufijos se puede ver como una estructura de datos construida en la parte superior de un trie, donde, en lugar de simplemente agregar la cadena misma al trie, también debería agregar todos los sufijos posibles de esa cadena. Como ejemplo, si quisiera indexar el string banana en un árbol de sufijo, construiría un trie con las siguientes cadenas:
banana
anana
nana
ana
na
a
Una vez hecho esto, puede buscar cualquier n-gram y ver si está presente en su cadena indexada. En otras palabras, la búsqueda n-gram es una búsqueda de prefijo de todos los posibles sufijos de su cadena.
Esta es la forma más simple y más 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. No estoy lo suficientemente versado en este dominio para dar una visión general, pero puede comenzar buscando en matrices de sufijos o estructuras de datos avanzadas de esta clase (disertaciones 16 y 18).
Esta answer también hace un maravilloso trabajo al explicar una variante de esta estructura de datos.