Учитывая фиксированное количество бит (например, слот) (m) и фиксированное число хеш-функции (k), как вычислить теоретическую ложноположительную скорость (p)?Bloom Filter: оценка ложноположительной скорости
Согласно Википедии http://en.wikipedia.org/wiki/Bloom_filter, для ложных срабатываний (р) и ряд пункта (п), число битов (м), необходимой дается m = - n * l(p)/(l(2)^2) и оптимальное количество хэш-функции (к) дается по k = m/n * l(2).
Из формулы, приведенной в Википедии странице, я думаю, я мог оценить теоретические ложные срабатывания (р) следующий: p = (1 - e(-(k * n/m)))^k
Но Википедия имеет другую формулу (р): p = e(-m/n*(l(2)^2)), который, я полагаю, предположим, что (k) является оптимальным числом хэш-функции.
Для моего примера я принял n = 1000000 и m = n * 2, оптимальное значение для (k) было бы равно 1.386, а теоретическая ложноположительная скорость (p) была бы равна 0,382 согласно предыдущей формуле. Давайте выберем число функции, вычислить теоретические ложные срабатывания (р) при фиксированном (к) и вычислить теоретическое число бит, необходимых (т '):
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)?
Примечание: вопрос, кажется, уже задан здесь: With fixed number of functions, how can I calculate the size of a Bloom Filter given the probability of false positives?, но нет ответа, соответствующего моему точному вопросу. How many hash functions does my bloom filter need? может представлять интерес, но опять же это не совсем то же самое.
Привет
Не могли бы вы изложить четкий вопрос? AFAICT вы ответили на свои вопросы, прочитав страницу Википедии, поэтому не особо ясно, что вы ищете в Stackoverflow. – Kaganar
@ Kaganar Я немного переписал вопрос и поставил акцент на важный реальный вопрос. Спасибо за комментарий. – ydroneaud
Статья Википедии довольно ясна (и исправлена) вплоть до последнего шага, где она вводит экспоненциальную функцию. В этот момент он использует приближение, с которым я не знаком. Являются ли шаги перед экспоненциальной функцией отбрасыванием вас? – Kaganar