فیلتر بلوم چیست؟

به گزارش reportaj.me  و به نقل از wikipedia فیلتر بلوم یک ساختار داده احتمالی کارآمد در فضا است که توسط برتون هاوارد بلوم در سال ۱۹۷۰ طراحی شد و برای آزمایش اینکه آیا یک عنصر عضوی از یک مجموعه است استفاده می شود. مطابقت های مثبت کاذب ممکن است، اما منفی های کاذب امکان پذیر نیست – به عبارت دیگر، یک پرس و جو یا “احتمالاً در مجموعه” یا “قطعاً در مجموعه نیست” برمی گردد. المان‌ها را می‌توان به مجموعه اضافه کرد، اما حذف نشد (اگرچه می‌توان این مشکل را با نوع فیلتر Bloom شمارش کرد). هرچه موارد بیشتری اضافه شود، احتمال مثبت کاذب بیشتر می شود.

ایده سطح بالا این است که عناصر x∈X را به مقادیر y=h(x)∈Y با استفاده از تابع هش h نگاشت، و سپس با بررسی اینکه آیا y’=h(x)∈Y، عضویت x’ در X را آزمایش کنید. و این کار را با استفاده از چندین توابع هش h انجام دهید.

بلوم این تکنیک را برای برنامه‌هایی پیشنهاد کرد که در آن‌ها در صورت استفاده از تکنیک‌های هش بدون خطا «معمولی»، مقدار داده‌های منبع به مقدار غیرعملی زیادی حافظه نیاز دارد. او الگوریتم خط خطی را برای فرهنگ لغت ۵۰۰۰۰۰ کلمه مثال زد که ۹۰٪ از آن از قوانین خط خطی ساده پیروی می کنند، اما ۱۰٪ باقیمانده نیاز به دسترسی های گران دیسک برای بازیابی الگوهای خط خطی خاص دارند. با حافظه هسته کافی، می توان از هش بدون خطا برای حذف تمام دسترسی های غیر ضروری دیسک استفاده کرد. از سوی دیگر، با حافظه هسته محدود، تکنیک بلوم از یک ناحیه هش کوچکتر استفاده می کند، اما همچنان بسیاری از دسترسی های غیر ضروری را حذف می کند. به عنوان مثال، یک منطقه هش تنها ۱۵٪ از اندازه مورد نیاز یک هش ایده آل بدون خطا، ۸۵٪ از دسترسی های دیسک را حذف می کند.

به طور کلی، کمتر از ۱۰ بیت در هر عنصر برای یک درصد احتمال مثبت کاذب، مستقل از اندازه یا تعداد عناصر در مجموعه مورد نیاز است.

توضیحات الگوریتم

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

برای افزودن یک عنصر، آن را به هر یک از توابع هش K تغذیه کنید تا موقعیت‌های آرایه k را بدست آورید. بیت ها را در تمام این موقعیت ها روی ۱ قرار دهید.

برای پرس و جو برای یک عنصر (آزمایش اینکه آیا در مجموعه است یا خیر)، آن را به هر یک از توابع هش k تغذیه کنید تا موقعیت های k آرایه را بدست آورید. اگر هر یک از بیت ها در این موقعیت ها ۰ باشد، عنصر قطعاً در مجموعه نیست. اگر اینطور بود، پس از درج همه بیت ها روی ۱ تنظیم می شد. اگر همه ۱ باشند، یا عنصر در مجموعه است، یا بیت ها به طور تصادفی در حین درج عناصر دیگر روی ۱ تنظیم شده اند که نتیجه آن مثبت کاذب است. در یک فیلتر بلوم ساده، هیچ راهی برای تمایز بین این دو مورد وجود ندارد، اما تکنیک های پیشرفته تر می توانند این مشکل را برطرف کنند.

نیاز به طراحی k توابع هش مستقل مختلف می تواند برای k بزرگ بازدارنده باشد. برای یک تابع هش خوب با یک خروجی گسترده، باید همبستگی کمی بین فیلدهای بیتی مختلف چنین هش وجود داشته باشد، بنابراین می توان از این نوع هش برای تولید چندین توابع هش «متفاوت» با برش خروجی آن به چند بیت استفاده کرد. زمینه های. از طرف دیگر، می توان k مقدار اولیه مختلف (مانند ۰، ۱، …، k-1) را به یک تابع هش که مقدار اولیه می گیرد، ارسال کرد. یا این مقادیر را به کلید اضافه کنید (یا اضافه کنید). برای m و/یا k بزرگتر، استقلال در میان توابع هش را می توان با افزایش ناچیز در نرخ مثبت کاذب کاهش داد.(به طور خاص، Dillinger & Manolios (2004b) اثربخشی استخراج شاخص‌های k را با استفاده از هش‌سازی دوگانه و هش سه‌گانه نشان می‌دهند، انواعی از هش دوگانه که به طور موثر مولدهای اعداد تصادفی ساده هستند که با دو یا سه مقدار هش تولید می‌شوند.)

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

