ブルームフィルタで適切なビット数を計算する

Question

ブルームフィルタを構成しようとしています。コンストラクタでは、予測されるフィルタの必要容量（n）、望ましいエラー率（p）、およびハッシュ関数のリスト（サイズk）を設定します。

According to Wikipedia、以下の関係が（mはビット数である）を保持：

p = (1 - k * n/m) ** k 

Iをパラメータとしてp、nとkを取得するので、私はmために解決する必要があります。私は次のようになります：

m = k * n/(1 - p ** (1/k)) 

しかし、私は何か間違ったと思ういくつかのことがあります。まず、p ** (1/k)はkの十分な大きさのために1に向かいます（これは、おそらく0によって分けることができるので、全体の分数が定義されていないことを意味します）。

もう1つお気づきのことは、p（許容最大エラーレート）が大きくなるため、それは完全に後方にあるmです。

どこが間違っていましたか？

Answer 1

ただし、ウィキペディアが述べていることに注意し、正しく方程式を解くました：

The probability of all of them being 1, which would cause 
the algorithm to erroneously claim that the element is in 
the set, is often given as: 

p ~= (1 - (1 - 1/m) ** (k * n)) ** k ~= (1 - Exp(-k * n/m)) ** k 

これはあなたが述べられてきたものとは非常に異なっている：

p = (1 - k * n/m) ** k 

だから、あなたが本当にで開始したいもの私は

になるこの働い

p = (1 - (1 - 1/m) ** (k * n)) ** k 

です

(1 - 1/m) ** (k * n) = 1 - p ** (1/k) 
1 - 1/m = (1 - p ** (1/k)) ** (1/(k * n)) 
m - 1 = m * (1 - p ** (1/k)) ** (1/(k * n)) 
m - m * (1 - p ** (1/k)) ** (1/(k * n)) = 1 
m * (1 - (1 - p ** (1/k)) ** (1/(k * n))) = 1 
m = 1/(1 - (1 - p ** (1/k)) ** (1/(k * n)))