فیلتر بولوم

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

فیلتر بولوم در سال ۱۹۷۰ به وسیله آقای بولوم ارائه شد. این فیلتر یک داده ساختار احتمالاتی با سایز بسیار کارامد است. وقتی مایلیم وجود عضوی را در مجموعه آزمون کنیم این داده ساختار بسیار کارامد هست.
فرض کنید می‌خواهیم وجود یک عنصری را در مجموعه جستجو کنیم، اگر داده ساختار به شما جواب داد که این عضو در مجموعه وجود دارد احتمال دارد که وجود نداشته باشد. اما اگر بگوید وجود ندارد، قطعاً درست هست. بر این اساس خطای مثبت داریم ولی خطای منفی امکان پذیر نمی‌باشد.
این داده ساختار امکان درج عنصر را به ما می‌دهد ولی امکان حذف آن وجود ندارد. هرچه بیشتر عنصر به آن اضافه شود احتمال خطای مثبت بیشتر می‌شود. یعنی احتمال اینکه داده ساختار به شما بگوید عضوی در مجموعه وجود دارد اما در واقع وجود نداشته باشد بیشتر می‌شود.

پیچیدگی زمانی فیلتر بلوم (k)O (در عملیات درج عنصر، جستجوی عنصر و حذف عنصر) است که K به معنی تعداد تابع درهم ساز می باشد.

توصیف الگوریتم[ویرایش]

یک فیلتر بولوم خالی متشکل از یک آرایه ی m بیتی می‌باشد که تمامی عناصر آن صفر است.
همچنین به تعداد K تابع درهم سازی در اختیار هست. که هرکدام از آنها یک عدد را به یکی از خانه‌های آرایه فیلتر بولوم نظیر می‌کند.

نکته : می توان برای هر تابع درهم ساز، یک آرایه m بیتی در نظر گرفت.

مثال یک آرایه و K تابع درهم ساز : عنصر اندیس خروجی هرکدام از توابع درهم ساز در هر یک از مقادیر وارد شده در تنها آرایه موجود، یک می شوند.

مثال برابری تعداد آرایه خالی و توابع درهم ساز : اگر به اضای K تابع درهم ساز، همان تعداد آرایه داشته باشیم، عنصر اندیس خروجی هرکدام از توابع درهم ساز در آرایه متناضر با تابع درهم ساز، یک می شوند.

درج عنصر[ویرایش]

برای این کار ابتدا عدد مورد نظر را به K تابع درهم سازی می‌دهیم. بر این اساس به تعداد K موقعیت در آرایه برای این عدد مشخص می‌شود. مقدار آرایه در موقعیت‌های مشخص شده را یک می‌کنیم. به این ترتیت عضو مورد نظر در فیلتر بولوم درج شد.

جستجو عنصر[ویرایش]

فرض کنید می‌خواهیم وجود یا عدم وجود عنصر x را در فیتر بولوم بررسی کنیم.
ابتدا این عنصر به K تابع درهم سازی داده و K موقعیت این عدد را در آرایه بولوم مشخص می‌کنیم. سپس مقادیر آرایه را در این K محل بررسی می‌کنیم. اگر در تعداد یک یا بیشتری خانه مقدار صفر بود، فیلتر با قطعیت جواب می‌دهد که این عنصر در آرایه وجود ندارد، زیرا اگر بود باید تمامی این K محل یک می‌بود. اما اگر تمامی آنها یک بود، معلوم نیست که این یک شدن به خاطر وجود این عنصر هست، یا به خاطر درج‌های دیگر عناصر منجر به یک شدن این خانه شده‌است. بنابراین جواب می‌دهد که احتمالاً این عنصر در فیلتر حضور دارد. از اینجا معلوم می‌شود که هرچه بیشتر عضو در آرایه درج بشود، احتمال غلط بودن جواب وجود عنصر بیشتر می‌شود.

حذف عنصر[ویرایش]

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

