¿Cómo elijo entre una tabla de hash y un trie (árbol de prefijos)?

Question

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 una sobre la otra? Desde mi punto de vista ingenuo, parece que el uso de un trie tiene una sobrecarga adicional ya que no se almacena como una matriz, pero en términos de tiempo de ejecución (suponiendo que la clave más larga es la palabra más larga en inglés) puede ser esencialmente O (1) (en relación con el límite superior). Tal vez la palabra más larga en inglés es de 50 caracteres?

Las tablas hash son de búsqueda instantánea una vez que obtenga el índice . La clave para obtener el índice, sin embargo, parece que podría dar fácilmente cerca de 50 pasos.

¿Puede alguien proporcionarme una perspectiva más experimentada sobre esto? Gracias!

Answer 1

Ventajas de los intentos:

Lo básico:

• Tiempo de búsqueda O (k) predecible donde k es el tamaño de la clave
• La búsqueda puede llevar menos de k tiempo si no está allí
• Soporta recorrido transversal
• 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, apuntando en otra parte al trie anterior. Esto puede ser útil para la concurrencia, múltiples versiones simultáneas de una tabla, etc.
• Un trie inmutable es compresible. Es decir, puede compartir la estructura de los sufijos también, mediante la comprobación de hash.

Ventajas de las tablas hash:

• Todo el mundo sabe hashtables, ¿verdad? Su sistema ya tendrá una buena implementación bien optimizada, más rápida que los intentos para la mayoría de los propósitos.
• Sus llaves no necesitan tener ninguna estructura especial.
• Más eficiente en espacio que la estructura de enlace vinculada obvia ( vea los comentarios a continuación )

Answer 2

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

Answer 3

Todo el mundo conoce la tabla hash y sus usos, pero no es exactamente el tiempo de búsqueda constante, depende del tamaño de la tabla hash, la complejidad computacional de la función hash.

La creación de enormes tablas hash para una búsqueda eficiente no es una solución elegante en la mayoría de los escenarios industriales donde incluso la latencia / escalabilidad son importantes (por ejemplo, operaciones de alta frecuencia). Debe preocuparse por las estructuras de datos que deben optimizarse para el espacio que ocupa en la memoria también para reducir la falta de caché.

Un ejemplo muy bueno donde trie se adapta mejor 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 esos casos, si desea filtrar mensajes según temas (que en realidad son cadenas), definitivamente no desea crear una tabla hash Por 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, perder menos caché.

Answer 4

Usa un árbol:

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

Answer 5

La implementación de

HashTable es eficiente en términos de espacio en comparación con la implementación básica de Trie . Pero con las cuerdas, el pedido 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á realizando operaciones basadas en orden lexográfico (como búsqueda parcial, todas las cadenas con el prefijo dado, todas las palabras en orden), debe usar Tries. Para solo búsqueda, se debe usar HashTable (como podría decirse, da un tiempo de búsqueda mínimo).

P.S .: Aparte de estos, Los árboles de búsqueda ternarios (TST) serían una excelente opción. Su tiempo de búsqueda es más que HashTable, pero es eficiente en todas las demás operaciones. Además, es más eficiente en espacio que los intentos.

Answer 6

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

Esto es asumiendo que tienes una buena función hash. Si no quieres " granja " y " animales de granja " para hacer un hash con el mismo valor, entonces la función hash tendrá que usar todos los bits de la clave, y así hashing " animales de granja " debería tomar aproximadamente el doble de tiempo que " granja " (a menos que esté en algún tipo de escenario hash rodante, pero también hay escenarios de ahorro de operaciones similares con intentos). Y con un intento de vainilla, queda claro por qué insertar " animales de granja " Tardará aproximadamente el doble de tiempo que "granja". A largo plazo, también es cierto con intentos comprimidos.

Answer 7

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á un O (1) para búsqueda y inserción, pero primero debe calcular el hash basándose 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 un poco más de sobrecarga desde la perspectiva de los datos, pero puede elegir un trie comprimido que lo pondrá de nuevo, más o menos en un empate con la tabla hash.

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

Y si lo haces solo por diversión, implementar un trie pondría un buen domingo por la tarde.

Answer 8

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 un trie varía según los datos.