حذف یکباره یک عنصر از فیلتر بلوم را می توان با داشتن یک فیلتر بلوم دوم که حاوی موارد حذف شده است شبیه سازی کرد. با این حال، مثبت کاذب در فیلتر دوم به منفی کاذب در فیلتر ترکیبی تبدیل می شود که ممکن است نامطلوب باشد. در این رویکرد افزودن مجدد آیتم حذف شده قبلی امکان پذیر نیست، زیرا باید آن را از فیلتر “حذف شده” حذف کرد.

اغلب اتفاق می افتد که همه کلیدها در دسترس هستند، اما شمارش آنها گران است (مثلاً نیاز به خواندن دیسک زیاد است). هنگامی که نرخ مثبت کاذب بیش از حد بالا می رود، فیلتر را می توان بازسازی کرد. این باید یک رویداد نسبتا نادر باشد.

مزایای مکان و زمان

فیلترهای Bloom در حالی که خطرات مثبت کاذب را به خطر می اندازند، دارای مزیت فضایی قابل توجهی نسبت به سایر ساختارهای داده برای نمایش مجموعه ها هستند، مانند درختان جستجوی باینری خود متعادل کننده، تلاش ها، جداول هش یا آرایه های ساده یا لیست های پیوندی ورودی ها. بسیاری از این موارد نیاز به ذخیره حداقل خود اقلام داده دارند، که می‌تواند از تعداد کمی بیت، برای اعداد صحیح کوچک، تا تعداد دلخواه بیت‌ها، مانند رشته‌ها (از آنجایی که می‌توانند فضای ذخیره‌سازی را بین عناصر به اشتراک بگذارند، مستثنی هستند.» با پیشوندهای مساوی). با این حال، فیلترهای بلوم به هیچ وجه موارد داده را ذخیره نمی کنند و باید راه حل جداگانه ای برای ذخیره سازی واقعی ارائه شود. ساختارهای پیوندی یک فضای خطی اضافی را برای نشانگرها ایجاد می کنند. یک فیلتر بلوم با خطای ۱% و مقدار بهینه k، در مقابل، صرف نظر از اندازه عناصر، تنها به ۹.۶ بیت برای هر عنصر نیاز دارد. این مزیت تا حدی ناشی از فشرده بودن آن است که از آرایه ها به ارث رسیده است و تا حدودی از ماهیت احتمالی آن ناشی می شود. نرخ مثبت کاذب ۱% را می توان با افزودن تنها ۴.۸ بیت به ازای هر عنصر، ده برابر کاهش داد.

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

فیلترهای بلوم همچنین دارای خاصیت غیرمعمولی هستند که زمان مورد نیاز برای افزودن آیتم ها یا بررسی اینکه آیا یک آیتم در مجموعه است یک ثابت ثابت O(k) است که کاملا مستقل از تعداد آیتم های موجود در مجموعه است. هیچ ساختار داده مجموعه فضای ثابت دیگری این ویژگی را ندارد، اما میانگین زمان دسترسی جداول هش پراکنده می تواند آنها را در عمل سریعتر از برخی فیلترهای بلوم کند. با این حال، در پیاده‌سازی سخت‌افزار، فیلتر Bloom می‌درخشد زیرا جستجوهای k آن مستقل هستند و می‌توانند موازی شوند.

برای درک کارایی فضای آن، مقایسه فیلتر بلوم عمومی با حالت خاص آن زمانی که k = 1 است، آموزنده است. به این معنی که آرایه باید بسیار بزرگ باشد و حاوی صفرهای طولانی باشد. محتوای اطلاعات آرایه نسبت به اندازه آن کم است. فیلتر بلوم تعمیم یافته (k بزرگتر از ۱) اجازه می دهد تا بیت های بیشتری تنظیم شود در حالی که نرخ مثبت کاذب پایینی را حفظ می کند. اگر پارامترهای (k و m) به خوبی انتخاب شوند، تقریباً نیمی از بیت‌ها تنظیم می‌شوند و ظاهراً تصادفی هستند و افزونگی را به حداقل می‌رسانند و محتوای اطلاعات را به حداکثر می‌رسانند.