A Bloom-szűrő egy helytakarékos valószínűségi struktúra, amely egy csavarral válaszol a halmaztaegység kérdésekre: lehet hamis pozitívja, de soha nem hamis negatívja. A "határozottan nincs jelen" biztos; a "valószínűleg jelen van" igazi ellenőrzést igényel.
Egy bit hosszú bitsorozat és hash-függvény. Egy elem állítsd a bitet, amelyre azt hash-eli. Az ellenőrizd ezeket a biteket — ha valamelyik 0, az elem határozottan nincs jelen.
mkkkbits: [0 0 0 0 0 0 0 0]
add "cat": hash->bits 1,4,6 -> [0 1 0 0 1 0 1 0]
query "dog": hashes to 1,3,6 -> bit 3 is 0 -> DEFINITELY absent
query "cat": all of 1,4,6 set -> "probably present"
class BloomFilter:
def __init__(self, m, hashes):
self.bits = [0]*m
self.m, self.hashes = m, hashes # list of hash fns
def add(self, x):
for h in self.hashes:
self.bits[h(x) % self.m] = 1
def __contains__(self, x): # False = certain; True = maybe
return all(self.bits[h(x) % self.m] for h in self.hashes)
| Művelet | Idő | Hely |
|---|---|---|
| add | O(k) | O(m) bit |
| query | O(k) | — |
Nincs hamis negatívja; a hamis pozitív aránya csökken, ahogy m (és a beállított k) növekszik.
A Bloom-szűrők olcsón kerülik meg a drága munkát: az adatbázisok (például Cassandra, HBase) használják őket, hogy elkerüljék a lemezolvasásokat olyan kulcsokhoz, amelyek biztosan nem vannak a lemezen.
Egy klasszikus rendszerkompromisszumot testesítenek meg — fogadj el egy kis, korlátos hibaarányt cserébe a memória és I/O hatalmas csökkentéséért.