固定数の関数では、偽陽性の確率を与えられたBloom Filterのサイズをどのように計算できますか？

Question

ブルームフィルタを実装する必要があります。そして、私はこれの方法を見つけることができません。

機能が固定されているため、偽陽性の確率を考慮してBloom Filterのサイズを計算するにはどうすればよいですか？

たとえば、フィルタには誤検出率が10％、数値関数とセット内の要素数があります。

偽陽性確率に一致するBloom Filterのサイズはどのように計算できますか？

Answer 1

この式はWikipediaです。利用可能なハッシュ関数が十分にあると仮定すると、指定した偽陽性率が0.1の場合、要素あたり〜4.8ビットが必要です。

この場合、4つのハッシュ関数が最適であるように見えます。より多くのハッシュ関数が常に優れているわけではないことに注意してください。フィルタのサイズに比べて非常に多くのハッシュ関数がある場合、ほとんどすべてのビットを素早く設定し、多くの誤検出が発生します。