Filtr Blooma
Filtr Blooma – tablica bitowa stworzona przez Burtona H. Blooma w 1970 roku. Pierwotnie Filtr Blooma był wykorzystywany do implementacji baz danych, obecnie jest bardzo popularny w sieciach komputerowych. Filtr ten jest strukturą prostą i wydajną pamięciowo, która ma na celu reprezentować zadany zbiór elementów. Zastosowanie znajduje w szybkim określaniu przynależności podanych argumentów do tego zbioru elementów. Filtr Blooma ma jedną wadę. Jego wydajność (oszczędność pamięci) jest możliwa dzięki wprowadzeniu marginesu błędnych pozytywnych odpowiedzi. Efektem tego zabiegu są straty, spowodowane błędnymi informacjami, które często są większe od zaoszczędzonej pamięci.
Implementacja
edytuj- Filtr Blooma jest tablicą o m-bitach.
- Filtr Blooma wykorzystuje k losowych i niezależnych funkcji haszujących, które przyjmują wartość z przedziału [0,m).
- Jakość funkcji haszujących oraz parametry m i k określają jakość działania filtru Blooma.
- Na początku tablica bitów jest pusta, czyli wszystkie bity są zgaszone.
Podstawowe operacje
edytuj- Dodawanie elementu do zbioru:
- Oblicza się k wartości funkcji haszujących.
- Zapala się k bitów.
- Sprawdzenie czy element należy do zbioru:
- Oblicza się k wartości funkcji haszujących.
- Jeśli co najmniej jeden z wyznaczonych bitów jest zgaszony, to element na pewno nie należy do zbioru.
Przykład
edytuj
- Parametry: k=3, m=18.
- Kolorowe strzałki wskazują wartości funkcji haszujących dla dodanych elementów x, y, z; szare – dla szukanego elementu w.
- Dla szukanego elementu w jedna z funkcji haszujących wskazuje w tablicy na wartość 0, co oznacza że tego elementu nie ma w zbiorze.
Bibliografia
edytuj- Filtry Blooma i systemy rozproszone. students.mimuw.edu.pl. [zarchiwizowane z tego adresu (2017-08-14)]. (plik pdf)