Изчисляване на точния брой битове в филтър за разцвет - математически, цъфтящ филтър

Опитвам се да направя конфигурируем цъфтящ филтър.В конструктора сте задали прогнозния необходим капацитет на филтъра (n), желаната степен на грешка (p) и списък на хеш функции (с размер k).

Според Уикипедия, има следната връзка (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, което е напълно обратно.

Къде сгреших?

Отговори:

Управихте правилно уравнението, но имайте предвид, че Уикипедия гласи:

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)))