Filtr Blooma

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania

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 | edytuj kod]

  • 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ącej wraz z parametrami m i k określają jakość działania filtru Blooma,
  • Z początku zbiór bitów jest pusty czyli wszystkie bity są zgaszone.

Podstawowe operacje na Filtrze Blooma[edytuj | edytuj kod]

  • Dodawanie elementu do zbioru:
  • Oblicza się wartość funkcji k
  • Zapala się k bitów
  • Sprawdzenie czy element należy do zbioru
  • Oblicza się wartość funkcji k
  • Jeśli co najmniej jeden z wyznaczonych bitów jest zgaszony, oznacza to, że element na pewno nie należy do zbioru.

Przykład[edytuj | edytuj kod]

  • k=3, m=18
  • Strzałki wskazują wartości funkcji haszujących dla x,y,z
  • Jedna z funkcji wyszła na 0 co oznacza, że elementu w nie ma w zbiorze

Bibliografia[edytuj | edytuj kod]