فیلتر بولوم

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

فیلتر بولوم در سال ۱۹۷۰ به وسیله آقای بولوم ارائه شد. این فیلتر یک داده ساختار احتمالاتی با سایز بسیار کارامد است. وقتی مایلیم وجود عضوی را در مجموعه آزمون کنیم این داده ساختار بسیار کارامد هست.

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

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

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

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

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

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

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

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

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

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