tries - Necesita una manera eficiente de almacenar toneladas de cadenas(fue: implementación de HAT-Trie en Java)
trie significado (4)
El trie parece una muy buena idea para tus limitaciones.
Una alternativa de "pensamiento fuera de la caja":
Si puede permitirse alguna probabilidad de responder "presente" a una cadena que está ausente
EDITAR: si puede permitirse falsos positivos, use un filtro Bloom como lo sugiere WizardOfOdds en los comentarios.
Para k = 1, un filtro Bloom es como una tabla hash sin las claves: cada "cubo" es simplemente un booleano que indica si estaba presente al menos una entrada con el mismo hash. Si el 1% de falsos positivos es aceptable, su tabla hash puede ser tan pequeña como aproximadamente 100 * 20 millones de bits o aproximadamente 200 MiB. Para 1 de cada 1000 falsos positivos, 2GiB.
Usar varias funciones hash en lugar de una puede mejorar la tasa de falsos positivos para la misma cantidad de bits.
Estoy trabajando con un conjunto grande (5-20 millones) de claves String (longitud promedio de 10 caracteres) que debo almacenar en una estructura de datos en memoria que admite la siguiente operación en tiempo constante o casi constante:
// Returns true if the input is present in the container, false otherwise
public boolean contains(String input)
El Hashmap de Java está demostrando ser más que satisfactorio en lo que respecta al rendimiento, pero ocupa mucha memoria. Estoy buscando una solución que sea eficiente desde el punto de vista de la memoria y aún así soporte un rendimiento que sea decente (comparable o casi tan bueno como el hashing).
No me importan los tiempos de inserción / eliminación. En mi aplicación, realizaré solo inserciones (solo en el momento del inicio) y, posteriormente, solo consultaré la estructura de datos utilizando el método contains durante la vida de la aplicación.
Leí que la estructura de datos de HAT-Trie está más cerca de mis necesidades. Me pregunto si hay una biblioteca que tiene una implementación.
Otras sugerencias con sugerencias para implementaciones son bienvenidas.
Gracias.
Google abre una publicación de blog sobre los intentos de HAT en Java . Pero no veo cómo esto resolverá su problema directamente: la estructura es un trie superficial sobre los prefijos de las claves, con las hojas siendo tablas que contienen los sufijos de todas las claves con el prefijo dado. Entonces, en total, tienes muchas tablas hash que almacenan todas las claves que están en tu hashtable grande actual (quizás guardando algunos bytes por clave en general debido a los prefijos comunes). De cualquier manera, necesita una tabla hash más eficiente en el uso del espacio que la Java Java predeterminada, o la sobrecarga por objeto le golpeará igual de mal. Entonces, ¿por qué no comenzar con una clase de tabla hash especializada solo para claves de cadena, si toma esta ruta, y preocuparse por la parte solamente si todavía parece valer la pena entonces?
Para la eficiencia del espacio, la búsqueda O (log (n)) y el código simple, intente la búsqueda binaria en una matriz de caracteres. 20 millones de claves de longitud promedio 10 hacen 200 millones de caracteres: 400 MB si necesita 2 bytes / char; 200 MB si puede salirse con la suya 1. Además de esto, debe representar de alguna manera los límites entre las teclas de la matriz. Si puede reservar un carácter separador, esa es una forma; de lo contrario, podría usar una matriz paralela de compensaciones int.
La variante más simple usaría una matriz de cadenas, a un alto costo de espacio por sobrecarga por objeto. Todavía debería vencer a una tabla hash en eficiencia espacial, aunque no tan impresionante.
Similar a un trie es un árbol de búsqueda ternario, pero un árbol de búsqueda ternario tiene la ventaja de usar menos memoria. Puedes leer sobre árboles de búsqueda ternarios here , here y here . También está aquí uno de los principales artículos sobre el tema de Jon Bentley y Robert Sedgewick. También habla sobre ordenar cadenas rápidamente, así que no te dejes llevar por eso.