موجودی عجیب! به نام Bloom Filter در برنامه نویسی

[دیکتاتورs.yavarnia]

بلوم فیلتر و کاربرد آن در برنامه نویسی


خُب این بلوم فیلتر چیه و به چه دردی میخوره را من هم نمی‌دونستم تا اینکه توی مقاله‌ای برای کاهش مصرف حافظه و کاهش افزونگی داده‌های تبادل شده بین نودهای شبکه‌های تحمیل پذیر تاخیر یا DTN بهش برخوردم که البته الان DTN موضوع مورد بحثم نیست و بعدا در یک نوشته جدا بهش می‌پردازم.

بیاید بریم سراغ ویکی‌پدیا، اگر سری به ویکی پدیا بزنید یک تعریف جالب از ساختار داده‌های احتمالاتیمی‌بینید که در بخشی توضیح داده که از خطای مثبت کاذب و منفی استفاده می کنه. اما داستان وقتی جالب تر میشه که به بخش زیر در ادامه توضیحات بلوم فیلتر بر می‌خوریم و با این تعریف روبرو می‌شویم:

فرض کنید می‌خواهیم وجود یک...

لطفا برای مشاهده کامل مطالب در انجمن ثبت نام کنید.

 

[دیکتاتورs.yavarnia]

تعریف Bloom filter
احتمالا می‌دونید که جدول درهم سازی(hash table) چطور کار می کنه؟ اگر نمی‌دونید پیشنهاد می‌کنم یک سری به ویکی بزنید.

در علوم رایانه، جدول درهم‌سازی یا جدول هش نوعی ساختمان داده است که مقدارهایی[۱] که باید ذخیره شوند را به وسیله تابع هش (درهم سازی) با کلیدهای ویژه‌ای مرتبط می‌سازد. عملیات اولیه‌ای که این جدول تسهیل می‌کند عمل مراجعه است. به این معنی که کاربر می‌تواند با سرعتی کارآمد داده مورد نظرش را در آن بیابد. در جدول‌های هش همچنین افزودن داده‌های جدید در زمان کم امکان‌پذیر است. زمان لازم برای جستجو و افزودن وابسته به نوع جدول و میزان داده‌ها هستند. این زمان می‌تواند با انتخاب جدول مناسب به مرتبه زمانی O(1) برسد.

وقتی...

لطفا برای مشاهده کامل مطالب در انجمن ثبت نام کنید.

 

[دیکتاتورs.yavarnia]

اما در این مثال از بلوم فیلتر ما از تابع هش چندگانه (k تعداد توابع هش) استفاده می‌کنیم که خروجی چندگانه نیز خواهیم داشت.

خروجی تابع هش چندگانه برای کلمه geeks
همونطور که در تصویر بالا مشخص هست برای ورودی آیتم geeks ما سه تابع هش داریم که هر تابع یک مقدار به ما بر می‌گردونه که در این مثال مقدار 1 ,4,7 هست یعنی خونه شماره 1 , 4 و 7 را از صفر به 1 تغییر میدهیم که ما آن ها را مشخص کردیم.

خروجی تابع هش چندگانه برای کلمه nerd
به...

لطفا برای مشاهده کامل مطالب در انجمن ثبت نام کنید.

 

[دیکتاتورs.yavarnia]

همچنین در نظر بگیرید که اگر نرخ خطای مثبت بلوم فیلتر شما 1% باشد به این معنی است که در میان هزینه های مراجعه به سرور یا دیسک، تنها 1% از کوئری‌های ما با خطا مواجه خواهد شد و ۹۹درصد دیگر سمت سرور نخواهند رفت. بد نیست نه؟

عملیات‌های بلوم فیلتر
یک بلوم فیلتر ساده از دو عملیات test (یا بررسی) و add (یا اضافه کردن) پشتیبانی می‌کند. Test برای چک کردن اینکه آیا یک عنصر در مجموعه وجود دارد یا نه و عملیات add هم برای اضافه کردن یک عنصر به مجموعه.

به نظرتون امکان حذف کردن یک ایتم از بلوم فیلتر وجود دارد؟ قبل از ادامه دادن یکم روی جواب تون فکر کنید.

قبل از جواب دادن به...

لطفا برای مشاهده کامل مطالب در انجمن ثبت نام کنید.

 

[دیکتاتورs.yavarnia]

اندازه Bloom filter و تعداد توابع Hash
شاید به این فکر کرده باشید که اگر اندازه بلوم فیلتر کوچک در نظر گرفته بشه ممکنه سریع همه خونه های آن برابر 1 بشه و بعد از این هر کلمه‌ای چه در لیست باشه چه نباشه را بررسی کنیم جواب مثبت برگردانده بشه. بنابراین اندازه بلوم فیلتر خیلی مهم است. در اینجا اگر اندازه بلوم فیلتر بزرگ انتخاب شود ما جواب های مثبت کاذب کمتری داریم و اگر اندازه کوچک باشد ما جواب های مثبت کاذب بیشتری خواهیم داشت. اینجا یک موضوع جدید خواهیم داشت با عنوان نرخ خطای مثبت کاذب. پارامتر مهم دیگر این است که چه تعداد تابع هش نیاز داریم؟

اینجا است که تحقیقات دانشگاهی می‌تواند به کمک ما بیاد(این موضوع را برای این اشاره کردم که بعضی از دوستان فکر...

لطفا برای مشاهده کامل مطالب در انجمن ثبت نام کنید.

 

[دیکتاتورs.yavarnia]

کاربردها
بلوم فیلتر برای بررسی عضو داخل یک مجموعه است. مثال ساده بلوم فیلتر برای کاهش هزینه مراجعه به دیسک یا شبکه برای کلیدهای ناموجود است. همونطور که ما می‌توانیم ببینیم بلوم فیلترها می توانند یک کلید را در O(k) جست و جو کنند که k تعداد تابع هش است. این بسیار سریعتر هست که کلید ناموجود را جست و جو کنیم. اگر عنصر در بلوم فیلتر نباشد پس ما نیازی به جست و جوی پر هزینه نداریم. از طرف دیگه اگر عنصر در بلوم فیلتر موجود باشد ما جست و جو را انجام می‌دهیم و می‌توانیم انتظار داشته باشیم که در برخی موارد ما نرخ خطای مثبت کاذب(false positive rate) داشته باشیم. و عنصر موجود نباشد. در ادامه برخی مثال‌های استفاده از بلوم فیلتر را معرفی می‌کنیم.

من در این قسمت در مورد یکی از...

لطفا برای مشاهده کامل مطالب در انجمن ثبت نام کنید.

 

[دیکتاتورs.yavarnia]

مثال های استفاده از بلوم فیلتر:

• برای هشدار به کاربران در مورد ضعیف بودن پسورد که در بالا توضیح داده شد.
• برای جلوگیری از دسترسی کاربران به سایت های مخرب
• برای بررسی اینکه چه کاربرانی قبلا از سایت شما بازدید کردند بر اساس IP هاشون.
• برای بررسی اینکه چه تعداد از کاربران محتوای سایت شما را خوانده اند

جالبه بدونید که خود سایت Medium هم از ساختار داده بلوم فیلتر استفاده می‌کنه که توضیحات کامل ترش را اینجا می‌تونید مطالعه کنید.

اگر هم علاقه دارید به صورت عملی با بلوم فیلتر بازی کنید و دقیق تر درکش کنید اینجا می‌تونید یک نسخه تحت وب را تست کنید.

در پست های آینده سعی می‌کنم یک مثال کاربردی را بصورت کدنویسی پیاده سازی کنم و شرح بدم.