فرض کنید در حال ایجاد حساب کاربری در Gmail هستید، می خواهید یک نام کاربری خاص انتخاب کنید، پیامی با عنوان “Username از قبل گرفته شده است“ دریافت می کنید. شما تاریخ تولد خود را به همراه نام کاربری اضافه کردید، هنوز شانسی وجود ندارد که نام کاربری مورد علاقه تان را انتخاب کنید. واقعا ناامید کننده است، نه؟
اما آیا تا به حال به این موضوع فکر کرده اید که با جستجوی میلیون ها نام کاربری ثبت شده با آن، دسترسی به نام کاربری را با چه سرعتی بررسی می کند. راه های زیادی برای انجام این کار وجود دارد.به طور مثال می توان از جستجوی خطی یا دویی استفاده کرد اما روش و الگوریتمی خوبی نیست چون در داده های زیاد زمان اجرای بیشتری دارند. اینجاست که باید دنبال روش بهینه ای باید باشیم!
Bloom Filter یک ساختار داده ای است که این کار را به صورت بهینه انجام می دهد
برای درک Bloom Filter، باید بدانید که Hash چیست. یک تابع درهم ساز ورودی و خروجی ها را یک شناسه منحصر به فرد با طول ثابت می گیرد که برای شناسایی ورودی استفاده می شود.
تعریف Bloom Filter
در واقع یکBloom Filter ساختار داده هست که برای بررسی احتمالاتی کارآمد در یک فضا است که برای تست اینکه آیا یک عنصر(نام کاربری) عضو یک مجموعه (لیست نام کاربری ها) است یا خیر استفاده می شود. به عنوان مثال، بررسی در استفاده نشدن نام کاربری مساله عضویت تنظیم شده است، که در آن مجموعه لیست تمام نام های کاربری ثبت شده است. هزینه ای که ما برای کارایی می پردازیم این است که در ذات احتمالاتی است. یعنی ممکن است نتایج مثبت کاذبی وجود داشته باشد. به معنای مثبت کاذب، ممکن است بگوید که نام کاربری داده شده قبلا استفاده شده است اما در واقع اینطور نیست.
ویژگی های جذاب و جالب Bloom Filter
برخلاف یک جدول هش استاندارد، یک Bloom Filter با اندازه ثابت می تواند مجموعه ای با تعداد دل خواه از عناصر را نشان دهد.
اضافه کردن یک عنصر هرگز به مشکل نمی خورد. با این حال، نرخ مثبت کاذب به طور پیوسته با اضافه شدن عناصر افزایش می یابد تا زمانی که تمام بیت های فیلتر بر روی 1 تنظیم شوند، که در آن نقطه همه پرس و جوها نتیجه مثبت می دهند.
Bloom Filter هرگز نتیجه منفی کاذب ایجاد نمی کنند، یعنی به شما می گویند که یک نام کاربری زمانی که واقعا وجود دارد، وجود ندارد.
حذف عناصر از فیلتر ممکن نیست، زیرا اگر یک عنصر را با پاک کردن بیت ها در شاخص های تولید شده توسط k تابع هش حذف کنیم، ممکن است باعث حذف چند عنصر دیگر شود. مثال – اگر با پاک کردن بیت در ۱، ۴ و ۷، “nerd” را حذف کنیم (در مثال زیر)، ممکن است در نهایت “nerd” را حذف کنیم همچنین چون بیت در اندیس ۴ ۰ می شود و فیلتر شکوفه ادعا می کند که “nerd” وجود ندارد.
طبق تعریف بلوم فیلتر می‌تونه یک مقدار را در حالت‌های “احتمال وجود آن در مجموعه است” یا “قطعا در آن مجموعه نیست” بررسی کند. تفاوت ظریف بین احتمالا و قطعا نه در اینجا بسیار مهم است.
فرض کنیم در یک کتاب خانه هر کتابی که به کتاب خانه اضافه می کنیم در یک لیستی بنویسیم حال اگر بخواهیم یک کتابی به نام X را جستجو کنیم دیگه کل کتاب خانه رو دنبال کتاب نمی گردیم لیست را نگاه می کنیم اگر در لیست بود می گویم که کتاب در لیست هست و احتمال دارد که کتابی در کتاب خانه باشد ولی در لیست نباشد.
آرایه ای از m بیت است که همگی روی صفر تنظیم شده اند
برای محاسبه هش ها برای یک ورودی داده شده به k عدد تابع هش نیاز داریم. وقتی می خواهیم یک آیتم را به فیلتر اضافه کنیم، بیت ها در k اندیس (h۱) (x)، h۲ (x)،… hk (x) تنظیم می شوند، که در آن اندیس ها با استفاده از توابع درهم ساز محاسبه می شوند.
به طور مثال – فرض کنید می خواهیم “geeks” را در فیلتر وارد کنیم، ما از ۳ تابع هش و یک آرایه بیتی با طول ۱۰ استفاده می کنیم، که در ابتدا همه آن ها روی صفر تنظیم شده اند. ابتدا هش ها را به صورت زیر محاسبه می کنیم:
h1(“geeks”) % 10 = 1
h2(“geeks”) % 10 = 4
h3(“geeks”) % 10 = 7
دوباره می خواهیم وارد “nerd” شویم، به همین ترتیب، هش ها را محاسبه خواهیم کرد.
h1(“nerd”) % 10 = 3
h2(“nerd”) % 10 = 5
h3(“nerd”) % 10 = 4
بیت ها را در شاخص های ۳، ۵ و ۴ به ۱ تنظیم کنید
حال اگر بخواهیم بررسی کنیم که “geeks” در فیلتر وجود دارد یا خیر. ما هم همین فرآیند را انجام خواهیم داد اما این بار به ترتیب معکوس. ما هش های مربوطه را با استفاده از h۱، h۲ و h۳ محاسبه می کنیم و بررسی می کنیم که آیا تمام این شاخص ها در آرایه بیتی روی 1 تنظیم شده اند یا خیر. اگر تمام بیت ها تنظیم شده باشند، می توانیم بگوییم که ” geeks” احتمالا وجود دارند. اگر هر یک از بیت های این شاخص ها ۰ باشند، آنگاه “geeks” قطعا وجود ندارد.
مثبت کاذب در Bloom Filter
سوال این است که چرا گفتیم “احتمالا وجود دارد“، چرا این عدم قطعیت هست. بیایید این موضوع را با یک مثال درک کنیم. فرض کنید می خواهیم بررسی کنیم که آیا “cat” وجود دارد یا خیر. ما هش ها را با استفاده از h۱، h۲ و h۳ محاسبه خواهیم کرد.
h1(“cat”) % 10 = 1
h2(“cat”) % 10 = 3
h3(“cat”) % 10 = 7
اگر آرایه بیتی را بررسی کنیم، بیت های این شاخص ها روی 1 تنظیم می شوند اما می دانیم که “cat” هرگز به فیلتر اضافه نشده است. بیت در اندیس 1 و 7 زمانی که “geeks” را اضافه کردیم و بیت 3 تنظیم شد “nerd” را اضافه کردیم.
بنابراین، از آنجا که بیت ها در شاخص های محاسبه شده قبلا توسط مورد دیگری تنظیم شده اند، Bloom Filter به اشتباه ادعا می کند که “cat” وجود دارد و نتیجه مثبت کاذب ایجاد می کند. بسته به کاربرد، ممکن است عیب بزرگ یا نسبتا خوب باشد.
ما می توانیم احتمال مثبت کاذب را با کنترل اندازه فیلتر بلوم کنترل کنیم. فضای بیشتر به معنای نکات مثبت کاذب کم تر است. اگر بخواهیم احتمال نتیجه مثبت کاذب را کاهش دهیم، باید از تعداد بیشتری تابع هش و آرایه بیتی بزرگ تر استفاده کنیم. این کار علاوه بر آیتم و بررسی عضویت، تاخیر را هم اضافه می کند.
عملیات اصلی درBloom Filter
درج (x): برای درج یک عنصر در فیلتر بلوم.
جستجوی (x): برای بررسی این که آیا یک عنصر در فیلتر بلوم با احتمال کاذب مثبت وجود دارد یا خیر.
نکته: نمی توانیم یک آیتم را در Bloom Filter حذف کنیم.
برنامه های از Bloom Filter استفاده می کنند:
- گوگل کروم: برای شناسایی URL های مخرب
- مدیوم: برای پیشنهاد مقالات مرتبط
- گوگل و Apache برای جستجو و فیلتر کردن استفاده می کنند
- حتی توی شبکه برای ارسال و دریافت بسته مورد استفاده قرار می گیرد
کاربرد های Bloom Filter
- برای جستجو و فیلتر کردن در دیتابیس
- برای آمار بازدید کنندگان از سایت
- برای بررسی و چک کردن قوی یا ضعیف بودن پسورد و اشتباه تایپی متن یا کلمه
- استفاده در Redis
نکات بد و معایب Bloom Filter
- Bloom Filter از عملیات حذف پشتیبانی نمی کند
- نرخ مثبت کاذب را نمی توان به صفر کاهش داد
- Bloom Filter روی دیسک به دلیل شاخص های تصادفی تولید شده توسط توابع هش به دسترسی تصادفی نیاز دارد.
منابع