algorithm - rugby - trie significado

¿Cómo elijo entre una tabla Hash y una Trie(árbol de prefijo)? (8)

Entonces, si tengo que elegir entre una tabla hash o un árbol de prefijos, ¿cuáles son los factores discriminatorios que me llevarían a elegir uno sobre el otro? Desde mi propio punto de vista ingenuo, parece que usar un trie tiene una carga adicional, ya que no se almacena como una matriz sino que en términos de tiempo de ejecución (asumiendo que la clave más larga es la más larga) puede ser esencialmente O (1) (en relación con el límite superior). ¿Tal vez la palabra inglesa más larga es de 50 caracteres?

Las tablas hash son búsquedas instantáneas una vez que obtiene el índice . Sin embargo, la clave para obtener el índice parece que podría tomar fácilmente cerca de 50 pasos.

¿Alguien puede proporcionarme una perspectiva más experimentada sobre esto? ¡Gracias!

Algunas aplicaciones (generalmente integradas, en tiempo real) requieren que el tiempo de procesamiento sea independiente de los datos. En ese caso, una tabla hash puede garantizar un tiempo de ejecución conocido, mientras que una trie varía en función de los datos.

La inserción y búsqueda en un trie es lineal con la longitud de la cadena de entrada O (s).

Un hash le dará una O (1) para búsqueda e inserción, pero primero debe calcular el hash basado en la cadena de entrada que nuevamente es O (s).

Conclusión, la complejidad del tiempo asintótico es lineal en ambos casos.

El trie tiene algunos gastos adicionales desde la perspectiva de los datos, pero puede elegir un trie comprimido que lo colocará de nuevo, más o menos en un empate con la tabla hash.

Para romper el lazo, hágase esta pregunta: ¿Necesito buscar palabras completas solamente? ¿O debo devolver todas las palabras que coincidan con un prefijo? (Como en un sistema de entrada de texto predictivo). Para el primer caso, vaya por un hash. Es un código más simple y limpio. Más fácil de probar y mantener. Para un caso de uso más elaborado donde importan prefijos o sufijos, vaya por un trie.

Y si lo haces solo por diversión, la implementación de un trie daría un buen uso a los domingos por la tarde.

Todo depende de qué problema estés tratando de resolver. Si todo lo que necesita hacer son inserciones y búsquedas, vaya con una tabla hash. Si necesita resolver problemas más complejos como las consultas relacionadas con el prefijo, entonces una trie podría ser la mejor solución.

Usa un árbol:

Si necesita la función de autocompletar
Encuentra todas las palabras que comiencen con ''a'' o ''ax'', etc.
Un árbol de sufijo es una forma especial de un árbol. Los sufijos tienen una lista completa de ventajas que hash no puede abarcar.

Ventajas de los intentos:

Los basicos:

Tiempo predecible de búsqueda de O (k) donde k es el tamaño de la clave
La búsqueda puede tomar menos de k tiempo si no está allí
Admite un recorrido ordenado
No hay necesidad de una función hash
La eliminación es sencilla

Nuevas operaciones:

Puede buscar rápidamente prefijos de claves, enumerar todas las entradas con un prefijo dado, etc.

Ventajas de la estructura vinculada:

Si hay muchos prefijos comunes, el espacio que requieren se comparte.
Los intentos inmutables pueden compartir estructura. En lugar de actualizar un trie en su lugar, puede construir uno nuevo que sea diferente solo a lo largo de una rama, en cualquier otro lado apuntando hacia el viejo trie. Esto puede ser útil para concurrencia, múltiples versiones simultáneas de una tabla, etc.
Un trie inmutable es compresible. Es decir, también puede compartir la estructura en los sufijos mediante el uso de hash-consing.

Ventajas de las tablas hash:

Todo el mundo sabe hashtables, ¿verdad? Su sistema ya tendrá una buena implementación bien optimizada, más rápido que los intentos para la mayoría de los propósitos.
Tus claves no necesitan tener ninguna estructura especial.
Más espacio-eficiente que la estructura trie vinculada obvia ( ver comentarios a continuación )

La implementación de HashTable es eficiente en el uso del espacio en comparación con la implementación básica de Trie . Pero con cadenas, el orden es necesario en la mayoría de las aplicaciones prácticas. Pero HashTable perturba totalmente el orden lexográfico. Ahora, si su aplicación está haciendo operaciones basadas en orden lexográfico (como búsqueda parcial, todas las cadenas con prefijo dado, todas las palabras en orden ordenado), debe usar Tries. Solo para la búsqueda, se debe usar HashTable (como podría decirse, da un tiempo mínimo de búsqueda).

PD: además de estos, los árboles de búsqueda terciaria (TST) serían una excelente opción. Su tiempo de búsqueda es más que HashTable, pero es eficiente en el tiempo en todas las demás operaciones. Además, es más eficiente en el uso del espacio que los intentos.

Hay algo que no he visto a nadie mencionar explícitamente que creo que es importante tener en cuenta. Tanto las tablas hash como las pruebas de varios tipos generalmente tendrán operaciones O(k) , donde k es la longitud de la cadena en bits (o equivalentemente en caracteres).

Esto supone que tienes una buena función hash. Si no quieres que "granja" y "animales de granja" hagan hash al mismo valor, entonces la función hash tendrá que usar todos los bits de la clave, por lo que los "animales de granja" hash tomarán aproximadamente el doble de tiempo que "granja" (a menos que esté en algún tipo de escenario de hash rodante, pero también hay escenarios similares de ahorro de operación con intentos). Y con un intento vainilla, está claro por qué la inserción de "animales de granja" tomará el doble de tiempo que solo "granja". A la larga es cierto también con intentos comprimidos.

Todo el mundo conoce la tabla hash y sus usos, pero no es exactamente el tiempo de búsqueda constante, depende de qué tan grande es la tabla hash, la complejidad computacional de la función hash.

La creación de grandes tablas hash para una búsqueda eficiente no es una solución elegante en la mayoría de los escenarios industriales donde incluso latencia / escalabilidad pequeñas son importantes (por ejemplo, el comercio de alta frecuencia). Debe preocuparse por la optimización de las estructuras de datos en cuanto al espacio que ocupa en la memoria para reducir el error de caché.

Un buen ejemplo en el que mejor se adapta a los requisitos es el middleware de mensajería. Tiene un millón de suscriptores y editores de mensajes en varias categorías (en términos JMS: temas o intercambios), en tales casos, si desea filtrar mensajes basados en temas (que en realidad son cadenas), definitivamente no desea crear una tabla hash para el millón de suscripciones con millones de temas. Un mejor enfoque es almacenar los temas en trie, de modo que cuando el filtrado se realiza en función de la coincidencia de temas, su complejidad es independiente del número de temas / suscripciones / editores (solo depende de la longitud de la cadena). Me gusta porque puede ser creativo con esta estructura de datos para optimizar los requisitos de espacio y, por lo tanto, tiene menos errores de caché.