construir un número único para una cadena en Java

Question

Tenemos un requisito de lectura / escritura de más de 10 millones de cuerdas en un archivo. Además no queremos duplicados en el archivo. Dado que las cadenas se vuelcan en un archivo tan pronto como se leen no estamos manteniendo en la memoria.

No se puede utilizar código hash debido a colisiones en el código hash debido a que podríamos perder una cadena como duplicado. Otros dos enfoques que he encontrado en mi googlear:

1.Utilice un mensaje como el algoritmo de resumen MD5 -., Pero que podría ser demasiado costoso para calcular y almacenar

2.Use una suma de comprobación algoritmo. [No estoy seguro de si esto produce una clave única para un String puede alguien confirmar por favor]

¿Hay algún otro método disponible,. Gracias.

Answer 1

Si estás bien con un riesgo microscópico de las colisiones, se podría utilizar un poco de función hash como MD5 como usted sugiere, y se basan en los valores hash.

Otra alternativa, posiblemente con una huella de memoria más grande, es almacenar el, cadenas ya se encuentran, en un trie (un tipo especial de árbol).

---

Actualización: Otra alternativa, sería utilizar un Bloom filtro . Esto, sin embargo, todavía se basa en hashing pero se pueden ajustar para tener un arbitrariamente pequeña probabilidad de colisiones.

Answer 2

El almacenamiento de 10 millones de cuerdas en la memoria es de hecho mucho, por lo que entiendo la razón para escribirlo en el archivo de inmediato en lugar de almacenar en, por ejemplo un TreeSet<String> principio, pero donde le gustaría para almacenar los 10 millones teclas numéricas únicas que desea comparar con? Cuando se desea mantenerlo único y numérica (que tiene mucho más escasa base / base de letras), no se puede hacer que la clave más corta que la propia cadena ya está, por lo que no se ahorrará ningún recuerdo. O tal vez al más alto con compresión de datos como GZIP, pero esto sólo añadiría un montón de gastos generales. MD5 también es inadecuado ya que dos cadenas diferentes pueden producir el mismo hash.

Realmente no ven ninguna solución mejor para esto que el uso de un RDBMS decente (base de datos SQL) en el que se establece la columna como UNIQUE y manejar la violación de restricción en consecuencia. Un RDBMS está muy optimizado para este tipo de tareas.

Si realmente no se puede considerar una base de datos, entonces usted necesita para volver a leer el archivo para cualquier entrada existente antes de la escritura / ras. Tal vez no es muy rápido, pero ciertamente eficiente de la memoria.

Answer 3

No hay manera de hacer una función que produciría una clave única para una cadena, que es más corta que la cadena.
Hay estructuras de datos que pueden resolver su tarea. Árbol B podría encajar si los datos están lo suficientemente grande. Dependiendo de la naturaleza de su entrada, puede haber maneras más eficaces.

Answer 4

eliminación de duplicados de forma fiable es casi tan difícil como la clasificación del archivo. Como otra respuesta indica, no se garantiza ninguna forma de detectar con precisión los duplicados sin mantener una copia completa de cada cadena en la memoria, lo que parece ser exactamente lo que estamos tratando de evitar.

Se podría mantener una en memoria o en el disco índice de hashcodes, y utilizar estos para recuperar cadenas reales de almacenamiento de archivos para la comparación, pero esto sería esencialmente duplicar lo que una base de datos sería capaz de hacer por usted.

Una alternativa es la post-procesar el archivo una vez que esté completo. El comando UNIX especie es bastante bueno en archivos de gran tamaño ( Cómo ? podría ordenar el comando UNIX Ordenar un archivo muy grande ), así que era de esperar el enfoque estándar de línea de comandos de UNIX para el trabajo razonablemente:

    sort my-file-of-strings.txt | uniq > my-filtered-file-of-strings.txt

(Tenga en cuenta que los archivos tienen que ser ordenados primero antes de pasar a uniq para eliminar duplicados).

Si usted no tiene estas herramientas (o equivalentes) disponibles, entonces siempre se puede tratar de implementar alguna variante de un tipo de fusión externo a sí mismo.

Answer 5

Si las cadenas son de un grupo fijo de posibles cadenas (N), entonces usted puede utilizar hash perfecta mínima para crear una matriz 0 ... N-1. Un cero en la ranura determinada por el medio de la función hash perfecta la cadena no se ha visto hasta ahora.

De lo contrario, el único medio corrigen con eficacia fuera de mucho de la memoria y las soluciones sugeridas hasta ahora es volver a leer el archivo antes de decidirse a escribir la cadena a la misma.

Se podría hacer esto lo más eficientemente posible por porciones de asignación de memoria del archivo.

Answer 6

Realmente creo que la mejor solución es - como ya se ha sugerido otra persona - para utilizar una base de datos.

Si por alguna razón no se puede utilizar una base de datos, se puede seguir utilizando un código hash. Seguro que habrá colisiones. Sólo tiene que añadir algo de código para que cuando se detecta un código hash duplicado, su programa comprueba el archivo para determinar si se trata de un duplicado genuino o una colisión.