Фильтр Блума: оценка ложноположительных результатов
Учитывая фиксированное количество битов (например, слот) (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 в соответствии с предыдущей формулой. Давайте выберем номер функции, вычислим теоретическую частоту ложных срабатываний (p) с учетом фиксированного значения (k) и вычислим теоретическое количество необходимых битов (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)?
Примечание: вопрос, кажется, уже задан здесь:С фиксированным числом функций, как я могу вычислить размер фильтра Блума, учитывая вероятность ложных срабатываний? но нет ответа, соответствующего моему точному вопросу.Сколько хеш-функций нужно моему фильтру Блума? может представлять интерес, но опять же, это не совсем то же самое.
С уважением