Изменения
→Свойства
__TOC__
{{Определение
|neat = 1
Неформально вероятностное множество {{---}} это структура, позволяющая проверить принадлежность элемента множеству. Ответ может быть:
* Элемент элемент точно не принадлежит множеству,* Элемент элемент возможно принадлежит множеству.
'''Фильтр Блума''' (англ. ''Bloom filter'') — это реализация вероятностного множества, придуманная Бёртоном Блумом в 1970 году, позволяющая компактно хранить элементы и проверять принадлежность заданного элемента к множеству. При этом существует возможность получить ложноположительное срабатывание (элемента в множестве нет, но структура данных сообщает, что он есть), но не ложноотрицательное.
Фильтр Блума может хранить универсальное множество всех возможных элементов. При этом все ячейки битового массива будут содержать <tex> 1 </tex>.
При существование существовании двух фильтров Блума одинаковых размеров и с одинаковыми наборами хеш-функций, их объединение и пересечение может быть реализовано с помощью [[Определение_булевой_функции#Бинарные функции|побитовых операций]] <tex> \vee </tex> и <tex>\wedge </tex> .
== Примеры реализации фильтра Блума ==
В ответ на запрос поиска есть вероятность получить положительный ответ, даже если этого элемента в данном множестве нет. Но если же запрашиваемый элемент в множестве естьответ фильтра был отрицательным, ответ в любом случае будет положительнымзапрашиваемого элемента точно нет. Чем больше размер этого множества, тем меньше вероятность получить некорректный ответ на запрос о наличии какого-либо элемента.
*Google BigTable<ref>[https://cloud.google.com/bigtable Google BigTable]</ref> использует фильтры Блума, пример вероятностного множества, для уменьшения числа обращений к жесткому диску при проверке на существование заданной строки или столбца в таблице базы данных. Такой подход к нахождению необходимого элемента в базе данных значительно ускоряет сам процесс поиска и уменьшает количество обращений к жесткому диску,
