[Algorithm] Filtr Blooma
Czym jest Filtr Blooma
Burton Howard Bloom w 1970 roku opracował filtr (nazywany teraz Filtrem Blooma), który służy do testowania czy dany element znajduje się w zbiorze, czy nie. Filtr nie jest doskonały, gdyż możliwa jest fałszywa odpowiedź pozytywna ale już negatywna nie. Czyli odpowiada na pytanie "Czy dany element znajduje się w zbiorze?" odpowiedziami "nie" lub "może". Mimo wszystko w wielu przypadkach może być to ogromna oszczędność mocy obliczeniowej oraz pamięci.
Właściwości Filtru Blooma
odpowiedź negatywna jest zawsze pewna
odpowiedź pozytywna może być fałszywa
koszt dodania elementu i zapytania jest stały
Jak to działa?
Bierzemy więc tablicę m bitów. Dla przykładu niech będzie m = 16. Czyli nasz filtr będzie miał rozmiar 16 bitów. Na start wypełnioną 0 jak poniżej:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ---------------------------------------------- 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Teraz potrzebujemy k niezależnych funkcji hashujących zwracających wynik z zakresu [0, m). Na potrzeby przykładu niech k = 3. Dodając element do naszego filtru musimy wyliczyć odpowiednio hash korzystając ze wszystkich naszych funkcji.
element = 'foo' hash1(element) = 3 hash2(element) = 10 hash3(element) = 5
Następnie ustawiamy 1 na odpowiednich bitach:
0 0 0 1 0 1 0 0 0 0 1 0 0 0 0 0 ---------------------------------------------- 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 ^ ^ ^
Następnie dodajemy drugi element, licząc jego hashe i tak samo ustawiając 1 na odpowiednich bitach:
element = 'bar' hash1(element) = 4 hash2(element) = 3 hash3(element) = 8 0 0 0 1 1 1 0 0 1 0 1 0 0 0 0 0 ---------------------------------------------- 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 ^ ^ ^
Warto zwrócić uwagę, że ponownie pojawił się hash = 3 w takim wypadku bit pozostaje w stanie 1. Raz zapalony bit nie zmienia już swojego stanu. Teraz sprawdźmy, czy wyraz baz znajduje się w naszym zbiorze:
element = 'baz' hash1(element) = 7 hash2(element) = 5 hash3(element) = 4 0 0 0 1 1 1 0 0 1 0 1 0 0 0 0 0 ---------------------------------------------- 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 ^ ^ ^
Jeżeli choć jeden bit dla wyliczonych hashy jest 0 (a tak się stało dla hash1 = 7) oznacza to, że element na pewno nie znajduje się w zbiorze. Może się zdarzyć tak, że hashe się pokryją. Załóżmy kolejne sprawdzenie dla elementu qux
element = 'qux' hash1(element) = 10 hash2(element) = 8 hash3(element) = 3 0 0 0 1 1 1 0 0 1 0 1 0 0 0 0 0 ---------------------------------------------- 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 ^ ^ ^
W tym wypadku filtr mówi nam element może znajduje się w zbiorze. Więc aby mieć pewność należy wykonać dokładne sprawdzenie.
Właściwości Filtru Blooma c.d.
zawsze można dodać element do zbioru
nie można usunąć elementu zbioru
przepełniony filtr zawsze będzie zwracać true
prawdopodobieństwo fałszu można łatwo obliczyć (przy założeniu, że funkcje hashujące mają równy rozkład)
Obliczanie k niezależnych funkcji hashujących można zrównoleglić
Zastosowanie Filtru Blooma
Filtr w praktyce wykorzystywany jest przez m. in. Google Big Data, HBase czy Casandrę do ograniczenia operacji dyskowych. Bitcoin wykorzystuje go aby przyspieszyć synchronizację portfela. A Ethereum do szybkiego wyszukiwania dzienników na łańcuchu bloków. Systemy rozproszone wykorzystują go do decydowania który serwer odpytać o dany zasób co ogranicza zużywany transfer danych między sobą.
Jest to ciekawe podejście do dość popularnego problemu. Gotowy filtr można zapisać i przesyłać bez obawy o wyciek oryginalnych danych. Sam sposób jego wykorzystania jest już zależy od konkretnego przypadku. Problem usuwania elementu można rozwiązać tworząc drugi filtr, w którym będziemy trzymać usunięte elementy. Zachęcam do kreatywnego podejścia do rozwiązywania problemów. Czasem najlepsze rozwiązanie nie jest oczywiste dlatego warto rozszerzać swoją wiedzę w dziedzinie algorytmów.
Jakie inne znasz algorytmy lub struktury danych warte poznania?
Linki
Wiki Filtr Blooma
Mój skrypt testowy Filtru Blooma