র‍্যান্ডমাইজড অ্যালগরিদম৭ মিনিট পড়া

ব্লুম ফিল্টার (Bloom Filter)

সম্ভবত হ্যাঁ, নিশ্চিতভাবে না — একটি মেমরি-সাশ্রয়ী মেম্বারশিপ পরীক্ষক
insert:O(k) — k সংখ্যক বিট সেট করুনquery:O(k) — k সংখ্যক বিট চেক করুনfalse positives:সম্ভব (টিউনযোগ্য)false negatives:কখনোই না

ধরুন একটি অনুষ্ঠানের দারোয়ান, যিনি একটি তালিকা দেখে অতিথিদের প্রবেশ করাচ্ছেন — কিন্তু তালিকাটি অদৃশ্য কালিতে লেখা, এবং মাঝে মাঝে কালি ছড়িয়ে গিয়ে এমন নামও দাগিয়ে দেয় যা সেখানে কখনোই ছিল না। দারোয়ান হয়তো কোনো নিরীহ ব্যক্তিকে ফিরিয়ে দিতে পারেন (ফলস পজিটিভ), কিন্তু তিনি কখনোই নিষিদ্ধ তালিকার কাউকে ঢুকতে দেবেন না (কোনো ফলস নেগেটিভ নেই)।

এটাই হলো ব্লুম ফিল্টার (Bloom Filter): মেমরি-সাশ্রয়ী ও অত্যন্ত দ্রুত একটি উপায় যা দিয়ে আপনি জানতে পারেন "এই জিনিসটি কি আমার সেটে আছে?" এটি হয়তো বলবে "সম্ভবত হ্যাঁ" যখন উত্তরটি আসলে না হতে পারে — কিন্তু এটি যদি বলে "নিশ্চিতভাবে না," তবে আপনি তা চোখ বন্ধ করে বিশ্বাস করতে পারেন।

এটি কীভাবে কাজ করে

ব্লুম ফিল্টার মূলত m বিটের একটি বিট অ্যারে (bit array) (শুরুতে সবগুলো শূন্য থাকে) যার সাথে k সংখ্যক স্বাধীন হ্যাশ ফাংশন যুক্ত থাকে। প্রতিটি হ্যাশ ফাংশন যেকোনো ইনপুটকে ওই অ্যারের একটি অবস্থানে ম্যাপ করে।

ইনসার্ট করার জন্য, একটি উপাদানকে সবকটি k হ্যাশ ফাংশনের মধ্য দিয়ে চালান এবং সেই বিট অবস্থানগুলোকে 1 করে দিন। ব্যাস, এটুকুই।

কোয়েরি করার জন্য, একই k হ্যাশ চালান। যদি সেই অবস্থানগুলোর প্রতিটি বিট 1 হয় → "সম্ভবত সেটের মধ্যে আছে।" যদি যেকোনো একটি বিট 0 হয় → "নিশ্চিতভাবে সেটের মধ্যে নেই।" একটি 0 তখনই থাকতে পারে যদি সেই অবস্থানটি কখনোই পাল্টানো না হয় — এর মানে এই উপাদানটি কখনোই ইনসার্ট করা হয়নি।

কেন ফলস পজিটিভ ঘটে — কিন্তু ফলস নেগেটিভ অসম্ভব

সময়ের সাথে সাথে অন্যান্য উপাদানগুলো অ্যারের বিভিন্ন বিট পরিবর্তন করতে থাকে। কাকতালীয়ভাবে, আপনার কোয়েরির জন্য যে নির্দিষ্ট অবস্থানগুলো দরকার, সেগুলো আগে থেকেই 1 হয়ে থাকতে পারে — যেগুলো অন্যান্য উপাদানগুলোর দ্বারা সেট হয়েছিল। এটিই হলো ফলস পজিটিভ। কিন্তু একবার কোনো বিট 1 হয়ে গেলে, সেটি চিরকাল 1-ই থাকে। সুতরাং যদি আপনি কোনো কিছু ইনসার্ট করে থাকেন, এর বিটগুলো সবসময় চালু থাকার গ্যারান্টি রয়েছে — যার মানে ফলস নেগেটিভ গঠনগতভাবেই অসম্ভব।

ফলস পজিটিভ রেট টিউন করা

প্রত্যাশিত ইনসারশন সংখ্যা n এবং লক্ষ্যকৃত ফলস পজিটিভ রেট p হলে, সর্বোত্তম প্যারামিটারগুলো হলো:
• বিট অ্যারের সাইজ: m = -n·ln(p) / (ln 2)²
• হ্যাশ ফাংশনের সংখ্যা: k = (m/n)·ln 2 ≈ 0.693·m/n

১% ফলস পজিটিভ রেটের জন্য, আপনার প্রতিটি উপাদানের জন্য প্রায় ৯.৬ বিট প্রয়োজন। ৬৪-বিট কী সংরক্ষণ করা একটি সাধারণ হ্যাশ সেটে প্রতিটি উপাদানের জন্য কমপক্ষে ৬৪ বিট লাগে — অর্থাৎ প্রায় ৭ গুণ বেশি স্পেস প্রয়োজন।

ডিলিশন বা মুছে ফেলা কেন সম্ভব নয়?

