Podczas wdrażania filtra Bloom tradycyjne podejście wymaga wielu niezależnych funkcji skrótu. Kirsch i Mitzenmacher pokazali, że tak naprawdę potrzebujesz tylko dwóch, a resztę możesz wygenerować jako kombinacje liniowe.
Moje pytanie brzmi: jaka tak naprawdę jest różnica między dwiema funkcjami skrótu i jedną z podwójną entropią?
Wynika to z patrzenia na to, co faktycznie robisz z wynikami funkcji skrótu: weźmiesz (powiedzmy) 64-bitową wartość skrótu i przeskalujesz ją do rozmiaru wektora bitowego, który prawdopodobnie jest znacznie mniejszy niż 2 64 . Jest to wyraźnie transformacja tracąca entropię (z wyjątkiem rzadkiego przypadku, gdy rozmiar skrótu i pojemność filtra dokładnie się pokrywają). Zakładając, że mój filtr ma mniej niż 2 32 wpisy, co powstrzyma mnie przed podzieleniem mojej 64-bitowej wartości skrótu na dwa 32-bitowe skróty i przyjmowanie ich liniowych kombinacji? Lub używając go do wysiewu PRNG?
Innymi słowy, ile informacji faktycznie muszę wiedzieć o każdym elemencie, który wstawiam do filtra Blooma, aby mieć pewność, że utrzymuje się standardowy współczynnik fałszywie dodatnich? Lub bardziej ogólnie, jaki jest związek między tym, jak dobrze potrafię odróżnić elementy (ile bitów używam do ich opisania), a tym, jak działa mój filtr Bloom?
Wygląda na to, że mogę uniknąć bitów dla filtra o rozmiarze lub równoważnie bitów do przechowywania elementów z fałszywie dodatnim prawdopodobieństwem ....