A Bloom filter एक स्पेस-एफिशिएन्ट probabilistic संरचना हो जसले सेट मेम्बरशिपको उत्तर एक ट्विस्टको साथ दिन्छ: यसमा false positives हुन सक्छ तर कहिले पनि false negatives हुँदैन। "निश्चित रूपमा मौजूद छैन" निश्चित छ; "सम्भवतः मौजूद छ" को लागि वास्तविक जाँच आवश्यक छ।
बिट्स र hash functions को बिट array। गर्न, यसले hash गर्ने बिट्स सेट गर्नुहोस्। गर्न, ती बिट्स जाँच गर्नुहोस् — यदि कुनै पनि 0 छ भने, आइटम निश्चित रूपमा अनुपस्थित छ।
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)
| Operation | Time | Space |
|---|---|---|
| add | O(k) | O(m) bits |
| query | O(k) | — |
कुनै false negatives छैन; false-positive दर m (र tuned k) बढ्दै जाँदा घट्छ।
Bloom filters सस्तैमा महँगो काम छोड्छन्: डाटाबेसहरू (जस्तै Cassandra, HBase) यसलाई डिस्क पढनबाट बचाउन प्रयोग गर्छन् ती कुञ्जीहरूको लागि जो निश्चित रूपमा डिस्कमा छैनन्।
तिनीहरू एक क्लासिक सिस्टम ट्रेड-अफ् को प्रतिनिधित्व गर्छन् — मेमोरी र I/O मा ठूलो कमीको बदलामा एक सानो, सीमित त्रुटि दर स्वीकार गर्नुहोस्।