যদি আপনি কোনো উপাদান "মুছে ফেলার" জন্য একটি বিট পরিষ্কার (0) করেন, তবে আপনি হয়তো অন্যান্য উপাদানের প্রমাণও মুছে ফেলতে পারেন যারা ওই একই বিট অবস্থান ব্যবহার করছিল। এর ফলে আপনি ফলস নেগেটিভ তৈরি করবেন — যা ব্লুম ফিল্টারকে অকেজো করে দেবে। কাউন্টিং ব্লুম ফিল্টার (Counting Bloom Filters) এর মতো এক্সটেনশনগুলো বিটের বদলে ছোট কাউন্টার ব্যবহার করে ডিলিশন করতে সক্ষম, তবে এর জন্য বেশি মেমরি লাগে।

বাস্তব উদাহরণ

গুগল ক্রোমের সেফ ব্রাউজিং ক্ষতিকারক ইউআরএলগুলোর একটি লোকাল ব্লুম ফিল্টার ব্যবহার করে। একটি ফলস পজিটিভ হলে শুধুমাত্র সার্ভারে গিয়ে আবার চেক করতে হয় — যার খরচ খুব সামান্য। কিন্তু একটি ফলস নেগেটিভ (প্রকৃত বিপদ এড়িয়ে যাওয়া) হলে তা বিপর্যয়কর হতে পারে, এবং ফিল্টারটি তা অসম্ভব করে তোলে।

ডেটাবেসগুলো (ক্যাসান্দ্রা, রক্সডিবি, এইচবেস) ডিস্কে হাত দেওয়ার আগে ব্লুম ফিল্টার ব্যবহার করে: "এই কী (key) কি এই SSTable-এ আছে?" একটি ফলস পজিটিভ হলে শুধুমাত্র একটি ডিস্ক রিড নষ্ট হয়। একটি ফলস নেগেটিভ হলে ভুল ডেটা ফেরত আসতো। ফিল্টারটি ফলস নেগেটিভ সম্পূর্ণ দূর করে এবং বেশিরভাগ অপ্রয়োজনীয় ডিস্ক আই/ও কমিয়ে দেয়।

দ্রষ্টব্য: ব্লুম ফিল্টার এর দুটি নিয়ম: (১) 'নিশ্চিতভাবে না' সর্বদা বিশ্বাসযোগ্য। (২) 'সম্ভবত হ্যাঁ' ভুল হতে পারে। যখন ফলস পজিটিভ একেবারে অগ্রহণযোগ্য তখন কখনও ব্লুম ফিল্টার ব্যবহার করবেন না — যখন ফলস পজিটিভ শুধুমাত্র কিছুটা সমস্যা তৈরি করে, তখনি এটি ব্যবহার করুন।

ব্লুম ফিল্টার — কোর ইনসার্ট এবং কোয়েরি

import math
import mmh3  # pip install mmh3


class BloomFilter:
    def __init__(self, capacity, fp_rate=0.01):
        self.m = math.ceil(-capacity * math.log(fp_rate) / (math.log(2)**2))
        self.k = math.ceil((self.m / capacity) * math.log(2))
        self.bits = bytearray(math.ceil(self.m / 8))


    def _hashes(self, item):
        return [mmh3.hash(item, seed) % self.m for seed in range(self.k)]


    def add(self, item):
        for pos in self._hashes(item):
            self.bits[pos >> 3] |= (1 << (pos & 7))


    def __contains__(self, item):
        return all(
            (self.bits[pos >> 3] >> (pos & 7)) & 1
            for pos in self._hashes(item)
        )


bf = BloomFilter(1000)
bf.add("anika")
bf.add("rafi")
print("anika" in bf)   # True (was inserted)
print("sadia" in bf) # False (definitely not inserted)
print(f"Bit array size: {bf.m} bits = {bf.m // 8} bytes")
Output
True
False
Bit array size: 9586 bits = 1198 bytes

Complexity

➕ একটি উপাদান ইনসার্ট করা
k একটি ছোট ধ্রুবক (সাধারণত ৭-১০); শুধুমাত্র সিপিইউ-এর কাজ, কোনো মেমরি অ্যালোকেশন নেই
k টি বিট পজিশন সেট করুন O(k)
🔍 মেম্বারশিপ কোয়েরি
প্রথম ০ বিট পেলেই কাজ শেষ হয়ে যায় — তাই বাস্তবে এটি O(k)-এর চেয়েও দ্রুত হতে পারে
k টি বিট পজিশন চেক করুন O(k)
⚠️ ফলস পজিটিভ রেট
~৯.৬ বিট/উপাদান ১% FPR দেয়; ~১৪.৪ বিট/উপাদান ০.১% FPR দেয়
m এবং k দ্বারা টিউনযোগ্য (1−e^(−kn/m))^k
✅ ফলস নেগেটিভ রেট
সেট হওয়া বিট কখনোই আবার ০ হয় না; তাই প্রতিটি ইনসার্ট করা উপাদান সবসময় কোয়েরিতে পাস করে
গঠনগতভাবেই অসম্ভব P = 0
💾 স্পেস বনাম হ্যাশ সেট
m ≈ −n·ln(p) / (ln 2)²; আসল কী সংরক্ষণ করতে প্রতিটি উপাদানের জন্য কমপক্ষে ৬৪+ বিট লাগে, সেখানে ব্লুম ফিল্টার মাত্র ~৯.৬ বিট নেয়
১% FPR-এ প্রায় ৭ গুণ কম স্পেস O(m) বিটস

ছোট কুইজ

একটি ব্লুম ফিল্টার বলছে উপাদান X সেটের মধ্যে নেই। আপনি কী সিদ্ধান্তে আসতে পারেন?

পড়া চালিয়ে যান