Efficiente appartenenza al set con filtro Bloom

Il filtro Bloom è una struttura di dati progettata per verificare se un elemento è un membro di un insieme. Viene utilizzato in varie applicazioni come il controllo ortografico, l'indicizzazione di database e i router di rete che richiedono un metodo rapido ed efficiente in termini di memoria per testare l'appartenenza al set. I filtri Bloom sono strutture dati probabilistiche, il che significa che potrebbero generare falsi positivi ma mai falsi negativi.

Prima di spiegare Bloom Filter, capiamo prima l'hashing. L'hashing è una tecnica per ridurre una grande quantità di dati in un valore hash più piccolo di dimensione fissa, con una piccola probabilità che due valori di dati generino lo stesso valore hash (collisione).

Implementazione

I filtri Bloom sono implementati come un array di N bit, tutti impostati a 0 all'inizio. L'array di bit rappresenta l'insieme e ogni elemento viene sottoposto a hash K volte utilizzando diverse funzioni hash. I valori hash K risultanti vengono utilizzati per impostare i bit corrispondenti nell'array di bit su 1.

Per verificare l'appartenenza, l'elemento viene nuovamente sottoposto a hash K volte e vengono controllati i bit risultanti nell'array di bit. Se tutti i K bit sono impostati su 1, l'elemento è considerato un membro dell'insieme, sebbene sia possibile che l'elemento non sia stato effettivamente inserito nell'insieme, risultando in un falso positivo.

La probabilità di un falso positivo è determinata dalla dimensione dell'array di bit, N, e dal numero di funzioni hash, K.

Caso d'uso

Supponiamo di dover progettare un sistema di registrazione degli utenti che consenta agli utenti di registrarsi con un nome utente e una password univoci. Per verificare se un nome utente scelto è disponibile, possiamo attraversare l'intero database e verificare la presenza di una corrispondenza, ma questo è un metodo lento e ad alta intensità di memoria. Una soluzione migliore è utilizzare un filtro Bloom.

Il filtro Bloom è inizializzato con un ampio array di bit e un insieme di funzioni hash. L'array di bit è inizialmente impostato su tutti zeri e le funzioni hash vengono selezionate per distribuire uniformemente i valori di input nell'array di bit.

Quando un utente tenta di registrarsi, il nome utente scelto viene passato attraverso le funzioni hash, che generano un insieme di indici nell'array di bit. Il sistema controlla quindi il valore dei bit in corrispondenza di questi indici. Se tutti i bit sono impostati a uno, il sistema presuppone che il nome utente sia già in uso e nega la registrazione. Se uno qualsiasi dei bit è impostato a zero, il sistema può confermare che il nome utente non è in uso e procede con la registrazione.

Al termine della registrazione, il sistema imposta su uno i bit negli indici generati dalle funzioni hash, indicando che il nome utente è ora in uso.

Questo è un semplice esempio di come è possibile utilizzare un filtro Bloom per verificare in modo efficiente l'appartenenza a un sistema di registrazione del nome utente. Sebbene esista una piccola probabilità di un falso positivo, l'uso di un controllo secondario può mitigare efficacemente questa limitazione e garantire l'accuratezza dei risultati.

Esempio

Eseguiamo un'implementazione di esempio di un filtro Bloom in un sistema di registrazione del nome utente.

Consideriamo un Bloom Filter con un bit array di lunghezza 10 e tre funzioni hash.
Inizialmente, tutti i bit dell'array di bit sono impostati su 0.

Bit Array: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

h1("Rohit") = 8
h2("Rohit") = 2
h3("Rohit") = 7

Al termine della registrazione, il sistema imposta su uno i bit negli indici generati dalle funzioni hash.

Bit Array: [0, 0, 1, 0, 0, 0, 0, 1, 1, 0]

h1("Mohit") = 2
h2("Mohit") = 8
h3("Mohit") = 5

Al termine della registrazione, il sistema imposta su uno i bit negli indici generati dalle funzioni hash.

Bit Array: [0, 0, 1, 0, 0, 1, 0, 1, 1, 0]

h1("Rahul") = 2
h2("Rahul") = 5
h3("Rahul") = 7

Questo è un esempio di falsi positivi che possono verificarsi quando si utilizzano i filtri Bloom. Per ovviare a questo, il sistema esegue un controllo secondario sul database per confermare la disponibilità del nome utente.

Pro e contro

Uno dei principali vantaggi del filtro Bloom è la sua efficienza in termini di spazio. Utilizza molta meno memoria rispetto ad altre strutture di dati, come tabelle hash o alberi di ricerca binari, per memorizzare gli elementi impostati. Un altro vantaggio è il suo funzionamento a tempo costante. La complessità temporale del test di appartenenza è O(K), sia che K sia il numero di funzioni hash, indipendentemente dal numero di elementi nell'insieme.

Tuttavia, la natura probabilistica del filtro Bloom significa che non è adatto per applicazioni in cui i falsi positivi non sono accettabili. In tali casi, dovrebbero essere utilizzate strutture di dati alternative, come tabelle hash o alberi di ricerca binari.

Il tasso di falsi positivi di un filtro Bloom può essere ridotto aumentando la dimensione dell'array di bit o il numero di funzioni hash. Tuttavia, l'aumento della dimensione dell'array di bit aumenterà anche i requisiti di memoria del filtro. D'altra parte, l'aumento del numero di funzioni hash aumenterà la complessità temporale del test di appartenenza. Trovare il compromesso ottimale tra spazio e complessità temporale è una considerazione importante quando si utilizzano i filtri Bloom.

Usi comuni

I filtri Bloom sono utilizzati in una varietà di applicazioni di progettazione di alto livello grazie alla loro efficienza e natura probabilistica. Alcuni dei casi d'uso comuni sono: -
Motori di ricerca Web : i filtri Bloom possono essere utilizzati per memorizzare gli URL delle pagine che sono già state sottoposte a scansione, impedendo ai motori di ricerca di ripetere la scansione delle pagine che sono già state visitate.
Indicizzazione del database : utilizzo dei filtri Bloom per verificare se un database contiene un record specifico, evitando la necessità di una scansione completa della tabella.
Routing di rete : filtraggio dei pacchetti di rete controllando se i loro indirizzi di destinazione appartengono a un insieme di indirizzi autorizzati.
Controllo ortografico : controllo dell'esistenza di una parola in un dizionario di grandi dimensioni.