PL 
EnglishDomyślny
Українська🌸 Filtr Blooma — probabilistyczne testowanie przynależności
Filtr Blooma sprawdza przynależność do zbioru za pomocą k funkcji haszujących na tablicy bitów: brak fałszywych negatywów, regulowane fałszywe pozytywy. Patrz, jak zapalają się bity, a stopa błędu podąża za (1−e^(−kn/m))^k.
O filtrze Blooma
Filtr Blooma to probabilistyczna struktura danych, która odpowiada na zapytania o przynależność w czasie O(1) i przestrzeni O(m), gdzie m to rozmiar tablicy bitowej — znacznie mniejszy niż przechowywanie samych elementów. Podczas wstawiania elementu k niezależnych funkcji haszujących odwzorowuje go na k pozycji w m-bitowej tablicy i ustawia te bity na 1. Aby sprawdzić przynależność, te same k pozycji jest odczytywanych: jeśli którakolwiek wynosi 0, element na pewno nie należy do zbioru; jeśli wszystkie wynoszą 1, prawdopodobnie należy. Bity nigdy nie są czyszczone, więc fałszywe negatywy są niemożliwe, ale kolizje haszy mogą powodować fałszywe pozytywy, których prawdopodobieństwo przybliża wzór (1 − e^(−kn/m))^k, gdzie n to liczba wstawionych elementów.
Ten symulator pozwala wpisywać słowa i dodawać je do interaktywnej wizualizacji tablicy bitowej, sprawdzać przynależność, by zobaczyć, jak fałszywe pozytywy pojawiają się wraz z zapełnianiem tablicy, oraz dostosowywać rozmiar tablicy m i liczbę funkcji haszujących k za pomocą suwaków. Teoretyczny współczynnik fałszywych pozytywów oraz zmierzony współczynnik na podstawie 2000 losowych zapytań testowych aktualizują się w czasie rzeczywistym, dzięki czemu kompromis między przestrzenią a dokładnością jest natychmiast widoczny.
Najczęściej zadawane pytania
Dlaczego filtr Blooma nigdy nie może dać fałszywego negatywu?
Podczas wstawiania elementu wszystkie k jego haszowanych pozycji bitowych jest ustawianych na 1 i nigdy nie są czyszczone. Dlatego jeśli sprawdzasz element, który faktycznie został wstawiony, wszystkie k bitów będzie równych 1, a filtr poprawnie zgłosi „prawdopodobnie w zbiorze”. Fałszywy negatyw wymagałby, aby bit wrócił do 0, co nigdy się nie zdarza.
Jaki jest wzór na prawdopodobieństwo fałszywego pozytywu?
Po wstawieniu n elementów do m-bitowej tablicy z k funkcjami haszującymi, ułamek bitów wciąż równych 0 wynosi w przybliżeniu e^(-kn/m), więc prawdopodobieństwo, że wszystkie k pozycji dla elementu spoza zbioru wynosi 1, to (1 - e^(-kn/m))^k. Na przykład dla m = 64, k = 3 i n = 10 elementów współczynnik fałszywych pozytywów wynosi w przybliżeniu 5%.
Jak wybrać optymalną liczbę funkcji haszujących k?
Wartość k = (m/n) × ln 2 minimalizuje współczynnik fałszywych pozytywów dla danych m i n. Zbyt mało funkcji haszujących pozostawia wiele bitów nieustawionych i zmniejsza rozróżnialność; zbyt wiele funkcji szybko zapełnia tablicę i zwiększa liczbę kolizji. Dla docelowego współczynnika błędu 1% optymalny rozmiar tablicy wynosi w przybliżeniu 9,6 bitu na wstawiony element.
Dlaczego nie można usuwać elementów ze standardowego filtra Blooma?
Usunięcie elementu wymagałoby wyczyszczenia jego k pozycji bitowych, ale te bity mogły zostać ustawione również przez inne wstawione elementy, więc ich wyczyszczenie po cichu wprowadziłoby fałszywe negatywy dla tamtych elementów. Zliczający filtr Blooma (Counting Bloom filter) zastępuje każdy bit małym licznikiem, zwiększanym przy wstawianiu i zmniejszanym przy usuwaniu, aby wspierać bezpieczne usuwanie kosztem dodatkowej pamięci.