403
правки
Изменения
Нет описания правки
[[Файл:bloom_filter.png|thumb|360px|Пример фильтра Блума с <tex>m = 9</tex> и <tex>k = 3</tex>, хранящего множество из элементов <tex>A</tex> и <tex>B</tex>. Цветные стрелки указывают на места в битовом массиве, соответствующие каждому элементу множества. Этот фильтр Блума может определить, что элемент <tex>C</tex> входит в множество, хотя он и не добавлен в него.]]
Фильтр Блума представляет собой битовый массив из <tex>m</tex> бит и <tex>k</tex> различных [[Хеширование|хеш-функций ]] <tex>h_1 \dots h_k</tex>, равновероятно отображающих элементы исходного множества во множество <tex> \big\{ 0, 1, \dots m - 1 \big\}</tex>, соответствующее номерам битов в массиве.
Изначально, когда структура данных хранит пустое множество, все <tex>m</tex> бит обнулены.
== Минимизация вероятности ложноположительного срабатывания ==
Пусть размер битового массива <tex> m </tex>, и заданы <tex> k </tex> [[Хеширование|хеш-функций]], причем все [[Хеширование|хеш-функции ]] являются [[Независимые случайные величины|независимыми случайными величинами]]. Тогда вероятность, что в <tex> j </tex>-ый бит не будет записана единица <tex> i </tex>-ой [[Хеширование|хеш-функцией ]] при вставке очередного элемента, равна:
<tex dpi = "150">p(h_i(x) \neq j) = 1 - \frac {1}{m} </tex>
<tex dpi = "150">(1 - e^{-kn/m})^k</tex>
Для фиксированных <tex> m </tex> и <tex> n </tex>, оптимальное число [[Хеширование|хеш-функций ]] <tex> k </tex>, минимизирующих вероятность ложноположительного срабатывания, равно:
<tex dpi = "150">k = \ln 2 \frac {m}{n} \approx 0.6931 \frac {m}{n}</tex>
Фильтр Блума может хранить универсальное множество всех возможных элементов. При этом все ячейки битового массива будут содержать 1.
При существование двух фильтров Блума одинаковых размеров и с одинаковыми наборами [[Хеширование|хеш-функций]], их объединение и пересечение может быть реализовано с помощью побитовых операций OR и AND.
== Источники ==
