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

একটি ব্লুম ফিল্টার হলো একটি ডেটা স্ট্রাকচার যা ডিজাইন করা হয়েছে একটি এলিমেন্টের প্রেজেন্স একটি সেটে শনাক্ত করতে দ্রুত এবং মেমরি-ইফিশিয়েন্টলি।

একটি নির্দিষ্ট ডেটা স্ট্রাকচার যেনে প্রোবাবিলিস্টিক ডেটা স্ট্রাকচার ব্লুম ফিল্টার হিসেবে বাস্তবায়িত হয়। এই ডেটা স্ট্রাকচার আমাদের সাহায্য করে শনাক্ত করতে যে একটি এলিমেন্ট হয় প্রেজেন্ট অথবা অ্যাবসেন্ট একটি সেটে।

বিট ভেক্টর বেস ডেটা স্ট্রাকচার হিসেবে বাস্তবায়িত হয়। এখানে একটি ছোটটি আমরা ব্যবহার করব ব্যাখ্যা করতে

টেবিলে প্রতিটি খালি সেল একটি বিট নির্দেশ করে এবং তার নিচের নম্বর তার ইনডেক্স বা পজিশন। একটি এলিমেন্ট ব্লুম ফিল্টারে অ্যাপেন্ড করতে, আমরা সেটি কিছুবার হ্যাশ করি এবং বিট ভেক্টরে সেই হ্যাশের পজিশন বা ইনডেক্সের বিটগুলো ১ সেট করি।

ব্লুম ফিল্টারের বিস্তারিত বাস্তবায়ন নিচে আলোচনা করা হলো

ব্লুম ফিল্টার দুটি অ্যাকশন সাপোর্ট করে, প্রথমে অবজেক্ট অ্যাপেন্ড করা এবং ট্র্যাক রাখা এবং দ্বিতীয়ে যাচাই করা কোনো অবজেক্ট আগে দেখা হয়েছে কিনা।

ব্লুম ফিল্টারে অবজেক্ট অ্যাপেন্ড করা

• অবজেক্ট অ্যাপেন্ড করার জন্য হ্যাশ ভ্যালু কম্পিউট করি;
• এই হ্যাশ-ভ্যালু ব্যবহার করে ব্লুম ফিল্টার স্টেটে নির্দিষ্ট বিট সেট করি (হ্যাশ ভ্যালু হলো সেট করার বিটের পজিশন)।

ব্লুম ফিল্টারে একটি অবজেক্ট আছে কিনা যাচাই করা −

• অবজেক্ট অ্যাপেন্ড করার জন্য হ্যাশ ভ্যালু কম্পিউট করি;
• তারপর যাচাই করি এই হ্যাশ ভ্যালু দ্বারা ইনডেক্সড বিটগুলো ব্লুম ফিল্টার স্টেটে সেট আছে কিনা।

আমাদের মনে রাখতে হবে যে একটি অবজেক্টের হ্যাশ ভ্যালু সরাসরি ব্লুম ফিল্টার স্টেটে অ্যাপেন্ড করা হয় না; প্রতিটি হ্যাশ ফাংশন শুধু নির্ধারণ করে কোন বিট সেট বা যাচাই করতে হবে। উদাহরণস্বরূপ: যদি শুধু একটি হ্যাশ ফাংশন ব্যবহার করা হয়, শুধু একটি বিট যাচাই বা চেক করা হয়।