من اولین بار در مورد فیلترهای بلوم از استادم در IIT Madras زمانی که در مورد حافظه پنهان صحبت می کردم شنیدم. من در آن زمان جوان و تازه وارد دنیای علوم کامپیوتر بودم، اما با این وجود، به یاد دارم که مجذوب فیلترهای بلوم ساده و در عین حال قدرتمند بودم. پس از نزدیک به 9 سال، متوجه شدم که وقتی کسی به ساختارهای داده اصلی فکر می کند، این ساختار داده ساده و در عین حال قدرتمند هنوز از بین می رود. این مقاله برای تصحیح آن است.
فیلترهای بلوم چیست؟
فیلترهای بلوم یک ساختار داده احتمالی هستند که برای بررسی عضویت استفاده می شود. آنها منفی های واقعی و مثبت های احتمالی را می دهند، به عنوان مثال، وقتی از یک فیلتر شکوفه می پرسم آیا عنصری در آن وجود دارد، پاسخ آن “قطعا نه” یا “شاید بله” خواهد بود. مزیت این است که آنها این کار را در زمان تقریباً ثابت با استفاده از هر فضای کوچک اضافی انجام می دهند. کنجکاو، اینطور نیست؟ اکنون توضیح خواهم داد که فیلتر شکوفه چگونه کار می کند و ماهیت پاسخ های آنها را خواهید فهمید.
فیلتر شکوفه دارای 2 جزء است:
- k توابع هش: یک تابع هش فقط تابعی است که یک رشته را می گیرد و یک «اثرانگشت» ریاضی از آن خروجی می گیرد.
- آرایه بیتی با اندازه N: هیچ چیز جالبی نیست، فقط N بیت.
افزودن یک عنصر
هنگامی که عنصر E را به فیلتر شکوفه اضافه می کنیم، موارد زیر را انجام می دهیم:
- هش E با هر یک از توابع هش k و ایجاد k هش h1، h2…hk.
- یافتن یادآوری زمانی که …