19
правок
Изменения
→Минимизация вероятности ложноположительного срабатывания
Пусть размер битового массива <tex> m </tex>, и заданы <tex> k </tex> хеш-функций, причем все хеш-функции выбираются случайным образом. Тогда вероятность, что в <tex> j </tex>-ый бит не будет записана единица <tex> i </tex>-ой хеш-функцией при вставке очередного элемента, равна:
<tex dpi = "150180">p(h_i(x) \neq j) = 1 - \frac {1}{m} </tex>
Так как для упрощения анализа мы предполагаем, что значения хеш-функций являются [[Независимые случайные величины#Независимость в совокупности|независимыми в совокупности]] [[Дискретная случайная величина|случайными величинами]], то вероятность, что <tex> j </tex>-ый бит останется нулевым после добавления очередного элемента, равна:
<tex dpi = "150180">p(h_i(x) \neq j</tex> для <tex dpi = "150180"> \forall i \in \big\{ 1 \dots k \big\}) = (1 - \frac {1}{m})^k </tex>
А вероятность того, что <tex> j </tex>-ый бит будет равен нулю после вставки <tex> n </tex> различных элементов в изначально пустой фильтр:
<tex dpi = "150180">(1 - \frac {1}{m})^{kn} </tex>
В силу второго замечательного предела и достаточно большого <tex> m </tex> можем это записать как:
<tex dpi = "150180">(1 - \frac {1}{m})^{kn} \approx e^{-kn/m}</tex>
Ложноположительное срабатывание происходит тогда, когда для несуществующего элемента все <tex> k </tex> бит окажутся ненулевыми, и фильтр Блума ответит, что он входит в число вставленных элементов.
Тогда вероятность такого события равна:
<tex dpi = "150180">(1 - e^{-kn/m})^k</tex>
Для фиксированных <tex> m </tex> и <tex> n </tex>, оптимальное число хеш-функций <tex> k </tex>, минимизирующих вероятность ложноположительного срабатывания, равно:
<tex dpi = "150180">k = \ln 2 \frac {m}{n} \approx 0.6931 \frac {m}{n}</tex>
== Свойства ==
