costruire un numero unico per una stringa in Java

Question

Abbiamo un requisito di lettura / scrittura di più di 10 milioni di stringhe in un file. Anche noi non vogliamo che i duplicati nel file. Dal momento che le corde sarebbero lavati in un file non appena vengono letti non stiamo mantenendo in memoria.

Non è possibile utilizzare codice hash a causa delle collisioni nel codice hash grazie al quale potremmo perdere una stringa come duplicato. Altri due approcci ho trovato nella mia googling:

1. Usare un messaggio digest algoritmo MD5 come -. Ma potrebbe essere troppo costoso per calcolare e memorizzare

2.Utilizzare un checksum algoritmo. [Non sono sicuro se questo produce una chiave unica per un String qualcuno può confermare prega]

C'è un altro approccio avaiable. Grazie.

Answer 1

Se stai bene con un rischio di collisioni microscopico, si potrebbe usare qualche funzione hash come MD5 come lei suggerisce, e si basano sugli hash.

Un'altra alternativa, possibilmente con un grande ingombro di memoria, è quello di memorizzare il, stringhe già incontrate, in un trie (un particolare tipo di albero).

---

Update: Ancora un'altra alternativa, sarebbe quella di utilizzare un Bloom filtro . Questo, tuttavia, si basa ancora sulla hashing, ma può essere regolata per avere un arbitrariamente piccola probabilità di collisioni.

Answer 2

Memorizzazione di 10 milioni di stringhe in memoria è davvero molto, quindi ho capito il motivo di scrivere a file immediatamente invece di memorizzare in es un TreeSet<String> prima, ma dove volete memorizzare i 10 milioni di tasti numerici uniche che si desidera confrontare con? Quando si desidera tenerlo Unique e numerico (che ha molto più piccolo di base / radice di lettere), non è possibile effettuare la chiave più corta della stringa stessa già è, in modo da non salvare qualsiasi memoria. O forse a più alto con la compressione dei dati, come GZIP, ma questo sarebbe solo aggiungere un sacco di spese generali. MD5 è anche inopportuno in quanto due differenti stringhe possono cedere lo stesso hash.

Io davvero vedere nessuna soluzione migliore per questo che utilizzare un RDBMS decente (database SQL) in cui si imposta la colonna come UNIQUE e gestire la violazione del vincolo di conseguenza. Un RDBMS è altamente ottimizzato per questo tipo di attività.

Se davvero non si può prendere in considerazione un database, allora avete bisogno di ri-leggere il file per qualsiasi voce esistente prima della scrittura / colore. Forse non è molto veloce, ma certamente efficiente della memoria.

Answer 3

Non v'è alcun modo per rendere una funzione che produrrebbe una chiave univoca per una stringa, che è più breve di quella stringa.
Ci sono strutture di dati che possono risolvere il vostro compito. B-tree potrebbe adattarsi se si dati è abbastanza grande. A seconda della natura del vostro ingresso, ci potrebbero essere modi più efficaci.

Answer 4

rimuovere i duplicati in modo affidabile è più o meno così difficile come l'ordinamento del file. Come un'altra risposta indica, non è garantito alcun modo di individuare con precisione i duplicati senza mantenere una copia completa di ogni stringa in memoria, che sembra essere esattamente quello che stai cercando di evitare.

Si potrebbe tenere un in-memoria o sul disco indice dei codici hash, e utilizzare questi per recuperare stringhe reali da archiviazione di file per il confronto, ma questo sarebbe essenzialmente duplicare ciò che una banca dati sarebbe in grado di fare per voi.

Un'alternativa è quella di post-elaborare il file una volta che è completo. Il comando UNIX ordinamento è abbastanza bravo a file di grandi dimensioni ( Come ? potrebbe il comando sort UNIX sorta un file molto grande ), quindi mi aspetto l'approccio della riga di comando UNIX standard al lavoro ragionevolmente:

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

(Si noti che i file devono essere ordinati prima di passare a uniq per rimuovere i duplicati).

Se non hai questi strumenti (o equivalenti) disponibili, allora si può sempre provare l'attuazione di una qualche variante di un merge esterna specie se stessi.

Answer 5

Se le stringhe sono da un pool fisso di possibili stringhe (N), quindi è possibile utilizzare minimo hashing perfetto per creare un array 0 ... N-1. Uno zero nella fessura determinato dal mezzo di funzione hash perfette la stringa non è stato visto finora.

In caso contrario, l'unico mezzo efficace corrette al di fuori di molto della memoria e le soluzioni suggerite finora è di ri-leggere il file prima di decidere di scrivere la stringa ad esso.

Si potrebbe fare questo nel modo più efficiente possibile, da porzioni di mappatura della memoria del file.

Answer 6

Credo davvero che la soluzione migliore è - come qualcun altro già suggerito - di utilizzare un database.

Se per qualche motivo non è possibile utilizzare un database, è comunque possibile utilizzare un codice hash. Certo ci saranno collisioni. Basta aggiungere un po 'di codice in modo che quando si rileva un codice hash duplicato, il tuo programma controlla il file per determinare se si tratta di un vero e proprio duplicato o una collisione.