Algoritmo di compressione con perdita di dati sparse

Quello che stai cercando è chiamato hash perfetto minimo . Se hai, ad esempio, 256 elementi da uno spazio dati di 1024 bit di larghezza, un hash come MD5 li assocerebbe agli hash a 128 bit, possibilmente con collisioni.

Se hai preso gli ultimi 8 bit dell'MD5, otterresti comunque un hash (di sorta), con un rischio molto più grande di collisioni.

Un hash perfetto minimo è una funzione che mappa i tuoi token 256 nei numeri da 0 a 255, in tal modo spremendo gli otto bit di informazioni di cui hai bisogno.

Un banale generatore di "hash" sarebbe

if (token == token1) { return hash1; }
if (token == token2) { return hash2; }

e ha complessità O (n). Mi sembra di ricordare che il generatore ideale ha una complessità molto più bassa di O (log2 (n)).

La ricerca casuale è in effetti un metodo per generare una tale funzione di hash.

Probabilmente vorrai controllare strumenti come questo .

Dato che permetti falsi positivi, non hai bisogno di un hash perfetto. Invece, puoi utilizzare un filtro di fioritura . Un filtro bloom è costituito da un vettore bit e da un set di diverse funzioni hash.

Per aggiungere un elemento al filtro di fioritura, hai l'elemento con ogni funzione di hash e usa ciascun hash come indice per il vettore di bit. Quindi imposta ciascun bit indirizzato su true.

Per verificare se un elemento è nell'insieme, si usano le funzioni hash per recuperare i bit corrispondenti dal vettore bit. Se tutti questi bit sono veri, l'elemento era probabilmente parte dell'input.

Questo approccio è abbastanza veloce, poiché le funzioni di hash possono essere molto semplici. È possibile utilizzare una famiglia di funzioni hash parametrizzate da alcune costanti per generare il set di funzioni hash. Insieme al vettore di bit, questi parametri costituiscono i dati memorizzati.

È importante scegliere una relazione sensata tra la dimensione dell'insieme di input n , la dimensione del vettore bit m , il numero di funzioni hash k e il tasso accettabile di falsi positivi p . La matematica pertinente è spiegata nell'articolo Wikipedia collegato. Ogni elemento di input influisce su k bit nel vettore di bit, indipendentemente dalle dimensioni dell'elemento, quindi è possibile risparmiare spazio quando si utilizzano solo poche funzioni di hash.

Mentre un filtro di fioritura consente di verificare se il set contiene un elemento, non è possibile enumerare tutti gli elementi in un set; questa informazione viene persa attraverso le funzioni hash.