Изменения

__TOC__{{Определение|neat = 1 |definition='''Вероятностное множество''' (англ. ''probabilistic set'') {{---}} структура данных, способная добавлять элемент в множество, а также выполнять запросы проверки принадлежности элемента множеству. При этом существует возможность получить или положительный, но неопределенный ответ (элемента в множестве нет, но структура данных сообщает, что он есть), или отрицательный определенный ответ (элемент точно не содержится в данном множестве).}}Неформально вероятностное множество {{---}} это структура, позволяющая проверить принадлежность элемента множеству. Ответ может быть: * элемент точно не принадлежит множеству,* элемент возможно принадлежит множеству.'''Фильтр Блума'''(англ. ''Bloom filter'') — это вероятностная структура данныхреализация вероятностного множества, придуманная Бёртоном Блумом в 1970 году, позволяющая компактно хранить множество элементов элементы и проверять принадлежность заданного элемента к множеству. При этом существует возможность получить ложноположительное срабатывание(элемента в множестве нет, но структура данных сообщает, что он есть), но не ложноотрицательное.

[[Файл: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>m</tex> бит обнулены. Далее определяются и <tex>k</tex> независимых различных [[Хеширование|хеш-функций ]] <tex>h_1\dots h_k</tex>, …, равновероятно отображающих элементы исходного множества во множество <tex>h_k\big\{ 0, 1, \dots m - 1 \big\}</tex>, отображающих каждый элемент соответствующее номерам битов в одну из массиве. Изначально, когда структура данных хранит пустое множество, все <tex>m</tex> позиций битового массива достаточно равномерным образомбит обнулены.

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

Чтобы проверить , что элемент <tex>e</tex> принадлежит множеству хранимых элементов, необходимо проверить состояние битов <tex>h_1(e)</tex>, …, <tex>\dots h_k(e)</tex>. Если хотя бы один из них равен нулю, элемент не принадлежит множеству. Если все они равны единице, то структура данных сообщает, что <tex>е</tex> элемент принадлежит множеству. При этом может возникнуть две ситуации: либо элемент действительно принадлежит к множеству, либо все эти биты оказались установлены по случайности при добавлении других элементов, что и является источником ложных срабатываний в этой структуре данных. По сравнению с [[Хеш-таблица|хеш-таблицами]], фильтр Блума может обходиться на несколько порядков меньшими объёмами памяти, жертвуя детерминизмом. Обычно он используется для уменьшения числа запросов к несуществующим данным в структуре данных с более дорогостоящим доступом (например, расположенной на жестком диске или в сетевой базе данных), то есть для «фильтрации» запросов к ней.

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

<tex dpi = "150">Pr(h_i(x) = t) = \frac 1m <1 - e^{-kn/tex>, где <tex dpi = "150">t = 1 .. m})^k</tex>

Тогда Для фиксированных <tex> m </tex> и <tex> n </tex>, оптимальное число хеш-функций <tex> k </tex>, минимизирующих вероятность тоголожноположительного срабатывания, что в некоторый p-й бит не будет записана единица во время операции вставки очередного элемента равнаравно:

<tex dpi = "150">Pr(h_i(x) \ne p)^k = (1 - \frac 1m)^k ln 2 \dfrac {m}{n} \approx 0.6931 \dfrac {m}{n}</tex>

Фильтр Блума может хранить универсальное множество всех возможных элементов. При этом все ячейки битового массива будут содержать <tex dpi = "150">(1 - \frac 1m)^{kn} </tex>.

В силу второго замечательного предела При существовании двух фильтров Блума одинаковых размеров и достаточно большого m можем это записать как:с одинаковыми наборами хеш-функций, их объединение и пересечение может быть реализовано с помощью [[Определение_булевой_функции#Бинарные функции|побитовых операций]] <tex> \vee </tex> и <tex>\wedge </tex> .

<tex dpi = "150">e^{= Примеры реализации фильтра Блума ==В ответ на запрос поиска есть вероятность получить положительный ответ, даже если этого элемента в данном множестве нет. Но если же ответ фильтра был отрицательным, запрашиваемого элемента точно нет. Чем больше размер этого множества, тем меньше вероятность получить некорректный ответ на запрос о наличии какого-kn/m}</tex>либо элемента.

Ложноположительное срабатывание происходит тогда*Google BigTable<ref>[https://cloud.google.com/bigtable Google BigTable]</ref> использует фильтры Блума, пример вероятностного множества, когда для несуществующего уменьшения числа обращений к жесткому диску при проверке на существование заданной строки или столбца в таблице базы данных. Такой подход к нахождению необходимого элемента все в базе данных значительно ускоряет сам процесс поиска и уменьшает количество обращений к жесткому диску,*компьютерные программы для проверки орфографии,*Bitcoin<texref>k[https://en.wikipedia.org/wiki/Bitcoin Wikipedia {{---}} Bitcoin]</texref> бит окажутся ненулевыми, и использует фильтр Блума ответит, что он входит в число вставленных элементовчтобы ускорить синхронизацию с кошельком.Вероятность такого события тогда равна:

<tex dpi = "150">(1 - e^{-kn/m})^k= Примечания ==<references/tex>

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