Alex całkiem dobrze to wyjaśnił. Dla tych, którzy nadal nie rozumieli, mam nadzieję, że ten przykład pomoże ci zrozumieć:
Powiedzmy, że pracuję dla Google, w zespole Chrome, i chcę dodać do przeglądarki funkcję, która powiadamia użytkownika, jeśli wprowadzony adres URL jest złośliwym adresem URL. Mam więc zbiór danych zawierający około 1 miliona złośliwych adresów URL, przy czym rozmiar tego pliku wynosi około 25 MB. Ponieważ rozmiar jest dość duży (duży w porównaniu z rozmiarem samej przeglądarki), przechowuję te dane na zdalnym serwerze.
Przypadek 1: Używam funkcji skrótu z tabelą skrótów. Decyduję się na wydajną funkcję mieszającą i uruchamiam wszystkie 1 milion adresów URL przez funkcję mieszania, aby uzyskać klucze skrótu. Następnie tworzę tablicę mieszającą (tablicę), w której klucz skrótu dałby mi indeks do umieszczenia tego adresu URL. Więc teraz, gdy już zaszyfowałem i zapełniłem tablicę haszującą, sprawdzam jej rozmiar. Przechowałem wszystkie 1 milion adresów URL w tabeli skrótów wraz z ich kluczami. Więc rozmiar wynosi co najmniej 25 MB. Ta tablica mieszająca, ze względu na swój rozmiar, będzie przechowywana na zdalnym serwerze. Kiedy pojawia się użytkownik i wpisuje adres URL w pasku adresu, muszę sprawdzić, czy jest złośliwy. W ten sposób uruchamiam adres URL za pomocą funkcji skrótu (sama przeglądarka może to zrobić) i otrzymuję klucz skrótu dla tego adresu URL. Muszę teraz wysłać żądanie do mojego zdalnego serwera za pomocą tego klucza skrótu, aby sprawdzić, czy określony adres URL w mojej tabeli skrótów z tym konkretnym kluczem jest taki sam, jak wpisany przez użytkownika. Jeśli tak, to jest złośliwe, a jeśli nie, to nie jest złośliwe. Dlatego za każdym razem, gdy użytkownik wprowadza adres URL, należy wysłać żądanie do zdalnego serwera, aby sprawdzić, czy jest to złośliwy adres URL. Zajmie to dużo czasu i spowolni moją przeglądarkę.
Przypadek 2: używam filtra bloom. Cała lista 1 miliona adresów URL jest przepuszczana przez filtr bloom przy użyciu wielu funkcji skrótu, a odpowiednie pozycje są oznaczone jako 1, w ogromnej tablicy zer. Powiedzmy, że chcemy fałszywie dodatniego wskaźnika 1%, używając kalkulatora filtra bloom ( http://hur.st/bloomfilter?n=1000000&p=0.01), uzyskujemy rozmiar wymaganego filtra bloom jako zaledwie 1,13 MB. Ten mały rozmiar jest oczekiwany, ponieważ mimo że rozmiar tablicy jest ogromny, przechowujemy tylko 1 lub 0, a nie adresy URL, jak w przypadku tablicy haszującej. Tablicę tę można traktować jako tablicę bitową. To znaczy, ponieważ mamy tylko dwie wartości 1 i 0, możemy ustawić pojedyncze bity zamiast bajtów. Zmniejszyłoby to zajmowane miejsce o 8 razy. Ten filtr bloom o wielkości 1,13 MB dzięki niewielkim rozmiarom może być przechowywany w samej przeglądarce internetowej !! Tak więc, gdy użytkownik przychodzi i wprowadza adres URL, po prostu stosujemy wymagane funkcje skrótu (w samej przeglądarce) i sprawdzamy wszystkie pozycje w filtrze bloom (który jest przechowywany w przeglądarce). Wartość 0 w dowolnej pozycji informuje nas, że ten adres URL ZDECYDOWANIE NIE znajduje się na liście złośliwych adresów URL i użytkownik może swobodnie kontynuować. W ten sposób nie nawiązaliśmy połączenia z serwerem, a tym samym zaoszczędziliśmy czas. Wartość 1 mówi nam, że URL MOŻE znajdować się na liście złośliwych adresów URL. W takich przypadkach wykonujemy wywołanie zdalnego serwera i tam możemy użyć innej funkcji skrótu z jakąś tablicą mieszającą, tak jak w pierwszym przypadku, aby pobrać i sprawdzić, czy adres URL jest rzeczywiście obecny. Ponieważ w większości przypadków adres URL nie jest złośliwy, mały filtr rozkwitu w przeglądarce pokazuje to, a tym samym oszczędza czas, unikając wywołań serwera zdalnego. Tylko w niektórych przypadkach, jeśli filtr bloom mówi nam, że URL MOŻE być złośliwy, tylko w takich przypadkach wywołujemy serwer. To „MOC” ma w 99% rację. W takich przypadkach wykonujemy wywołanie zdalnego serwera i tam możemy użyć innej funkcji skrótu z jakąś tablicą mieszającą, tak jak w pierwszym przypadku, aby pobrać i sprawdzić, czy adres URL jest rzeczywiście obecny. Ponieważ w większości przypadków adres URL nie jest złośliwy, mały filtr rozkwitu w przeglądarce pokazuje to, a tym samym oszczędza czas, unikając wywołań serwera zdalnego. Tylko w niektórych przypadkach, jeśli filtr bloom mówi nam, że URL MOŻE być złośliwy, tylko w takich przypadkach wywołujemy serwer. To „MOC” ma 99% racji. W takich przypadkach wykonujemy wywołanie zdalnego serwera i tam możemy użyć innej funkcji skrótu z jakąś tablicą mieszającą, tak jak w pierwszym przypadku, aby pobrać i sprawdzić, czy adres URL jest rzeczywiście obecny. Ponieważ w większości przypadków adres URL nie jest złośliwy, mały filtr rozkwitu w przeglądarce pokazuje to, a tym samym oszczędza czas, unikając wywołań serwera zdalnego. Tylko w niektórych przypadkach, jeśli filtr bloom mówi nam, że URL MOŻE być złośliwy, tylko w takich przypadkach wywołujemy serwer. To „MOC” ma w 99% rację. mały filtr rozkwitu w przeglądarce pokazuje to, a tym samym oszczędza czas, unikając wywołań do zdalnego serwera. Tylko w niektórych przypadkach, jeśli filtr bloom mówi nam, że URL MOŻE być złośliwy, tylko w takich przypadkach wywołujemy serwer. To „MOC” ma w 99% rację. mały filtr rozkwitu w przeglądarce pokazuje to, a tym samym oszczędza czas, unikając wywołań do zdalnego serwera. Tylko w niektórych przypadkach, jeśli filtr bloom mówi nam, że URL MOŻE być złośliwy, tylko w takich przypadkach wywołujemy serwer. To „MOC” ma 99% racji.
Tak więc, używając małego filtra bloom w przeglądarce, zaoszczędziliśmy dużo czasu, ponieważ nie musimy wykonywać wywołań serwera dla każdego wprowadzonego adresu URL.
Widzimy, że tabela skrótów z pojedynczą funkcją skrótu jest używana do zupełnie innego celu niż filtr bloom. Mam nadzieję, że to rozwiąże Twoje wątpliwości :)
edytuj :
Zaimplementowałem filtr bloom do zadania testowania złośliwych adresów URL w Pythonie. Kod można znaleźć tutaj - https://github.com/tarunsharma1/Bloom-Filter
Kod jest bardzo prosty do zrozumienia, a szczegółowy opis znajduje się w pliku readme.