19
правок
Изменения
м
== Вероятностное множество ==
В ответ на некоторый запрос есть вероятность получить положительный ответ, даже если этого элемента в данном множестве нет. Но если же запрашиваемый элемент в множестве есть, ответ в любом случае будет положительным. Чем больше размер этого множества, тем меньше вероятность получить некорректный ответ на запрос о наличии какого-либо элемента.
Google BigTable<ref>[https://cloud.google.com/bigtable Google BigTable]</ref> использует фильтры Блума, пример '''вероятностного множества''', для уменьшения числа обращений к жесткому диску при проверке на существование заданной строки или столбца в таблице базы данных. Такой подход к нахождению необходимого элемента в базе данных значительно ускоряет сам процесс поиска и уменьшает количество обращений к жесткому диску.
Проще говоря, вероятностное множество {{---}} это структура, позволяющая проверить принадлежность элемента множеству. Ответ может быть:
* Элемент точно не принадлежит множеству,
* Элемент возможно принадлежит множеству.
Нет описания правки
{{Определение
|neat = 1
|definition=Фильтр Блума (англ. ''Bloom filter'') является примером ''Вероятностное множество'вероятностного множества''', структуры {{---}} структура данных, способной способная добавлять элемент в множество и способной способная также выполнять запросы поиска в заданном множестве. При этом существует возможность получить или положительный ,но неопределенный ответ (элемента в множестве нет, но структура данных сообщает, что он есть), или отрицательный определенный ответ (элемент точно не содержится в данном множестве).
}}
Неформально вероятностное множество {{---}} это структура, позволяющая проверить принадлежность элемента множеству. Ответ может быть: * Элемент точно не принадлежит множеству,* Элемент возможно принадлежит множеству.'''Фильтр Блума'''(англ. ''Bloom filter'') — это структура данных, придуманная Бёртоном Блумом в 1970 году, позволяющая компактно хранить множество элементов и проверять принадлежность заданного элемента к множеству. При этом существует возможность получить ложноположительное срабатывание (элемента в множестве нет, но структура данных сообщает, что он есть), но не ложноотрицательное.
Фильтр Блума может использовать любой объём памяти, заранее заданный пользователем, причем чем он больше, тем меньше вероятность ложного срабатывания. Поддерживается операция добавления новых элементов в множество, но не удаления существующих (если только не используется модификация со счётчиками). С увеличением размера хранимого множества повышается вероятность ложного срабатывания.
<tex dpi = "150">k = \ln 2 \dfrac {m}{n} \approx 0.6931 \dfrac {m}{n}</tex>
== Свойства ==
При существование двух фильтров Блума одинаковых размеров и с одинаковыми наборами хеш-функций, их объединение и пересечение может быть реализовано с помощью [[Определение_булевой_функции#Бинарные функции|побитовых операций]] <tex> \vee </tex> и <tex>\wedge </tex> .
== Примеры реализации фильтра Блюма ==
В ответ на запрос поиска есть вероятность получить положительный ответ, даже если этого элемента в данном множестве нет. Но если же запрашиваемый элемент в множестве есть, ответ в любом случае будет положительным. Чем больше размер этого множества, тем меньше вероятность получить некорректный ответ на запрос о наличии какого-либо элемента.
*Google BigTable<ref>[https://cloud.google.com/bigtable Google BigTable]</ref> использует фильтры Блума, пример '''вероятностного множества''', для уменьшения числа обращений к жесткому диску при проверке на существование заданной строки или столбца в таблице базы данных. Такой подход к нахождению необходимого элемента в базе данных значительно ускоряет сам процесс поиска и уменьшает количество обращений к жесткому диску,
*Компьютерные программы для проверки орфографии,
*Bitcoin<ref>[https://en.wikipedia.org/wiki/Bitcoin Wikipedia {{---}} Bitcoin]</ref> использует фильтр Блюма, чтобы ускорить синхронизацию с кошельком.
== Примечания ==
