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

Question

Tenemos un requisito de leer/escribir más de 10 millones de cadenas en un archivo. Además, no queremos duplicados en el archivo. Como las cuerdas se enjuagarán en un archivo tan pronto como se lean, no lo mantendremos en la memoria.

No podemos usar hashcode debido a las colisiones en el código hash debido a que podríamos perder una cadena como duplicada. Otros dos enfoques que encontré en mi Google:

1.Utilice un algoritmo de resumen de mensaje como MD5, pero podría ser demasiado costoso de calcular y almacenar.

2.Utilice un algoritmo de suma de comprobación. [No estoy seguro si esto produce una clave única para una cadena- ¿alguien puede confirmar?]

¿Hay algún otro enfoque disponible? Gracias.

Answer 1

Si está de acuerdo con un riesgo microscópico de colisiones, podría utilizar alguna función hash como MD5 como sugiere, y confiar en los hash.

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

---

Actualización: Otra alternativa sería utilizar un Bloom filter. Sin embargo, esto todavía depende del hash, pero puede ajustarse para tener una probabilidad arbitrariamente pequeña de colisión.

Answer 2

Almacenar 10 millones de cadenas en la memoria es de hecho mucho, así que entiendo la razón para escribirlo en el archivo inmediatamente en lugar de almacenarlo en, por ejemplo, a TreeSet<String> primero, pero donde le gustaría almacenar los 10 millones de claves numéricas únicas con las que desea comparar? Cuando desee mantenerlo único y numérico (que tiene una base/raíz mucho menor que las letras), no puede hacer que la clave sea más corta que la cadena misma, por lo que no guardará ninguna memoria. O tal vez en el nivel más alto con la compresión de datos como GZIP, pero esto solo agregaría muchos gastos generales. MD5 también es inapropiado ya que dos cadenas diferentes pueden producen el mismo hash.

Realmente no veo una mejor solución para esto que usar un RDBMS decente (base de datos SQL) en el que establece la columna como UNIQUE y maneja la violación de restricción en consecuencia. Un RDBMS está altamente optimizado para este tipo de tareas.

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

Answer 3

No hay forma de crear una función que produzca una clave única para una cadena, que es más corta que esa cadena.
Existen estructuras de datos que pueden resolver su tarea. B-tree podría caber si tu información es lo suficientemente grande. Dependiendo de la naturaleza de su información, puede haber formas más efectivas.

Answer 4

Si las cadenas provienen de un grupo fijo de cadenas posibles (N), entonces puede usar hash perfecto mínimo para crear una matriz 0 ... N-1. Un cero en la ranura determinado por la función hash perfecta significa que la cadena no se ha visto hasta ahora.

De lo contrario, el único medio eficazmente correcto fuera de mucho de memoria y las soluciones sugeridas hasta el momento es volver a leer el archivo antes de decidir escribirle la cadena.

Puede hacer esto de la manera más eficiente posible mediante el mapeo de memoria de partes del archivo.

Answer 5

La eliminación confiable de duplicados es casi tan difícil como ordenar el archivo. Como indica otra respuesta, no existe una forma garantizada de detectar con precisión los duplicados sin guardar una copia completa de cada cadena en la memoria, que parece ser exactamente lo que intenta evitar.

Puede conservar un índice de hashcodes en memoria o en disco, y usarlos para recuperar cadenas reales del almacenamiento de archivos para comparar, pero esto esencialmente duplicaría lo que una base de datos podría hacer por usted.

Una alternativa es procesar el archivo una vez que se haya completado. El comando sort UNIX es bastante bueno en archivos de gran tamaño (How could the UNIX sort command sort a very large file?), así que esperaría que el enfoque de línea de comandos estándar de UNIX para trabajar 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 no tiene estas herramientas (o equivalentes) disponibles, entonces siempre puede intentar implementar alguna variante de una clasificación de combinación externa usted mismo.

Answer 6

Realmente creo que la mejor solución es, como alguien más ya sugirió, usar una base de datos.

Si por alguna razón no puede usar una base de datos, puede usar un código hash. Claro que habrá colisiones. Simplemente agregue un código para que cuando detecte un código hash duplicado, su programa verifique el archivo para determinar si es un duplicado genuino o una colisión.