El trie fue la primera estructura de datos de este tipo descubierta.
El árbol de sufijo es una mejora sobre el trie (tiene enlaces de sufijo que permiten la búsqueda de error lineal, el árbol de sufijo recorta las ramas innecesarias del trie, por lo tanto, no requiere tanto espacio).
La matriz de sufijos es una estructura de datos simplificada basada en el árbol de sufijos (sin enlaces de sufijos (coincidencias de errores lentos), aunque la coincidencia de patrones es muy rápida).
El trie no es para uso en el mundo real porque consume demasiado espacio.
El árbol de sufijo es más ligero y más rápido que el trie y se usa para indexar el ADN u optimizar algunos grandes motores de búsqueda web.
La matriz de sufijos es más lenta en algunas búsquedas de patrones que en el árbol de sufijos, pero ocupa menos espacio y es más utilizada que el árbol Suffix.
En la misma familia de estructuras de datos:
Hay otras implementaciones, el CST es una implementación del árbol de sufijos utilizando un arreglo de sufijos y algunas estructuras de datos adicionales para obtener algunas de las capacidades de búsqueda de árbol de sufijos.
El FCST lo lleva más lejos, implementa un árbol de sufijo muestreado con una matriz de sufijos.
El DFCST es una versión dinámica del FCST.
Ampliación:
Los dos factores importantes son el uso del espacio y el tiempo de ejecución de la operación. Se podría pensar que con las máquinas modernas esto no es relevante, pero para indexar el ADN de un solo ser humano requeriría 40 gigabytes de memoria (utilizando un árbol de sufijo descomprimido y no optimizado). Y construir uno de estos índices sobre esta cantidad de datos puede llevar días. Imagine Google, tiene muchos datos de búsqueda, necesitan un gran índice sobre todos los datos web y no lo cambian cada vez que alguien construye una página web. Tienen alguna forma de almacenamiento en caché para eso. Sin embargo, el índice principal probablemente sea estático. Y cada dos semanas más o menos reúnen todos los nuevos sitios web y datos y crean un nuevo índice, que reemplaza al antiguo cuando termina el nuevo. No sé qué algoritmo usan para indexar, pero probablemente sea un arreglo de sufijo con propiedades de árbol de sufijo sobre una base de datos particionada.
El CST utiliza 8 gigabytes, sin embargo, la velocidad de las operaciones del árbol de sufijo se reduce considerablemente.
El conjunto de sufijos puede hacer lo mismo en unos 700 megas a 2 Gigas. Sin embargo, no encontrará errores genéticos en el ADN con una matriz de sufijos (lo que significa que buscar un patrón con un comodín es mucho más lento).
El FCST (árbol de sufijo totalmente comprimido) puede crear un árbol de sufijos en 800 a 1.5 gigas. Con un deterioro de velocidad bastante pequeño hacia el CST.
El DFCST utiliza un 20% más de espacio que el FCST y pierde velocidad en la implementación estática del FCST (sin embargo, un índice dinámico es muy importante).
No hay muchas implementaciones viables (espacio-sabio) del árbol de sufijo porque es muy difícil hacer que las operaciones aceleren la compensación de las estructuras de datos del costo de espacio de RAM.
Dicho esto, el árbol de sufijo tiene resultados de búsqueda muy interesantes para la coincidencia de patrones con errores. El aho corasick no es tan rápido (aunque es casi tan rápido para algunas operaciones, no coincide con el error) y el Boyer Moore queda en el polvo.
¿El mejor rendimiento para qué operaciones? –