Filtru Bloom
Un filtru Bloom este o structură de date care permite calculatoarelor să vadă dacă un anumit element apare într-un set. Filtrele Bloom utilizează funcții hash pentru a face acest lucru. Pentru fiecare element adăugat, se calculează o valoare hash. Atunci când se adaugă un nou element, valoarea hash a acestuia este comparată cu cea a celorlalte elemente din set. Un filtru Bloom este o structură de date probabilistică. Este posibil să se obțină un fals pozitiv, dar nu și un fals negativ. Cu alte cuvinte, o interogare returnează fie "posibil în set", fie "cu siguranță nu este în set". Elementele pot fi adăugate la set, dar nu și eliminate. Pentru fiecare element adăugat, crește probabilitatea de a obține un fals pozitiv.
Edward Bloom a propus filtrul Bloom în 1970. În articol, Bloom presupune că există un algoritm pentru a elimina cuvintele de la sfârșitul unei linii. Conform exemplului, majoritatea cuvintelor au modele simple de cratimă. Dar aproximativ 10% dintre cuvinte necesită căutări consumatoare de timp pentru a prelua regula corectă. Cazul său a fost acela de a despărți prin cratimă aproximativ 500.000 de cuvinte. El a văzut că utilizarea tehnicilor "normale" de hashing fără erori, care stochează modelele de cratimă, ar necesita o cantitate mare de memorie. El a constatat că, folosind tehnica sa, ar putea elimina majoritatea căutărilor. De exemplu, o zonă de hașurare de numai 15% din dimensiunea necesară pentru o hașurare ideală fără erori elimină totuși 85% din accesările pe disc.
În general, sunt necesari mai puțin de 10 biți pe element pentru o probabilitate de 1% de fals pozitiv, indiferent de mărimea sau de numărul de elemente din set.
Întrebări și răspunsuri
Î: Ce este un filtru Bloom?
R: Un filtru Bloom este o structură de date care permite calculatoarelor să vadă dacă un anumit element apare într-un set. În acest scop, utilizează funcții hash pentru a face acest lucru, calculând valoarea hash a fiecărui element adăugat și comparând-o cu celelalte elemente din set.
Î: Ce tip de structură de date este un filtru Bloom?
R: Un filtru Bloom este o structură de date probabilistică, ceea ce înseamnă că există posibilitatea de a obține rezultate pozitive false, dar nu și negative false.
Î: Cine a propus filtrul Bloom?
R: Edward Bloom a propus filtrul Bloom în 1970.
Î: Care a fost exemplul dat de Edward pentru utilizarea tehnicii sale?
R: Exemplul lui Edward a constat în despărțirea prin cratimă a aproximativ 500 000 de cuvinte; a constatat că, folosind tehnica sa, a putut elimina majoritatea căutărilor și a redus accesările pe disc cu 15%.
Î: Câți biți pe element sunt necesari pentru o probabilitate de 1% de fals pozitiv?
R: Mai puțin de 10 biți pe element sunt necesari pentru o probabilitate de 1% de fals pozitiv, indiferent de mărimea sau de numărul de elemente din set.
Î: Este posibil să se elimine elemente dintr-un filtru bloom după ce au fost adăugate?
R: Nu, elementele pot fi doar adăugate la set, dar nu și eliminate.
Î: Adăugarea mai multor elemente crește sau scade probabilitatea de a obține un rezultat fals pozitiv?
R: Adăugarea mai multor elemente crește probabilitatea de a obține un rezultat fals pozitiv.
