Te damos la bienvenida a nuestra web, aquí hallarás la respuesta de lo que estabas buscando.
Solución:
El trie fue la primera estructura de datos de este tipo descubierta.
El árbol de sufijos es una mejora sobre el trie (tiene enlaces de sufijos que permiten la búsqueda de errores lineales, el árbol de sufijos recorta las ramas innecesarias del trie, por lo que no requiere tanto espacio).
el sufijo array es una estructura de datos simplificada basada en el árbol de sufijos (sin enlaces de sufijos (coincidencias de error lentas), pero 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 sufijos es más ligero y rápido que el trie y se utiliza para indexar el ADN u optimizar algunos grandes motores de búsqueda web.
el sufijo array es más lento en algunas búsquedas de patrones que el árbol de sufijos pero ocupa menos espacio y se usa más ampliamente que el árbol de sufijos.
En la misma familia de estructuras de datos:
Hay otras implementaciones, el CST es una implementación del árbol de sufijos usando un sufijo array y algunas estructuras de datos adicionales para obtener algunas de las capacidades de búsqueda del árbol de sufijos.
El FCST va más allá, implementa un árbol de sufijos de muestra con un sufijo array.
El DFCST es una versión dinámica del FCST.
En expansión:
Los dos factores importantes son el uso del espacio y el tiempo de ejecución de la operación. Puede pensar que con las máquinas modernas esto no es relevante, pero indexar el ADN de un solo ser humano requeriría 40 gigabytes de memoria (usando un árbol de sufijos sin comprimir y sin optimizar). Y construir uno de estos índices sobre esta cantidad de datos puede llevar días. Imagínese Google, tiene muchos datos que se pueden buscar, necesitan un gran índice sobre todos los datos web y no lo cambian cada vez que alguien crea una página web. Tienen alguna forma de almacenamiento en caché para eso. Sin embargo, el índice principal es probablemente static. Y cada dos semanas recopilan todos los sitios web y datos nuevos y crean un nuevo índice, reemplazando el antiguo cuando el nuevo está terminado. No sé qué algoritmo usan para indexar, pero probablemente sea un sufijo array con propiedades de árbol de sufijos sobre una base de datos particionada.
El CST usa 8 gigabytes, sin embargo, la velocidad de las operaciones del árbol de sufijos se reduce considerablemente.
el sufijo array puede hacer lo mismo en unos 700 megas a 2 Gigas. Sin embargo, no encontrará errores genéticos en el ADN con un sufijo array (es decir: buscar un patrón con un comodín es mucho más lento).
El FCST (árbol de sufijos completamente comprimido) puede crear un árbol de sufijos en 800 a 1,5 gigas. Con un deterioro de velocidad bastante pequeño hacia la CST.
El DFCST utiliza un 20 % más de espacio que el FCST y pierde velocidad frente al static implementación del FCST (sin embargo, un índice dinámico es muy importante).
No hay muchas implementaciones viables (en cuanto al espacio) del árbol de sufijos porque es muy difícil hacer que el aumento de la velocidad de las operaciones compense el costo del espacio RAM de las estructuras de datos.
Dicho esto, el árbol de sufijos tiene resultados de búsqueda muy interesantes para la coincidencia de patrones con errores. El aho corasick no es tan rápido (aunque casi tan rápido para algunas operaciones, no para la coincidencia de errores) y el boyer moore se queda atrás.
¿Qué operaciones piensas hacer? libdivsufsort fue en un momento el mejor sufijo array implementacion en c
Con los árboles de sufijos, puede escribir algo que haga coincidir su diccionario con su texto en tiempo O (n + m + k), donde n son letras en su diccionario, m son letras en su texto y k es el número de coincidencias. Los intentos son mucho más lentos para esto. No estoy seguro de qué es una matriz de sufijos, así que no puedo comentar sobre eso.
Dicho esto, no es trivial codificar y no conozco ninguna biblioteca de Java que proporcione las funciones necesarias.