java - tries - trie significado
Trie vs. Suffix Tree vs. Suffix Array (6)
Qué estructura proporciona los mejores resultados de rendimiento; trie (árbol de prefijos), árbol de sufijos o matriz de sufijos? ¿Hay otras estructuras similares? ¿Cuáles son las buenas implementaciones de Java de estas estructuras?
Editar: en este caso quiero hacer una coincidencia de cadenas entre un gran diccionario de nombres y un gran conjunto de textos en lenguaje natural, para identificar los nombres del diccionario en los textos.
EDITAR: En este caso quiero hacer una coincidencia de cadenas entre un gran diccionario de nombres y un gran conjunto de textos en lenguaje natural, para identificar los nombres del diccionario en los textos.
Esto suena como una aplicación para el algoritmo Aho-Corasick : construye un autómata del diccionario (en tiempo lineal), que luego puede usarse para encontrar todas las ocurrencias de cualquiera de las palabras del diccionario en varios textos (también en tiempo lineal).
(La descripción en estas notas de conferencia , enlazadas desde la sección "Enlaces externos" de la página de Wikipedia, es mucho más fácil de leer que la descripción en la página).
¿Qué operaciones planeas hacer? libdivsufsort fue en algún momento la mejor implementación de matriz de sufijos en C.
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 sufijo que permiten la búsqueda lineal de errores, 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 sufijos 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 usa menos espacio y es más utilizada que el árbol de sufijos.
En la misma familia de estructuras de datos:
Existen otras implementaciones, la CST es una implementación del árbol de sufijos que utiliza una matriz 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 allá, implementa un árbol de sufijo muestreado con una matriz de sufijos.
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. 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 usa 8 gigabytes, sin embargo, la velocidad de las operaciones del árbol de sufijo se reduce considerablemente.
La matriz 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 (en el espacio) del árbol de sufijos porque es muy difícil hacer que las operaciones aumenten la velocidad para compensar el costo de espacio de la RAM de las estructuras de datos.
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.
Trie vs Suffix tree
ambas estructuras de datos aseguran una búsqueda muy rápida, el tiempo de búsqueda es proporcional a la longitud de la palabra de consulta, tiempo de complejidad O (m) donde m es la longitud de la palabra de consulta.
es malo si tenemos una palabra de consulta que tenga 10 caracteres, por lo que necesitamos como mucho 10 pasos para encontrarla.
Trie : Un árbol para almacenar cadenas en el que hay un nodo por cada prefijo común. Las cadenas se almacenan en nodos de hojas adicionales.
Árbol de sufijo : una representación compacta de un trie correspondiente a los sufijos de una cadena dada donde todos los nodos con un hijo se fusionan con sus padres.
def son de: Dictionary of Algorithms and Data Structures
generalmente Trie solía indexar palabras del diccionario (léxico) o cualquier conjunto de cadenas ejemplo D = {abcd, abcdd, bxcdf, ....., zzzz}
un sufijo usado para indexar texto usando la misma estructura de datos "Trie" en todos los sufijos de nuestro texto T = abcdabcg todos los sufijos de T = {abcdabcg, abcdabc, abcdab, abcda, abcd, abc, ab, a}
ahora parece un grupo de cadenas. construimos un Trie sobre este grupo de cadenas (todos los sufijos de T).
la construcción de ambas estructuras de datos es lineal, toma O (n) en tiempo y espacio.
en el caso de dicionary (un conjunto de cadenas): n = la suma de los caracteres de todas las palabras. en texto: n = longitud del texto.
array de sufijo: es una técnica para representar un árbol de sufijo en sapce comprimido, es una matriz de todas las posiciones de inicio de los sufijos de una cadena.
es más lento que el árbol de sufijos en el tiempo de búsqueda.
Para obtener más información, vaya a la wikipedia, hay un buen artículo que habla sobre este tema.
Usando Suffix Trees puede escribir algo que haga coincidir su diccionario con su texto en O (n + m + k) tiempo donde n es letras en su diccionario, m es letras en su texto, yk es el número de coincidencias. Las pruebas son mucho más lentas 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 sé de ninguna biblioteca de Java que proporcione las funciones necesarias.
This implementación del algoritmo de ordenación inducida (llamada sais) tiene una versión de Java para construir matrices de sufijos.