Filtr Blooma: Prawdopodobieczna Członowość Zbioru

A bit array representing a set

Burton Howard Bloom described this structure in 1970 as a way to test set membership without storing the entire set itself. A Bloom filter is an array of 'm' bits, all initially set to zero, alongside 'k' independent hash functions. To insert an item, its hash values are computed 'k' times, and the corresponding bits within the array are then set to one. To determine if an item might be present in the set, its hash values are calculated again using the same 'k' hash functions, and a check is performed: if even a single bit among those 'k' is zero, it definitively means the item was never inserted. If all 'k' bits are one, the item is likely present in the set.

This approach offers significant space savings when dealing with large sets, particularly when memory is limited. The accuracy of the Bloom filter depends on selecting appropriate hash functions and choosing suitable values for 'm' and 'k'. It’s important to note that a Bloom filter can only indicate whether an element *might* be present; it cannot guarantee its existence.

Bez fałszowych negatywnych ocen, regulowane fałszywe pozytywy

To jest cała propozycja wartości w jednym zdaniu: filtr Blooma nigdy nie zgłasza, że usuniętego elementu nie ma, ale może, z pewną prawdopodobieństwem, zgłosić, że element istnieje, gdy go nigdy nie wprowadzono. Fałszywy pozytyw występuje, gdy niezwiązane wpisy losowo ustawiają wszystkie k bitów zapytania nowego, wyłącznie przez kolizję hash. Nie ma mechanizmu fałszywej negatywnej oceny, ponieważ wpisanie zawsze tylko ustawia bity i nigdy ich nie usuwa.

function add(item) {
  for (let i = 0; i < k; i++) bits[hash(item, i) % m] = 1;
}
function mightContain(item) {
  for (let i = 0; i < k; i++)
    if (bits[hash(item, i) % m] === 0) return false;   // definitely not in the set
  return true;                                          // probably in the set
}

Fałszywy pozytywny wzór

Po wstawieniu n elementów do tablicy o m bitach z k funkcjami haszującymi, prawdopodobieństwo, że pojedynczy bit pozostaje na 0, wynosi około e do potęgi minus kn przez m. Zatem prawdopodobieństwo, że zapytanie o element nigdy nie wprowadzony znajdzie wszystkie k bitów ustawionych przypadkowo, wynosi w przybliżeniu (1 minus e do potęgi minus kn przez m) podniesione do potęgi k. Wyrażenie to jest zminimalizowane, dla ustalonej wartości m i n, gdy k równa się (m ponad n) razy logarytmu naturalnego 2 - w przybliżeniu 0,693 bitów warstw hash per bit budżetu na element. Wstawienie tego optymalnego wzoru daje znane oszacowanie, że około 10 bitów na element i 7 funkcji haszujących daje w przybliżeniu 1% fałszywych pozytywnych wyników.

Dlaczego warto w przypadku fałszywych pozytywów

Hash set przechowujący same elementy wymagałby pamięci proporcjonalnej do liczby i wielkości elementów. Bloom filter potrzebuje jedynie stałego rozmiaru bitowego tablicy, niezależnie od tego, jak duzi lub złożeni są elementy, kosztem okazjonalnego błędnego "może". Ta kompromisowa sytuacja jest idealna jako wstępny filtr przed czymś kosztownym: bazą danych sprawdzającą, czy klucz może istnieć przed kosztownym odczycie dyskowego, crawlerem pomijającym URL-e, które prawdopodobnie już odwiedził, CDN lub routerem decydującym, czy bufor prawdopodobnie zawiera element przed wykonaniem podróży sieciowej, lub korektorem słów sprawdzającym, czy słowo prawdopodobnie jest poprawne przed pełnym wyszukiwaniem w słowniku.

Variants worth knowing

A counting Bloom filter replaces each bit with a small counter, incremented on insert and decremented on delete, which restores support for removal at the cost of several times the memory. A cuckoo filter stores short fingerprints in a cuckoo hash table instead of raw bits, supports deletion natively, and at low false-positive rates uses less memory than a Bloom filter for the same guarantee - the modern default when deletion matters.

Często zadawane pytania

Wypróbuj na żywo

Wszystko powyżej działa bezpośrednio w Twojej przeglądarce — otwórz Bloom Filter i zmieniaj parametry podczas działania. Nic nie jest instalowane ani przesyłane na serwer, cały model działa w jednej karcie.