Filtru Bloom

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 10 februarie 2020; verificările necesită 5 modificări .

Filtrul Bloom este o structură de date probabilistică inventată de Burton Bloom în 1970 [1] , care permite verificarea dacă un element aparține unei mulțimi . În acest caz, este posibil să obțineți un fals pozitiv (nu există niciun element în set, dar structura datelor raportează că este), dar nu un fals negativ .

Filtrul Bloom poate folosi orice cantitate de memorie , prestabilită de utilizator, și cu cât este mai mare, cu atât este mai puțin probabil să fie fals pozitiv. Operația de adăugare a elementelor noi la set este acceptată, dar nu ștergerea celor existente (cu excepția cazului în care se folosește modificarea cu contoare).

Descrierea structurii datelor

Filtrul Bloom este un bitmap de m biți . Inițial, când structura de date stochează setul gol , toți m biți sunt setați la zero. Utilizatorul trebuie să definească k funcții hash independente h 1 , …, h k , fiecare dintre ele mapează un set de elemente într-un set de putere m. (Cu alte cuvinte, funcția hash atribuie fiecărui element un număr de la 1 la m.) Pentru fiecare element e , biții matricei cu numere h 1 ( e ), ..., h k ( e ) egale cu valorile funcțiilor hash sunt setate la 1.

Pentru a verifica dacă elementul e aparține mulțimii elementelor stocate, este necesar să se verifice starea biților h 1 ( e ), …, h k ( e ). Dacă cel puțin unul dintre ei este egal cu zero, elementul nu poate aparține mulțimii (altfel, atunci când a fost adăugat, toți acești biți ar fi setați). Dacă toate sunt egale cu unul, atunci structura de date spune că e poate aparține mulțimii. În acest caz, pot apărea două situații: fie elementul aparține cu adevărat mulțimii, fie toți acești biți au fost setați întâmplător la adăugarea altor elemente, ceea ce este sursa fals pozitive în această structură de date.

Independenţa funcţiilor hash asigură probabilitatea minimă de repetare a indicilor h k ( e ) prin minimizarea numărului de biţi setat la 1 de mai multe ori. (Și aceasta este o sursă majoră de fals pozitive.)

Probabilitate fals pozitivă

Fie dimensiunea matricei de biți să fie egală cu m biți și sunt date k funcții hash. Să presupunem că mulțimea de funcții hash este aleasă aleatoriu, iar pentru orice element x , fiecare funcție hash h i îi atribuie unul dintre locurile din harta de biți cu probabilitate egală

\Pr(h_{i}(x)=p)={\frac {1}{m)),\quad p=1\ldots m,

și, în plus, valorile sunt variabile aleatoare independente colectiv (pentru a simplifica analiza ulterioară). $Salut x)$

Atunci probabilitatea ca o unitate să nu fie scrisă pe un bit p -al-lea în timpul operației de inserare a următorului element este egală cu

\Pr(h_{1}(x)\neq p\cap \ldots \cap h_{k}(x)\neq p)=\Pr(h_{i}(x)\neq p)^{k}= \left(1-{\frac {1}{m}}\right)^{k}.

Și probabilitatea ca bitul p --lea să rămână egal cu zero după introducerea a n elemente diferite x 1 , ..., x n în filtrul Bloom inițial gol este egală cu

\Pr \left(\forall i\in \{1\dots k\},\\forall j\in \{1\ldots n\},\h_{i}(x_{j})\neq p\right)=\left(1-{\frac {1}{m}}\right)^{kn}\aprox e^{-kn/m}

pentru m suficient de mare în vederea celei de-a doua limite remarcabile .

Un fals pozitiv este că pentru un element y care nu este egal cu niciunul dintre elementele inserate, toți k biți cu numere h i ( y ) vor fi non-zero, iar filtrul Bloom va răspunde în mod eronat că y este inclus în mulțime a elementelor inserate. Probabilitatea unui astfel de eveniment este aproximativ egală cu

(1-e^{-kn/m})^{k}.

Evident, această probabilitate scade odată cu creșterea m (dimensiunea matricei de biți) și crește odată cu creșterea n (numărul de elemente inserate). Pentru m și n fix , numărul optim k (numărul de funcții hash) care îl minimizează este

\textstyle k={\frac {m}{n}}\ln 2\approx 0{,}6931{\frac {m}{n}}.

În acest caz, probabilitatea unui fals pozitiv este egală cu

2^{{-k}}\aprox {0{,}6185}^{{m/n}}.

În consecință, rețineți că, pentru ca filtrul Bloom să suporte o probabilitate fals pozitivă mărginită dată, dimensiunea hărții de bit trebuie să fie liniar proporțională cu numărul de elemente inserate.

Proprietăți

Spre deosebire de multe alte structuri de date (cum ar fi tabelele hash ) care stochează și multe elemente, un filtru Bloom poate reprezenta setul universal al tuturor elementelor posibile. În acest caz, toți biții din harta sa de biți sunt egali cu unul.
Unirea și intersecția a două filtre Bloom de aceeași dimensiune și cu același set de funcții hash pot fi implementate prin operațiuni SAU și AND pe bitmap-urile lor.

Aplicație

În comparație cu tabelele hash, filtrul Bloom poate gestiona cu câteva ordine de mărime mai puțină memorie, sacrificând determinismul. Este folosit de obicei pentru a reduce numărul de solicitări de date inexistente într-o structură de date cu acces mai scump (de exemplu, situată pe un hard disk sau pe o bază de date de rețea), adică pentru a „filtra” cererile către aceasta.

Exemple de aplicații practice:

Proxy -ul Squid folosește filtre de înflorire pentru opțiunea de digerări în cache .
Google BigTable folosește filtre Bloom pentru a reduce numărul de accesări pe hard disk atunci când verifică existența unui anumit rând sau coloană într-un tabel al bazei de date. [2]
Programe de calculator pentru verificarea ortografiei.

Vezi și

Filtru de înflorire cu numărare

Note

↑ Bloom, Burton H. (1970), Space/time trade-offs in hash coding with allowable errors , Communications of the ACM vol. 13 (7): 422–426 , DOI 10.1145/362686.362692
↑ Bigtable: A Distributed Storage System for Structured Data . Consultat la 30 iulie 2012. Arhivat din original la 8 februarie 2015. (nedefinit)