Filtr Blooma
Filtr Bloom to struktura danych, która umożliwia komputerom sprawdzenie, czy dany element występuje w zbiorze. Filtry Bloom używają w tym celu funkcji hash. Dla każdego dodanego elementu obliczana jest wartość haszu. Gdy dodawany jest nowy element, jego wartość hash jest porównywana z wartością innych elementów w zbiorze. Filtr Bloom to probabilistyczna struktura danych. Można uzyskać wartość fałszywie dodatnią, ale nie można uzyskać fałszywie ujemną. Innymi słowy, zapytanie zwraca albo "ewentualnie w zestawie" albo "zdecydowanie nie w zestawie". Elementy mogą być dodane do zestawu, ale nie usunięte. Dla każdego dodanego elementu rośnie prawdopodobieństwo otrzymania fałszywego pozytywu.
Edward Bloom zaproponował filtr Bloom w 1970 roku. W artykule Bloom zakłada, że na końcu wiersza znajduje się algorytm pozwalający na łączenie słów. Według przykładu, większość słów ma proste wzorce myślenia hipenatycznego. Ale około 10% słów wymaga czasochłonnych poszukiwań, aby uzyskać właściwą regułę. Jego przypadek to łączenie około 500.000 słów. Widział, że użycie "normalnych", bezbłędnych technik haszyszowania, przechowywanie wzorów myślenia wymagałoby dużej ilości pamięci. Odkrył, że używając swojej techniki, mógł wyeliminować większo¶ć lookupsów. Dla przykładu, obszar haszyszu tylko 15% rozmiaru wymaganego przez idealny bezbłędny haszysz nadal eliminuje 85% dostępu do dysku.
Ogólnie rzecz biorąc, mniej niż 10 bitów na element jest wymagane dla 1% fałszywie dodatniego prawdopodobieństwa, niezależnie od wielkości lub liczby elementów w zestawie.
Pytania i odpowiedzi
P: Co to jest filtr Blooma?
O: Filtr Blooma to struktura danych, która pozwala komputerom sprawdzić, czy dany element występuje w zbiorze. Wykorzystuje do tego funkcje skrótu, obliczając wartość skrótu każdego dodanego elementu i porównując ją z innymi elementami w zbiorze.
P: Jakim typem struktury danych jest filtr Blooma?
O: Filtr Blooma jest probabilistyczną strukturą danych, co oznacza, że istnieje możliwość otrzymania fałszywych pozytywów, ale nie fałszywych negatywów.
P: Kto zaproponował filtr Blooma?
O: Edward Bloom zaproponował filtr Blooma w 1970 roku.
P: Jaki był przykład Edwarda na zastosowanie jego techniki?
A: Przykładem Edwarda było łączenie około 500.000 słów; stwierdził, że stosując jego technikę, może wyeliminować większość wyszukiwań i zmniejszyć dostęp do dysku o 15%.
P: Ile bitów na element potrzeba, aby prawdopodobieństwo fałszywego pozytywu wynosiło 1%?
O: Do uzyskania 1% prawdopodobieństwa fałszywie pozytywnego potrzeba mniej niż 10 bitów na element, niezależnie od wielkości i liczby elementów w zbiorze.
P: Czy można usunąć elementy z filtra bloomowego po ich dodaniu?
O: Nie, elementy można tylko dodawać do zbioru, ale nie można ich usuwać.
P: Czy dodanie większej ilości elementów zwiększa czy zmniejsza prawdopodobieństwo uzyskania wyniku fałszywie pozytywnego?
O: Dodanie większej ilości elementów zwiększa prawdopodobieństwo uzyskania wyniku fałszywie pozytywnego.
