Blumov filter

Iz Vikipedije, slobodne enciklopedije
Skoči na: navigacija, pretraga

Blumov filter je prostorno-efikasna probabilistička struktura podataka koja služi za testiranje da li je element član skupa. Osmislio ga je Barton Hauard Blum 1970. godine[1]. Lažni pozitivni rezultati su mogući, ali lažni negativni nisu; to znači da upit vraća ili „jeste u skupu (što može da bude pogrešno)“ ili „definitivno nije u skupu“. Elementi mogu da se dodaju u skup, ali ne mogu da se iz njega izbacuju (mada ovo može da se reši pomoću brojačkog filtera). Što se više elemenata dodaje u skup, veća je verovatnoća lažnih pozitivnih rezultata.

Sadržaj

Opis algoritma [uredi]

Primer Blumovog filtera, predstavlja skup {x, y, z}. Obojene strelice pokazuju pokazuju pozicije u bitovskom nizu u koje je svaki element mapiran. Element w nije u skupu {x, y, z}, jer jedna od njegovih heš vrednosti u nizu sadrži 0. Na ovoj slici je m=18 i k=3.

Prazan Blumov filter je bitovski niz od m bitova koji su svi postavljeni na 0. Takođe je potrebno i da bude definisano k različitih heš funkcija, od kojih svaka preslikava neki skup elemenata u jednu od m pozicija sa uniformnom slučajnom distribucijom.

Kako bi se dodao element u filter, potrebno je za njega izračunati svaku od k heš vrednosti. Svaku od dobijenih k pozicija u nizu treba postaviti na 1.

Kako bi se filter pretražio za neki element (testiranje da li je element u skupu), ponovo se za njega računa svaka od k heš vrednosti kako bi se dobilo k pozicija u nizu. Ako je bilo koji bit na nekoj od ovih pozicija jednak 0, element sigurno nije u skupu – jer da jeste, onda bi svi bitovi bili postavljeni na 1 prilikom umetanja. Ako su sve vrednosti jednake 1, onda je ili element u skupu, ili su svi bitovi već postavljeni na 1 tokom umetanja drugih elemenata skupa, što dovodi do lažnog pozitivnog rezultata. U jednostavnom Blumovom filteru ne postoji način da se razlikuju ova dva slučaja, ali naprednije tehnike mogu da se koriste za rešavanje ovog problema.

Zahtev za definisanjem k različitih nezavisnih heš funkcija može da bude nezgodan za veliko k. Kod „dobre“ heš funkcije sa dugačkim izlazom, trebalo bi da ima jako malo ili nimalo korelacija između različitih bitovskih polja takvog heša, tako da ovakva heš funkcija može da se koristi za generisanje više „različitih“ heš funkcija tako što se njen izlaz isecka u više bitovskih nizova. Drugi pristup je da se prosledi k različitih početnih vrednosti (na primer 0, 1, ..., k − 1) heš funkciji koja uzima dva parametra, ili da se ove vrednosti dodaju (dopišu) elementu koji se ubacuje u skup. Za veće m i(li) k, uslov nezavisnosti između heš funkcija može da se relaksira sa zanemarljivim porastom verovatnoće lažnih pozitivnih rezultata (Dillinger & Manolios (2004a), Kirsch & Mitzenmacher (2006)). Specifično, pokazana je (Dillinger & Manolios (2004b)) efektivnost dobijanja k indeksa korišćenjem unapređenog dvostrukog heširanja ili trostrukog heširanja, što su varijante dvostrukog heširanja koje su efektivno jednostavni generatori slučajnih brojeva inicijalizovani sa dve ili tri heš vrednosti.

Uklanjanje elemenata iz jednostavnog Blumovog filtera je nemoguće jer lažni negativni rezultati nisu dozvoljeni. Element se preslikava u k bita, i iako bi postavljanje bilo kog od ovih k bita na nulu bilo dovoljno da se element ukloni, to bi ujedno uklonilo i svaki drugi element koji je preslikan u taj bit. Kako ne postoji način da se utvrdi da li je bilo koji drugi element preslikan u neki od bitova elementa koji se uklanja, postavljanje bilo kog od tih bitova na 0 bi uvelo mogućnost lažnih negativnih rezultata.

