forma eficiente de almacenar toneladas de cuerdas (era: aplicación HAT-Trie en Java)

Question

estoy trabajando con un gran conjunto (5-20 millones) de claves de cadena (longitud media de 10 caracteres) cual necesitará almacenar en una estructura de datos de memoria que soporta la operación siguiente en tiempo constante o casi en tiempo constante:

// Returns true if the input is present in the container, false otherwise 
public boolean contains(String input) 

Hashmap de Java está demostrando ser más que satisfactorio en cuanto a rendimiento se refiere, pero está tomando una gran cantidad de la 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 útil de la aplicación.

He leído que la estructura de datos de HAT-Trie es la más cercana para mis necesidades. Me pregunto si hay una biblioteca que tiene una implementación.

Otras sugerencias con sugerencias para implementaciones de bienvenida.

Gracias.

Answer 1

El trie parece una muy buena idea para sus limitaciones.

A "pensar fuera de la caja" alternativa:

si puede permitirse cierta probabilidad de responder "presente" para una cadena que está ausente

EDIT: si no puede pagar los falsos positivos, use un Bloom filter como lo sugiere WizardOfOdds en los comentarios.

Para k = 1, un filtro Bloom es como una tabla hash sin las teclas: cada "cubo" es simplemente un booleano que indica si había 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.

Answer 2

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 utilizaría una matriz de cadenas, a un alto costo de espacio por sobrecarga de objetos. Todavía debería vencer a una tabla hash en eficiencia espacial, aunque no tan impresionante.

Answer 3

Google abre una publicación de blog en HAT tries in 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?

Answer 4

Similar a un trie es un árbol de búsqueda ternario, pero un árbol de búsqueda ternario tiene la ventaja de utilizar menos memoria. Puede leer sobre los árboles de búsqueda ternarios here, here y here. También uno de los principales documentos sobre el tema por Jon Bentley y Robert Sedgewick es here. También habla sobre ordenar cadenas rápidamente, así que no te dejes llevar por eso.