Bloom-Szűrő
A Bloom-szűrő egy olyan adatszerkezet, amely lehetővé teszi a számítógépek számára, hogy megnézzék, hogy egy adott elem előfordul-e egy halmazban. A Bloom-szűrők ehhez hash-függvényeket használnak. Minden egyes hozzáadott elemhez egy hash-értéket számolnak ki. Amikor egy új elemet adunk hozzá, annak hash-értékét összehasonlítjuk a halmaz többi elemének értékével. A Bloom-szűrő egy valószínűségi adatszerkezet. Lehetséges, hogy hamis pozitív eredményt kapjunk, de hamis negatív eredményt nem. Más szóval, egy lekérdezés vagy azt adja vissza, hogy "valószínűleg benne van a halmazban", vagy azt, hogy "biztosan nincs benne a halmazban". A halmazba elemeket lehet hozzáadni, de eltávolítani nem. Minden egyes hozzáadott elemmel nő a hamis pozitív eredmény valószínűsége.
Edward Bloom 1970-ben javasolta a Bloom-szűrőt. A cikkben Bloom feltételezi, hogy létezik egy algoritmus a sor végén lévő szavak kötőjeles szűrésére. A példa szerint a legtöbb szónak egyszerű kötőjeles mintája van. A szavak körülbelül 10%-a azonban időigényes keresést igényel a helyes szabály lekérdezéséhez. Esetében körülbelül 500 000 szó kötőjelezéséről volt szó. Úgy látta, hogy a "normál" hibamentes hashing technikák használata, a kötőjelképzési minták tárolása sok memóriát igényelne. Úgy találta, hogy az ő technikáját használva a legtöbb keresést ki tudja küszöbölni. Például egy olyan hash-terület, amely csak 15%-a az ideális hibamentes hash-hez szükséges méretnek, még mindig kiküszöböli a lemezelérések 85%-át.
Általánosságban elmondható, hogy elemenként kevesebb mint 10 bit szükséges 1%-os hamis pozitív valószínűséghez, függetlenül a halmaz elemeinek méretétől vagy számától.
Kérdések és válaszok
K: Mi az a Bloom-szűrő?
V: A Bloom-szűrő egy olyan adatszerkezet, amely lehetővé teszi a számítógépek számára, hogy megnézzék, előfordul-e egy adott elem egy halmazban. Ehhez hash-függvényeket használ, kiszámítva minden egyes hozzáadott elem hash-értékét, és összehasonlítva azt a halmaz többi elemével.
K: Milyen típusú adatszerkezet a Bloom-szűrő?
V: A Bloom-szűrő valószínűségi adatszerkezet, ami azt jelenti, hogy előfordulhat, hogy hamis pozitív eredményt kapunk, de hamis negatív eredményt nem.
K: Ki javasolta a Bloom-szűrőt?
V: Edward Bloom 1970-ben javasolta a Bloom-szűrőt.
K: Mi volt Edward Bloom példája a technikája használatára?
V: Edward példája körülbelül 500 000 szó kötőjeles keresése volt; úgy találta, hogy a technikáját használva a legtöbb keresést ki tudja küszöbölni, és 15%-kal csökkenti a lemezeléréseket.
K: Hány bit szükséges elemenként 1%-os hamis pozitív valószínűséghez?
V: Elemenként kevesebb mint 10 bit szükséges az 1%-os hamis pozitív valószínűséghez, függetlenül a halmaz elemeinek méretétől vagy számától.
K: Lehetséges-e eltávolítani elemeket egy bloom szűrőből, miután azokat hozzáadtuk?
V: Nem, elemeket csak hozzáadni lehet a halmazhoz, de eltávolítani nem.
K: Több elem hozzáadása növeli vagy csökkenti a hamis pozitív eredmény valószínűségét?
V: Több elem hozzáadása növeli a hamis pozitív eredmény valószínűségét.