Jednokratno brisanje elementa iz Blumovog filtera može da se simulira dodavanjem drugog Blumovog filtera koji bi sadržavao elemente koji su obrisani. Međutim, lažni pozitivni rezultati u drugom filteru bi mogli da proizvedu lažne negativne razultate, što nije dopušteno. U ovom pristupu ne bi bilo moguće ponovno dodavanje prethodno obrisanih elemenata, jer bi oni morali da budu uklonjeni iz drugog filtera.

Međutim, čest je slučaj da su svi elementi skupa dostupni i moguće ih je pobrojati, ali je to skupo (na primer, jer zahteva dosta čitanja sa diska). U ovom slučaju, ako stopa lažnih pozitivnih rezultata postane suviše visoka, filter može da bude regenerisan; to bi trebalo da se dešava relativno retko.

Verovatnoća lažnog pozitivnog rezultata [uredi]

Verovatnoća lažnog pozitivong rezultata p kao funkcija broja elemenata n u filteru i veličine filtera, m. Podrazumevan je optimalan broj heš funkcija, k= (m/n) \ln 2.

Neka važi pretpostavka da heš funkcija bira svaki element niza sa jednakom verovatnoćom. Ako je m broj bitova u nizu, verovatnoća da određeni bit nije postavljen na jedinicu od strane određene heš funkcije tokom umetanja elementa iznosi

1-\frac{1}{m}.

Verovatnoća da taj bit nije postavljen na jedinicu od strane bilo koje heš funkcije prilikom umetanja jednog elementa je

\left(1-\frac{1}{m}\right)^k.

Ako je umetnuto n elemenata, verovatnoća da je određeni bit još uvek jednak nuli je

\left(1-\frac{1}{m}\right)^{kn};

Iz toga sledi da je verovatnoća da je postavljen na jedinicu jednaka

1-\left(1-\frac{1}{m}\right)^{kn}.

Neka se testira pripadnost skupu nekog elementa koji nije u skupu. Svaki od k bitova koje daju heš funkcije je 1 sa verovatnoćom datom gore. Verovatnoća da su svi oni jednaki 1, što bi dovelo do toga da algoritam pogrešno vrati da je element u skupu, se često navodi kao

\left(1-\left[1-\frac{1}{m}\right]^{kn}\right)^k \approx \left( 1-e^{-kn/m} \right)^k.

Ovo nije strogo tačno jer podrazumeva nezavisnost verovatnoća postavljanja svakog bita. Međutim ako se pretpostavi da je to bliska aproksimacija, važi da verovatnoća lažnih pozitivnih rezultata opada kako m (broj bitova u nizu) raste, i povećava se kako n (broj umetnutih elemenata) raste. Za dato m i n, vrednost za k (broj heš funkcija) koje minimizuju verovatnoću lažnog pozitivnog rezultata je

\frac{m}{n}\ln 2 \approx 0.7\frac{m}{n},

što daje verovatnoću lažnog pozitivnog rezultata od

2^{-k} \approx {0.6185}^{m/n}.

Potreban broj bitova, m za dato n (broj umetnutih elemenata) i traženu verovatnoću lažnog pozitivnog rezultata, p (uz pretpostavku da se koristi optimalna vrednost za k) može da se izračuna zamenom optimalne vrednosti za k u gornjoj jednačini:

p = \left( 1-e^{-(m/n\ln 2) n/m} \right)^{(m/n\ln 2)}

što može da se pojednostavi:

\ln p = -\frac{m}{n} \left(\ln 2\right)^2.

a to daje:

m=-\frac{n\ln p}{(\ln 2)^2}.

Ovo znači da dužina Blumovog filtera mora da raste linearno sa brojem umetnutih elemenata kako bi se održala fiksna verovatnoća lažnih pozitivnih rezultata. Iako je gornja formula asimptotska (to jest, važi za m, n → ∞), sasvim je prihvatljiva i za konačne vrednosti m i n; verovatnoća lažnog pozitivnog rezultata za konačni Blumov filter od m bitova, n elemenata i k heš funkcija je najviše

\left( 1-e^{-k(n+0.5)/(m-1)} \right)^k.


Reference [uredi]

  1. ^ Donald Knuth. „The Art of Computer Programming, Errata for Volume 3 (2nd ed.)“ 

Literatura [uredi]

Spoljašnje veze [uredi]

Implementacije [uredi]

Preuzeto iz „http://sr.wikipedia.org/w/index.php?title=Блумов_филтер&oldid=6937839“