Bloom filtresi, küme üyeliğine bir kez daha yanıt veren, alan açısından verimli bir olasılıksal yapıdır: yanlış pozitif olabilir ancak asla yanlış negatif olmaz. "Kesinlikle mevcut değil" kesindir; "muhtemelen mevcut" gerçek bir kontrol gerektirir.
bit ve hash fonksiyonundan oluşan bit dizisi. Öğe için, hash yaptığı bitleri ayarlayın. için, bu bitleri kontrol edin — herhangi biri 0 ise, öğe kesinlikle mevcut değildir.
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)
| İşlem | Zaman | Alan |
|---|---|---|
| add | O(k) | O(m) bit |
| query | O(k) | — |
Yanlış negatif yoktur; yanlış pozitif oranı m (ve ayarlanmış k) büyüdükçe düşer.
Bloom filtreleri pahalı işi ucuza atlayan kullanır: veritabanları (ör. Cassandra, HBase), diskte kesinlikle olmayan anahtarlar için disk okumalarından kaçınmak için bunları kullanır.
Bunlar klasik bir sistemler uzlaşmasını gösterir — bellek ve I/O da muazzam bir azalma karşılığında küçük, sınırlı bir hata oranını kabul edin.