Bei der Implementierung eines Bloom-Filters erfordert der herkömmliche Ansatz mehrere unabhängige Hash-Funktionen. Kirsch und Mitzenmacher haben gezeigt, dass man eigentlich nur zwei braucht und den Rest als Linearkombination daraus erzeugen kann.
Meine Frage ist: Was ist der Unterschied zwischen zwei Hash-Funktionen und einer mit der doppelten Entropie?
Dies hängt damit zusammen, was Sie tatsächlich mit der Ausgabe Ihrer Hash-Funktionen tun: Sie werden Ihren (etwa) 64-Bit-Hash-Wert auf die Größe Ihres Bitvektors skalieren, der wahrscheinlich bedeutend kleiner als 2 ist 64 . Dies ist eindeutig eine Transformation, bei der die Entropie verloren geht (außer in seltenen Fällen stimmen Ihre Hash-Größe und Filterkapazität genau überein). Angenommen, mein Filter enthält weniger als 2 32 Einträge. Was hindert mich daran, meinen 64-Bit-Hash-Wert in zwei 32-Bit-Hashes aufzuteilen und lineare Kombinationen daraus zu erstellen? Oder verwenden Sie es, um einen PRNG zu erzeugen?
Mit anderen Worten, wie viele Informationen muss ich tatsächlich über jedes Element wissen, das ich in einen Bloom-Filter einfüge, um sicherzustellen, dass die Standard-False-Positive-Rate gilt? Oder allgemeiner: In welchem Verhältnis steht es, wie gut ich Elemente unterscheiden kann (wie viele Bits benutze ich, um sie zu beschreiben) und wie gut mein Bloom-Filter funktioniert?
Es scheint sicher, dass ich bei einer Filtergröße von mit Bits davonkommen kann , oder äquivalent mit Bits, die gespeichert werden müssen Elemente mit falsch positiver Wahrscheinlichkeit ....