'''Фильтр Блума''' (англ. ''Bloom filter'') — это структура данных, придуманная Бёртоном Блумом в 1970 году, позволяющая компактно хранить множество элементов и проверять принадлежность заданного элемента к множеству. При этом существует возможность получить ложноположительное срабатывание (элемента в множестве нет, но структура данных сообщает, что он есть), но не ложноотрицательное.

Фильтр Блума может использовать любой объём памяти, заранее заданный пользователем, причем чем он больше, тем меньше вероятность ложного срабатывания. Поддерживается операция добавления новых элементов в множество, но не удаления существующих (если только не используется модификация со счётчиками). С увеличением размера хранимого множества повышается вероятность ложного срабатывания.

== Описание структуры данных ==

[[Файл: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>m</tex> бит обнулены.

Для добавления элемента <tex> e </tex> необходимо записать единицы на каждую из позиций <tex>h_1(e) \dots h_k(e)</tex> битового массива.

Чтобы проверить, что элемент <tex>e</tex> принадлежит множеству хранимых элементов, необходимо проверить состояние битов <tex> h_1(e) \dots h_k(e) </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> j </tex>-ый бит останется нулевым после добавления очередного элемента, равна:

<tex dpi = "150">p(h_i(x) \neq j</tex> для <tex dpi = "150"> \forall i \in \big\{ 1 \dots k \big\}) = (1 - \frac {1}{m})^k </tex>

А вероятность того, что <tex> j </tex>-ый бит будет равен нулю после вставки <tex> n </tex> различных элементов в изначально пустой фильтр:

<tex dpi = "150">(1 - \frac {1}{m})^{kn} </tex>

В силу второго замечательного предела и достаточно большого <tex> m </tex> можем это записать как:

<tex dpi = "150">(1 - \frac {1}{m})^{kn} \approx e^{-kn/m}</tex>

Ложноположительное срабатывание происходит тогда, когда для несуществующего элемента все <tex> k </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.

== Источники информации==
* [http://ru.wikipedia.org/wiki/Фильтр_Блума Википедия {{---}} Фильтр Блума]
* [http://en.wikipedia.org/wiki/Bloom_filter Wikipedia {{---}} Bloom filter]
*Demetrescu, Camil. «Experimental Algorithms» {{---}} «Springer», 2007 г. {{---}} 108-121 стр. {{---}} ISBN 978-3-540-72844-3

[[Категория: Дискретная математика и алгоритмы ]]
[[Категория: Хеширование]]

Фильтр Блума

2016-01-08T12:39:45Z

Kuro: /* Источники */

'''Фильтр Блума''' — это структура данных, придуманная Бёртоном Блумом в 1970 году, позволяющая компактно хранить множество элементов и проверять принадлежность заданного элемента к множеству. При этом существует возможность получить ложноположительное срабатывание (элемента в множестве нет, но структура данных сообщает, что он есть), но не ложноотрицательное.

Фильтр Блума может использовать любой объём памяти, заранее заданный пользователем, причем чем он больше, тем меньше вероятность ложного срабатывания. Поддерживается операция добавления новых элементов в множество, но не удаления существующих (если только не используется модификация со счётчиками). С увеличением размера хранимого множества повышается вероятность ложного срабатывания.

== Описание структуры данных ==

[[Файл: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>m</tex> бит обнулены.

Для добавления элемента <tex> e </tex> необходимо записать единицы на каждую из позиций <tex>h_1(e) \dots h_k(e)</tex> битового массива.

Чтобы проверить, что элемент <tex>e</tex> принадлежит множеству хранимых элементов, необходимо проверить состояние битов <tex> h_1(e) \dots h_k(e) </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> j </tex>-ый бит останется нулевым после добавления очередного элемента, равна:

<tex dpi = "150">p(h_i(x) \neq j</tex> для <tex dpi = "150"> \forall i \in \big\{ 1 \dots k \big\}) = (1 - \frac {1}{m})^k </tex>

А вероятность того, что <tex> j </tex>-ый бит будет равен нулю после вставки <tex> n </tex> различных элементов в изначально пустой фильтр:

<tex dpi = "150">(1 - \frac {1}{m})^{kn} </tex>

В силу второго замечательного предела и достаточно большого <tex> m </tex> можем это записать как:

<tex dpi = "150">(1 - \frac {1}{m})^{kn} \approx e^{-kn/m}</tex>

Ложноположительное срабатывание происходит тогда, когда для несуществующего элемента все <tex> k </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.

== Источники информации==
* [http://ru.wikipedia.org/wiki/Фильтр_Блума Википедия {{---}} Фильтр Блума]
* [http://en.wikipedia.org/wiki/Bloom_filter Wikipedia {{---}} Bloom filter]
*Demetrescu, Camil. «Experimental Algorithms» {{---}} «Springer», 2007 г. {{---}} 108-121 стр. {{---}} ISBN 978-3-540-72844-3

[[Категория: Дискретная математика и алгоритмы ]]
[[Категория: Хеширование]]