ব্লুম ফিল্টার (Bloom Filter)
ধরুন আপনি একটা বিশাল বড় বিয়ের অনুষ্ঠানে গেট চেকার বা বাউন্সার হিসেবে দাঁড়িয়ে আছেন। আপনার হাতে একটা ছোট্ট চেকলিস্ট আছে — সেখানে কারো নাম লেখা নেই, শুধুই কতগুলো বক্স করা আছে। যখন কেউ অনুষ্ঠানে ঢোকে, আপনি তার নামের ওপর ভিত্তি করে নির্দিষ্ট কয়েকটা বক্সে টিক দিয়ে দেন। এরপর যখন কেউ গেটে আসে, আপনি ঠিক ওই বক্সগুলো চেক করেন। যদি দেখেন এর মধ্যে যেকোনো একটা বক্স খালি বা টিক দেওয়া নেই: তাহলে ১০০% কনফার্ম যে সে আমন্ত্রিত ছিল না। আর যদি দেখেন সব বক্সে টিক দেওয়া আছে: তবে সে সম্ভবত আমন্ত্রিত ছিল — কিন্তু এখানে আপনার একটু ভুল হওয়ার চান্স থাকে (কারণ অন্য কারো জন্য হয়তো ওই বক্সগুলোতে টিক পড়েছিল)।
এটাই হলো ব্লুম ফিল্টার (Bloom filter)। এটা মূলত একটা বিটের অ্যারে (যেখানে শুরুতে সব ০ থাকে) এবং এর সাথে থাকে k সংখ্যক স্বাধীন হ্যাশ ফাংশন (hash functions)। এটা আপনাকে ১০০% গ্যারান্টি দিয়ে বলতে পারবে যে কোনো জিনিস লিস্টে নেই, কিন্তু জিনিসটা লিস্টে আছে কি না—সেটা সে শুধু সম্ভাবনা (probably) হিসেবে বলতে পারে।
এটা কীভাবে কাজ করে?
নতুন কোনো ডেটা ঢোকাতে (insert) হলে: ডেটাটাকে ওই k-সংখ্যক হ্যাশ ফাংশনের ভেতর দিয়ে পাস করুন। প্রতিটা ফাংশন আপনাকে ওই বিট অ্যারের একটা করে পজিশন বা ইনডেক্স দেবে। এবার ওই k-টা পজিশনের মান ০ থেকে বদলে ১ করে দিন।
কোনো ডেটা খুঁজতে (query) হলে: ডেটাটাকে আবার ওই k-সংখ্যক হ্যাশ ফাংশন দিয়ে পাস করে পজিশনগুলো বের করুন। যদি দেখেন সবগুলো পজিশনেই ১ আছে — তার মানে ডেটাটা সম্ভবত লিস্টে আছে। কিন্তু যদি দেখেন যেকোনো একটা পজিশনেও 0 আছে — তার মানে ডেটাটা ১০০% কনফার্ম লিস্টে নেই।
← → অ্যারো কি (arrow key) ব্যবহার করুন · উপাদানগুলোতে ক্লিক করুন
ফলস পজিটিভ (False positives) — কেন হয়?
আলাদা আলাদা শব্দ বা ডেটা একই বিটকে ১ করে দিতে পারে। অনেক বেশি ডেটা ঢোকানোর পর, অ্যারের বেশিরভাগ বিটই ১ হয়ে যায়। তখন এমন হতে পারে যে, আপনি এমন একটা নতুন শব্দ খুঁজতে দিলেন যেটা আগে কখনোই ঢোকানো হয়নি, কিন্তু ওই শব্দটার k-টা পজিশন চেক করে দেখলেন সবগুলোই ১ হয়ে আছে — কারণ অন্য কোনো শব্দ আগে এসে হয়তো ওই বিটগুলোকে ১ করে দিয়ে গেছে। এটাকেই বলে ফলস পজিটিভ (False positive): ফিল্টার আপনাকে বলছে "হ্যাঁ, হয়তো আছে", কিন্তু আসল উত্তর হলো "না, নেই"।
এই ফলস পজিটিভ হওয়ার হার নির্ভর করে ফিল্টারের সাইজ (m বিট), হ্যাশ ফাংশনের সংখ্যা (k), এবং কতগুলো ডেটা ঢোকানো হয়েছে (n) তার ওপর। ফিল্টারের সাইজ বড় হলে এবং সঠিক k বেছে নিলে ভুল হওয়ার হার অনেক কমে যায়।
ফলস নেগেটিভ (False negatives) — কখনোই হয় না
যদি কোনো শব্দ আগে লিস্টে ঢোকানো হয়ে থাকে, তবে তার k-টা বিট অবশ্যই ১ করা হয়েছিল এবং সেগুলো সারা জীবন ১-ই থাকবে। ব্লুম ফিল্টারে ১ হয়ে যানয়া বিটকে আর কখনো ০ করা যায় না (কারণ বেসিক ব্লুম ফিল্টারে ডেটা ডিলিট করার কোনো অপশন নেই)। তাই কোনো শব্দ যদি লিস্টে সত্যিই থাকে, তবে ফিল্টার কখনোই ভুল করে বলবে না যে "না, শব্দটা নেই"।
বাস্তব দুনিয়ায় এর ব্যবহার
- স্পেল চেকার (Spell checkers) — পুরো ডিকশনারি সেভ করে না রেখেই, কোনো বানান ডিকশনারিতে না থাকার সম্ভাবনা ফিল্টার করে ফেলা যায়।
- সিডিএন / ওয়েব ক্যাশ (CDN / web caches) — কোনো আসল বা ভারী মেমরি খোঁজার আগে, আগেভাগে চেক করে নেওয়া যায় যে URL-টা ক্যাশে আছে কি না।
- ডেটাবেস (Databases) — যেসব ডেটা ডেটাবেসে নেই, তাদের জন্য অযথা হার্ডডিস্ক খোঁজার সময় নষ্ট বাঁচায় (যেমন Cassandra, HBase, LevelDB)।
- ব্রাউজার (Browsers) — ক্ষতিকর বা ম্যালিসিয়াস ওয়েবসাইট চেনার জন্য গুগল ক্রোম (Safe Browsing) অফলাইনে একটা ব্লুম ফিল্টার ব্যবহার করে।