एक Bloom filter एक अंतरिक्ष-कुशल संभाव्यतात्मक संरचना है जो सेट सदस्यता का जवाब देती है एक मोड़ के साथ: इसमें झूठी सकारात्मकताएं हो सकती हैं लेकिन कभी भी झूठी नकारात्मक नहीं। "निश्चित रूप से अनुपस्थित" निश्चित है; "संभवतः अनुपस्थित" को वास्तविक जांच की आवश्यकता है।
बिट्स और हैश फ़ंक्शन की एक बिट सरणी। एक आइटम , उन बिट्स को सेट करें जिन्हें यह हैश करता है। , उन बिट्स की जांच करें — यदि कोई 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)
| ऑपरेशन | समय | स्थान |
|---|---|---|
| add | O(k) | O(m) बिट्स |
| query | O(k) | — |
कोई झूठी नकारात्मकताएं नहीं; झूठी सकारात्मक दर m (और ट्यून किए गए k) के बढ़ने के साथ गिरती है।
Bloom filters सस्ती कीमत में महंगे काम को छोड़ देते हैं: डेटाबेस (जैसे Cassandra, HBase) उन्हें उन कुंजियों के लिए डिस्क पढ़ने से बचने के लिए उपयोग करते हैं जो निश्चित रूप से डिस्क पर नहीं हैं।
वे एक क्लासिक सिस्टम व्यापार-बंद को मूर्त रूप देते हैं — मेमोरी और I/O में एक विशाल कमी के बदले में एक छोटी, सीमित त्रुटि दर को स्वीकार करते हैं।