固定数のビット (例: スロット) (m) と固定数のハッシュ関数 (k) が与えられた場合、理論上の偽陽性率 (p) をどのように計算しますか?
ウィキペディアhttp://en.wikipedia.org/wiki/Bloom_filterによると、偽陽性率 (p) と項目数 (n) に対して、必要なビット数 (m) はm = - n * l(p) / (l(2)^2) 、ハッシュ関数 (k) は で与えられk = m / n * l(2)ます。
ウィキペディアのページに記載されている式から、理論上の偽陽性率 (p) を次のように評価できると思います。p = (1 - e(-(k * n/m)))^k
しかし、ウィキペディアには (p) の別の式があります。p = e(-m/n*(l(2)^2))これは、(k) がハッシュ関数の最適な数であると仮定しています。
私の例では、 と を取りn = 1000000ましm = n * 2た。(k) の最適値は 1.386 で、前の式によると、理論上の偽陽性率 (p) は 0.382 です。関数の数を選択し、固定 (k) が与えられた場合の理論上の偽陽性率 (p) を計算し、必要な理論上のビット数 (m') を計算します。
for k = 1, p = .393 and m' = 1941401
for k = 2, p = .399 and m' = 1909344
for k = 3, p = .469 and m' = 1576527
for k = 4, p = .559 and m' = 1210636
フィルターに詰め込むビットが多いほど、偽陽性が多くなります。論理的に思えます。
p = (1 - e(-(k * n/m)))^kしかし、(k)、(m)、および (n) が固定されている場合、理論上の偽陽性率を取得する式が正しいことを確認できますか?
注: 質問は既にここで尋ねられているようです:関数の数が固定されている場合、偽陽性の確率を考慮してブルーム フィルターのサイズを計算するにはどうすればよいですか? しかし、私の正確な質問に一致する答えはありません。 ブルーム フィルターにはいくつのハッシュ関数が必要ですか? 興味深いかもしれませんが、まったく同じではありません。
よろしく