فیلتر بلوم

احتمالاتی

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

فیلتر بلوم یک آرایه‌ی m بیتی و k تابع درهم‌سازی است (اینجا m = 16 و k = 2):

ادامه‌ی توضیح ↓

زمان: O(k) per key for k hash functions
حافظه: m bits
هوروویتز–ساهنی، فصل ۸

ورودی:

n=4 · target=12خروجی PDF

پرس‌وجوی ۱۲ که درج شده؛ هر دو بیتش یک است: «شاید هست» (و واقعاً هست).

def bloom_filter(keys, query):
m = 16
bits = [0] * m
for key in keys:
for seed in (3, 7):
h = (key * seed + 1) % m
bits[h] = 1
for seed in (3, 7):
h = (query * seed + 1) % m
if bits[h] == 0:
return False
return True

ناوردا: برای هر کلید درج‌شده، همه‌ی بیت‌های h₁(k) و h₂(k) یک‌اند؛ پس کلید درج‌شده هیچ‌وقت «قطعاً نیست» نمی‌گیرد.

شروع اجرا

متغیرهای محلی

query12

نارنجی = در همین گام عوض شد

`keys` list

5122033

Call stack

bloom_filter()خط 1

گام ۱ از ۴۴

رشد تعداد عملیات با اندازه‌ی ورودی

میانگین ۱۲ گراف تصادفی برای هر n (با seed ثابت). نشانگر توخالی = ورودی فعلی.

set_bit
ورودی فعلی (n=4)

نمایش به شکل جدول

n	set_bit
4	8
6	12
8	16
10	20
12	24

توضیح

ایده

فیلتر بلوم یک آرایه‌ی m بیتی و k تابع درهم‌سازی است (اینجا m = 16 و k = 2):

درج: برای کلید، بیت‌های h₁(key) و h₂(key) را یک کن.
پرس‌وجو: اگر حتی یکی از بیت‌های h₁(q) و h₂(q) صفر بود، q قطعاً درج نشده. اگر همه یک بودند، q شاید درج شده باشد.

چرا «شاید»؟

بیت‌ها را کلیدهای مختلف با هم یک می‌کنند. ممکن است بیت‌های یک کلید درج‌نشده را کلیدهای دیگر یک کرده باشند: مثبت کاذب. ولی منفی کاذب هیچ‌وقت پیش نمی‌آید. ورودی «مثبت کاذب» یک نمونه است.

هزینه و کاربرد

حافظه فقط m بیت است، هر چقدر هم کلیدها بزرگ باشند. برای همین فیلتر بلوم جلوی جستجوهای گران را می‌گیرد: مثلاً پایگاه داده قبل از خواندن دیسک می‌پرسد «شاید هست؟» و اگر جواب «قطعاً نیست» بود، دیسک را نمی‌خواند.

در trace به چه چیزی نگاه کنی

میله‌ها همان بیت‌ها هستند (۰ یا ۱)؛ فلش h بیتی است که تنظیم یا بررسی می‌شود.
ورودی «فیلتر شلوغ» را ببین: تقریباً همه‌ی بیت‌ها یک شده‌اند.