403
правки
Изменения
м
→Описание структуры данных
== Описание структуры данных ==
[[Файл:bloom_filter.png|400px|thumb|Фильтра Фильтр Блума с <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>e</tex> принадлежит множеству хранимых элементов, необходимо проверить состояние битов <tex> h_1(e) \dots h_k(e) </tex>. Если хотя бы один из них равен нулю, элемент не принадлежит множеству. Если все они равны единице, то структура данных сообщает, что элемент принадлежит множеству. При этом может возникнуть две ситуации: либо элемент действительно принадлежит к множеству, либо все эти биты оказались установлены при добавлении других элементов, что и является источником ложных срабатываний в этой структуре данных.
== Минимизация вероятности ложноположительного срабатывания ==
