¿La mejor estructura de datos para implementar un diccionario?

Question

¿Cuál sería la mejor estructura de datos para almacenar todas las palabras de un diccionario? Lo mejor que pude pensar fue usar un HashMap, que se asignará a un HashTable. Básicamente, dependiendo del primer personaje, obtendremos el HashTable asociado y luego, usando esto, podemos agregar las palabras que comiencen por ese carácter. A continuación, seleccionaremos una buena función hash basada en la cadena.

¿Hay un mejor enfoque?

Answer 1

Dependiendo de lo que quiera hacer, hay muchas buenas estructuras de datos.

Si solo quiere guardar las palabras y preguntar "¿está aquí esta palabra o no?", Una tabla de hash estándar sin otras maquinarias es un enfoque razonable. Si esa palabra está lista por adelantado, considere usar un perfect hash table para obtener un excelente rendimiento y uso del espacio.

Si desea poder comprobar si existe un prefijo dado mientras admite búsquedas rápidas, un trie es una buena opción, aunque puede ser un poco ineficiente en cuanto a espacio. También admite inserciones o eliminaciones rápidas. También permite la iteración en orden alfabético, lo que hashing no ofrece. Esta es esencialmente la estructura que ha descrito en su respuesta, pero dependiendo del caso de uso, otras representaciones de intentos podrían ser mejores.

Si además de lo anterior, usted sabe de hecho que la lista de palabras es fija, considere el uso de DAWG (gráfico de palabras acíclica dirigido), que es esencialmente un DFA de estado mínimo para el idioma. Es sustancialmente más compacto que el trie, pero admite muchas de las mismas operaciones.

Si desea un comportamiento similar al de un trie pero no quiere pagar una penalización de espacio enorme, el ternary search tree es otra opción viable, como es el radix tree. Estas son estructuras muy diferentes, pero pueden ser mucho mejores que el trie en diferentes circunstancias.

Si el espacio es una preocupación pero desea un trie, mire en la representación succinct trie, que tiene búsquedas más lentas pero casi teóricamente el uso de espacio óptimo. El enlace explica cómo se usa en JavaScript como una forma fácil de transmitir una gran cantidad de datos. Una representación compacta alternativa es double-array trie, aunque reconozco que sé muy poco al respecto.

Si desea utilizar el diccionario para operaciones como el corrector ortográfico donde necesita encontrar palabras similares a otras palabras, el BK-tree es una excelente estructura de datos a considerar.

Espero que esto ayude!