حذف از فیلتر بلوم، در الگوریم های تغریبی کاربردهای مهمی را شامل می شود. در الگوریتم تشخیص تقریبی تکرار در جریان داده، هنگامی که داده های ورودی بیش از حد در فیلتر بلوم درج می گردند، K فضای آرایه های درهم سازی عملاً پر می شود و بررسی داده در آرایه ها کارایی ندارد (جواب همیشه بله است؛ نکته: در اینصورت باید در تمامی آرایه های فیلتر بلوم، اقدام به عمل re hash نمود و این عمل بسیار هزینه بر است)، بنابراین اقدام به حذف داده می نماید. حذف هر عنصر از فیلتر بلوم، قطعیت را کاهش می دهد، اما با درج عنصر جدید در آرایه و حذف خانه قدیمی در آرایه، به یک تشخیص تغریبی می رسیم.[1]

کاربرد[ویرایش]

کاربرد فیلتر بلوم در کامپیوتر، کاهش بار سرور (کاهش پیچیدگی زمانی) و در عین حال استفاده اندک از حافظه می باشد.

به عنوان مثال می خواهیم از درج کلمات نامناسب توسط کاربر جلوگیری کنیم، در این صورت باید کلمه به کلمه در جمله را در بانک اطلاعاتی جستجو کنیم. در حالت عادی پیچیدگی زمانی جستجوی خطی برابر است با (n)O حال اگر داده ها از قبل مرتب شده باشند پیچیدگی زمانی برابر است با ((n)LOG)O، اگر از قبل جدول هش ایجاد شده باشد پیچیدگی زمانی برابر (1)O است (این عمل به یک آرایه ثابت و رزرو شده نیازمند است که حجم زیادی از حافظه را اشغال می نماید). در صورت استفاده از فیلتر بلوم، ابتدا کلیه کلمات نامناسب در فیلتر بلوم درج می گردند. برای اطمینان حاصل کردن از نامناسب نبودن کلمه، آن را در فیلتر بلوم بررسی می نماییم؛ اگر فیلتر بلوم جواب دهد که این کلمه در مجموعه وجود دارد، احتمال دارد که وجود نداشته باشد و در این صورت برای حصول اطمینان از نامناسب نبودن کلمه باید آن را در بانک اطلاعاتی بررسی نمود، اما اگر بگوید وجود ندارد، قطعاً درست هست و دیگر در بانک اطلاعاتی جستجو انجام نمی شود.

مثال حذف عنصر از فیلتر بلوم[ویرایش]

مسئله : جلوگیری از حمله DDOS با استفاده از تشخیص تقریبی تکرار در جریان داده[1]

نحوه عملکرد در 3 بند خلاصه می شود.

1- ابتدا درخواست کننده تشخیص داده میشود؛ سرویس گیرنده کاربر است یا کامپیوتر (تکرار در درخواست های مکرر و بیش از حد به سرور را، به عنوان کامپیوتر، تشخیص می دهد)
2- IP متعلق به کامپیوتر سرویس گیرنده در هر بار تکرار درخواست، در آرایه های فیلتر بلوم درج می گردد.

3- در صورت رسیدن به مرز اشباع (درصدی که آرایه می تواند داده در خود نگهداری کند، مثلاً مرز 60 درصد)، اقدام به حذف داده های قدیمی می نماید. راه حل معمول، به کارگیری سیاست اخراج تصادفی برای بیت از فیلترهای بلوم به جای عناصر جدید و نگه داشتن FPR (نرخ مثبت کاذب) شود.

(نکته : هر 3 بند به طور مداوم انجام می شود.)

سوال : وقتی می توان، IP کامپیوتر سرویس گیرنده را برای همیشه فیلتر کنند چرا صرفاً از عملکرد خالص فیلتر بلوم بدون حذف داده استفاده نمی کنند؟

جواب : برای هر بار اتصال به اینترنت نیاز به یک IP هست، این IP ها به دو گروه پویا و ایستا تقسیم میشوند؛ در حملات DDOS، حمله کننده برای یک مدت زمان اندک از یک IP پویا استفاده می کند، در واقع IP های خود را تغییر می دهند. حال اگر به طور مداوم چندین IP بسته شوند، نه تنها حمله کننده را محدود نکرده ایم، بلکه از دسترسی به جمعیتی از افراد که به طور تصادفی به یک IP پویا متصل می شوند، جلوگیری کرده ایم.

منابع[ویرایش]