計算布隆過濾器中的正確比特數

Question

我正在嘗試製作可配置的布隆過濾器。在構造函數中，您可以設置過濾器的預測必要容量（n），期望的錯誤率（p）以及散列函數（大小爲k）的列表。

According to Wikipedia，下列關係成立（m是比特數）：

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

由於我得到p，n和k作爲參數，我需要解決m;我得到以下：

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

但是，有幾件事情讓我覺得我做錯了什麼。對於初學者，p ** (1/k)將傾向於1足夠大的k，這意味着整個分數是病態定義（因爲您可以想像除以0）。

您可能會注意到的另一件事是，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)))