Изменения

Перейти к: навигация, поиск

Фильтр Блума

195 байт убрано, 17:39, 9 июня 2012
Описание структуры данных
== Описание структуры данных ==
[[Файл:bloom_filter.png|400px|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>, соответствующее номерам битов в массиве.
403
правки

Навигация