19
правок
Изменения
по замечаниям
{{Определение|neat = 1 |definition=Фильтр Блума (англ. ''Bloom filter'Фильтр Блума') является примером '''вероятностного множества''' , структуры данных, способной добавлять элемент в множество и способной также выполнять запросы поиска в заданном множестве. При этом существует возможность получить или положительный ,но неопределенный ответ (элемента в множестве нет, но структура данных сообщает, что он есть), или отрицательный определенный ответ(англэлемент точно не содержится в данном множестве). }}''Bloom filter'Фильтр Блума''') — это структура данных, придуманная Бёртоном Блумом в 1970 году, позволяющая компактно хранить множество элементов и проверять принадлежность заданного элемента к множеству. При этом существует возможность получить ложноположительное срабатывание (элемента в множестве нет, но структура данных сообщает, что он есть), но не ложноотрицательное.
Фильтр Блума может использовать любой объём памяти, заранее заданный пользователем, причем чем он больше, тем меньше вероятность ложного срабатывания. Поддерживается операция добавления новых элементов в множество, но не удаления существующих (если только не используется модификация со счётчиками). С увеличением размера хранимого множества повышается вероятность ложного срабатывания.
Пусть размер битового массива <tex> m </tex>, и заданы <tex> k </tex> хеш-функций, причем все хеш-функции выбираются случайным образом. Тогда вероятность, что в <tex> j </tex>-ый бит не будет записана единица <tex> i </tex>-ой хеш-функцией при вставке очередного элемента, равна:
<tex dpi = "180150">p(h_i(x) \neq j) = 1 - \frac dfrac {1}{m} </tex>
Так как для упрощения анализа мы предполагаем, что значения хеш-функций являются [[Независимые случайные величины#Независимость в совокупности|независимыми в совокупности]] [[Дискретная случайная величина|случайными величинами]], то вероятность, что <tex> j </tex>-ый бит останется нулевым после добавления очередного элемента, равна:
<tex dpi = "180150">p(h_i(x) \neq j</tex> для <tex dpi = "180150"> \forall i \in \big\{ 1 \dots k \big\}) = (1 - \frac dfrac {1}{m})^k </tex>
А вероятность того, что <tex> j </tex>-ый бит будет равен нулю после вставки <tex> n </tex> различных элементов в изначально пустой фильтр:
<tex dpi = "180150">(1 - \frac dfrac {1}{m})^{kn} </tex>
В силу второго замечательного предела и достаточно большого <tex> m </tex> можем это записать как:
<tex dpi = "180150">(1 - \frac dfrac {1}{m})^{kn} \approx e^{-kn/m}</tex>
Ложноположительное срабатывание происходит тогда, когда для несуществующего элемента все <tex> k </tex> бит окажутся ненулевыми, и фильтр Блума ответит, что он входит в число вставленных элементов.
Тогда вероятность такого события равна:
<tex dpi = "180150">(1 - e^{-kn/m})^k</tex>
Для фиксированных <tex> m </tex> и <tex> n </tex>, оптимальное число хеш-функций <tex> k </tex>, минимизирующих вероятность ложноположительного срабатывания, равно:
<tex dpi = "180150">k = \ln 2 \frac dfrac {m}{n} \approx 0.6931 \frac dfrac {m}{n}</tex>
== Вероятностное множество ==
В ответ на некоторый запрос есть вероятность получить положительный ответ, даже если этого элемента в данном множестве нет. Но если же запрашиваемый элемент в множестве есть, ответ в любом случае будет положительным. Чем больше размер этого множества, тем меньше вероятность получить некорректный ответ на запрос о наличии какого-либо элемента.
Google BigTable<ref>[https://cloud.google.com/bigtable Google BigTable]</ref> использует фильтры Блума, пример '''вероятностного множества''', для уменьшения числа обращений к жесткому диску при проверке на существование заданной строки или столбца в таблице базы данных. Такой подход к нахождению необходимого элемента в базе данных значительно ускоряет сам процесс поиска и уменьшает количество обращений к жесткому диску.
Проще говоря, вероятностное множество {{- --}} это структура, позволяющая проверить принадлежность элемента множеству. Ответ может быть:
* Элемент точно не принадлежит множеству,
== Примечания ==
<references/>
== Источники информации==
