example - hashtable java tutorialspoint

¿Cómo implementar un diccionario(Trie vs HashTable y problemas importantes)?

Question

He encontrado varias preguntas y artículos que dicen que la implementación del diccionario en java se realiza mejor con intentos. Pero la mayoría de ellos no abordaron temas importantes, por lo que yo vi. Entonces, la siguiente es una tarea del mundo real:

Supongamos que necesito implementar un diccionario (digamos algo como Lingvo, pero más simple) usando java. Para mi tarea particular, es necesario almacenar definiciones de palabras y realizar búsquedas rápidas en el diccionario.

Por favor, responda a las siguientes preguntas:

• ¿Qué estructura de datos debo usar entonces (Trie o HashTable)?
• ¿Cómo debería organizarse (búsqueda, conducto de datos) si necesito que el diccionario no distinga mayúsculas de minúsculas?
• ¿Qué sucede si quiero que (búsqueda, diccionario) distinga mayúsculas y minúsculas?

PD: los ejemplos de código son muy apreciados. :)

Gracias por las respuestas por adelantado.

ACTUALIZACIÓN : si estamos hablando de implementaciones estándar de DS en java, ¿es cierto que HashTable será la mejor para esta tarea en particular? ¿Por qué no HashMap, TreeMap o LinkedHashMap?

Answer 1

Implementación de diccionario en Java, definitivamente las colecciones de hash son la mejor apuesta.

Con respecto a HashMap o HashTable : Principalmente, si su clase se usa de manera multiproceso, entonces tiene que usar HashTable , de lo contrario, HashMap es la mejor opción.

HashMap vs TreeMap : si necesita una orden de inserción en la colección, tenemos que usar TreeMap .

HashMap vs LinkedHashMap : la implementación de LinkedHashMap difiere de HashMap en que mantiene una lista con enlaces HashMap que se ejecuta en todas sus entradas. Esta lista enlazada define el orden de iteración, que normalmente es el orden en que se insertaron las claves en el mapa (orden de inserción). Tenga en cuenta que el orden de inserción no se ve afectado si una clave se reinserta en el mapa. (Una clave k se reinserta en un mapa m si m.put(k, v) se invoca cuando m.containsKey(k) devolverá verdadero inmediatamente antes de la invocación).

Answer 2

Quiero abordar solo un punto en tu pregunta:

Un trie no es una estructura de datos de diccionario de propósito general. El motivo es que trie es un árbol de búsqueda especializado para la búsqueda de (sub) cadenas. En general, estará más interesado en los árboles de búsqueda general, por ejemplo, árboles de búsqueda binarios o árboles B-trees

Todas estas implementaciones se basan en un ordenamiento de los elementos del diccionario, y todas ellas tienen un tiempo de ejecución de caso promedio logarítmico y de caso más desfavorable para operaciones comunes.

Una tabla hash , por el contrario, no requiere un ordenamiento relativo de los elementos. En su lugar, requiere que los elementos sean hashable y la igualdad comparable . La característica del caso más desfavorable de las características comunes de la tabla hash es mucho peor que para los árboles, es decir, lineal en el número de elementos.

Sin embargo, con un poco de cuidado, el promedio de las operaciones de tablas hash puede hacerse constante (es decir, independiente del tamaño del contenedor). Además, se puede demostrar que las operaciones más lentas son extremadamente raras.

En la práctica, esto significa que, excepto en casos de uso muy especializados, las tablas hash superan los diccionarios basados ​​en árboles.

La desventaja de esto es que las tablas hash imponen un orden de apariencia arbitraria en sus elementos. Si está interesado en ordenar los elementos de su diccionario en orden, las tablas hash no son para usted.

(Hay otras implementaciones interesantes de diccionarios, p. Ej., Listas de salto que compiten con árboles de búsqueda e implementaciones probabilísticas como el filtro Bloom ).

Una implementación basada en trie solo se puede utilizar si está tratando con un diccionario de valores de cadena, en cuyo caso a menudo es una buena opción, en particular si muchas cadenas en el diccionario comparten prefijos comunes y son bastante cortas.

Answer 3

EDITAR dejar de subirvotando esto: He leído mal la pregunta. El OP no busca un diccionario para verificar la ortografía de palabras / sugerencias / tipografía anticipada-búsqueda / autocompletar / lo que sea (lo que pensé era lo que buscaba). El OP es después de una asignación de clave / valor donde para cada palabra hay una definición.

Habiendo trabajado en diccionarios, puedo decirle que está tomando el enfoque equivocado.

No es tan simple como una elección entre una tabla hash o un trie.

Mencionas Lingvo: es mucho más que una mesa.

¿Quieres que se le ofrezcan sugerencias para igualar? Es posible que luego necesite elementos como generar permutaciones sobre lo que el usuario ingresó y para cada permutación ver si existe en el dico: si lo hace, entonces deberá calcular su ''Distancia de edición de Levenhstein y sugerir primero las palabras que tienen la LED más corto.

¿Desea que las coincidencias más probables se completen / sugieran automáticamente (como lo hace Google)? Entonces necesitarías una estructura de datos muy avanzada como un árbol BK (básicamente un árbol de LED si lo entiendo correctamente).

¿Cuántas palabras tendrás en tu diccionario? No podrá usar un diccionario hecho de 400 000 palabras usando Cadenas y otros objetos / estructuras de datos Java pesados ​​sin un impacto de rendimiento serio (una vez más: un diccionario es más que una tabla hash, un diccionario suele incluir varias estructuras de datos) . Esto no encajará fácilmente en la memoria de la computadora de sus usuarios. Existen formas conocidas de buscar palabras para almacenar palabras en las que cada palabra puede incluir menos de 15 bits por palabra (menos de 15 bits por palabra, se lee correctamente).

Además de eso, es posible que desee hacer una sugerencia basada en la fonética: por ejemplo, utilizando un mapeo de doble metáfono.

Un diccionario, como en un "diccionario de palabras", es mucho más que una simple tabla de claves / valores. Realmente es una bestia complicada debido a las características que el usuario debe hacer, excepto y debido a la cantidad de datos involucrados. Solo inglés simple + algunos dominios especializados terminologías, médico, comp-sci, lo que sea. le dará cientos de miles de datos: intente poner eso en un HashMap de Java y ... ¡Kaboom!