آشنایی با Bloom Filter
فیلتر بلوم در سال ۱۹۷۰ به وسیله فردی به نام بلوم ارائه شد. این فیلتر یک داده ساختار احتمالاتی و تقریبی با پیچیدگی مکانی بسیار کارآمد است. وقتی مایلیم وجود عضوی را در مجموعه آزمون کنیم این داده ساختار بسیار کارآمد است.
فرض کنید میخواهیم وجود یک عنصری را در مجموعه جستجو کنیم، اگر داده ساختار به شما جواب داد که این عضو در مجموعه وجود دارد احتمال دارد که وجود نداشته باشد. اما اگر بگوید وجود ندارد، قطعاً درست هست. بر این اساس خطای مثبت داریم ولی خطای منفی امکان پذیر نمیباشد.
این داده ساختار امکان درج عنصر را به ما میدهد ولی امکان حذف آن وجود ندارد. هرچه بیشتر عنصر به آن اضافه شود احتمال خطای مثبت بیشتر میشود. یعنی احتمال اینکه داده ساختار به شما بگوید عضوی در مجموعه وجود دارد اما در واقع وجود نداشته باشد بیشتر میشود.
پیچیدگی زمانی فیلتر بلوم (k)O (در عملیات درج عنصر، جستجوی عنصر) است که K به معنی تعداد تابع درهم ساز می باشد
توصیف الگوریتم
یک فیلتر بلوم خالی متشکل از یک آرایه ی m بیتی میباشد که تمامی عناصر آن صفر است.
همچنین به تعداد K تابع درهم سازی در اختیار هست. که هرکدام از آنها یک عدد را به یکی از خانههای آرایه فیلتر بلوم نظیر میکند و خانه را از صفر به یک تغییر میدهند.
درج عنصر
برای این کار ابتدا عدد مورد نظر را به K تابع درهم سازی میدهیم. بر این اساس به تعداد K موقعیت در آرایه برای این عدد مشخص میشود. مقدار آرایه در موقعیتهای مشخص شده را یک میکنیم. به این ترتیت عضو مورد نظر در فیلتر بلوم درج شد.
جستجو عنصر
فرض کنید میخواهیم وجود یا عدم وجود عنصر x را در فیتر بلوم بررسی کنیم.
ابتدا این عنصر به K تابع درهم سازی داده و K موقعیت این عدد را در آرایه بلوم مشخص میکنیم. سپس مقادیر آرایه را در این K محل بررسی میکنیم. اگر در تعداد یک یا بیشتری خانه مقدار صفر بود، فیلتر با قطعیت جواب میدهد که این عنصر در آرایه وجود ندارد، زیرا اگر بود باید تمامی این K محل یک میبود. اما اگر تمامی آنها یک بود، معلوم نیست که این یک شدن به خاطر وجود این عنصر هست، یا به خاطر درجهای دیگر عناصر منجر به یک شدن این خانه شدهاست. بنابراین جواب میدهد که احتمالاً این عنصر در فیلتر حضور دارد. از اینجا معلوم میشود که هرچه بیشتر عضو در آرایه درج بشود، احتمال غلط بودن جواب وجود عنصر بیشتر میشود.
حذف عنصر
از آنجایی که خطای منفی در این فیلتر اجازه داده نمیشود، امکان حذف عنصر نیست. یعنی چون عدم وجود عنصر باید با قطعیت گفته شود، امکان حذف نداریم. این امر از اینجا حاصل میشود که موقعی که مایلیم عنصری را حذف کنیم، یعنی باید تمام بیتهای متناظر این عنصر را در آرایه صفر کنیم. به این ترتیب این عنصر حذف میشود. ولی ممکن است مکانهای عددهای دیگر با این عنصر اشتراکاتی داشته باشد که به اشتباه آن خانهها صفر شدهاست. بنابراین اگر بعد از حذف عنصر، قصد جستجوی عنصر دیگر را داشته باشیم، اگر فیلتر جواب دهد که این عنصر در آرایه وجود ندارد ممکن است جواب درستی نباشد. زیرا صفر بودن بعضی از موقعیتهای این عنصر در آرایه میتواند به معنی عدم وجود این عنصر نباشد.
کاربرد
کاربرد فیلتر بلوم در کامپیوتر، کاهش بار سرور (کاهش پیچیدگی زمانی) و در عین حال استفاده اندک از حافظه می باشد.
به عنوان مثال می خواهیم از درج رمزهای عبور نامناسب توسط کاربر جلوگیری کنیم، در این صورت باید کلمه به کلمه در جمله را در بانک اطلاعاتی جستجو کنیم. در حالت عادی پیچیدگی زمانی جستجوی خطی برابر است با (n)O حال اگر داده ها از قبل مرتب شده باشند پیچیدگی زمانی برابر است با ((n)LOG)O، اگر از قبل جدول هش ایجاد شده باشد پیچیدگی زمانی برابر (1)O است (این عمل به یک آرایه ثابت و رزرو شده نیازمند است که حجم زیادی از حافظه را اشغال می نماید). در صورت استفاده از فیلتر بلوم، ابتدا کلیه رمزهای عبور نامناسب در فیلتر بلوم درج می گردند. برای اطمینان حاصل کردن از نامناسب نبودن رمزعبور، آن را در فیلتر بلوم بررسی می نماییم؛ اگر فیلتر بلوم جواب دهد که این کلمه در مجموعه وجود دارد، احتمال دارد که وجود نداشته باشد و در این صورت برای حصول اطمینان از نامناسب نبودن کلمه باید آن را در بانک اطلاعاتی بررسی نمود، اما اگر بگوید وجود ندارد، قطعاً درست هست و دیگر در بانک اطلاعاتی جستجو انجام نمی شود.
دیدگاهتان را بنویسید
برای نوشتن دیدگاه باید وارد بشوید.