একটি Bloom filter হল একটি স্থান-দক্ষ সম্ভাবনামূলক কাঠামো যা সেট সদস্যতা প্রশ্নের উত্তর দেয় একটি পরিবর্তন সহ: এটি মিথ্যা ইতিবাচক থাকতে পারে কিন্তু কখনও মিথ্যা নেতিবাচক নেই। "নিশ্চিতভাবে উপস্থিত নয়" নিশ্চিত; "সম্ভবত উপস্থিত" একটি বাস্তব পরীক্ষার প্রয়োজন।
বিট এবং hash ফাংশনের একটি বিট অ্যারে। একটি আইটেম করতে, যে বিটগুলিতে এটি 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)
| অপারেশন | সময় | স্থান |
|---|---|---|
| add | O(k) | O(m) bits |
| query | O(k) | — |
কোন মিথ্যা নেতিবাচক নেই; মিথ্যা-ইতিবাচক হার m বৃদ্ধির সাথে সাথে পড়ে (এবং টিউন করা k)।
Bloom filters সস্তায় ব্যয়বহুল কাজ এড়িয়ে যায়: ডাটাবেস (যেমন Cassandra, HBase) সেগুলি ব্যবহার করে যে কীগুলির জন্য ডিস্ক পড়া এড়াতে যা নিশ্চিতভাবে ডিস্কে নেই।
তারা একটি ক্লাসিক সিস্টেম ট্রেড-অফকে মূর্ত করে — মেমোরি এবং I/O-তে বিশাল হ্রাসের বিনিময়ে একটি ছোট, সীমাবদ্ধ ত্রুটির হার গ্রহণ করুন।