Фильтр Блума — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Вероятность ложноположительного срабатывания)
м (rollbackEdits.php mass rollback)
 
(не показано 50 промежуточных версий 9 участников)
Строка 1: Строка 1:
'''Фильтр Блума''' — это вероятностная структура данных, придуманная Бёртоном Блумом в 1970 году, позволяющая компактно хранить множество элементов и проверять принадлежность заданного элемента к множеству. При этом существует возможность получить ложноположительное срабатывание(элемента в множестве нет, но структура данных сообщает, что он есть), но не ложноотрицательное.
+
__TOC__
 +
{{Определение
 +
|neat = 1
 +
|definition='''Вероятностное множество''' (англ. ''probabilistic set'') {{---}} структура данных, способная добавлять элемент в множество, а также выполнять запросы проверки принадлежности элемента множеству. При этом существует возможность получить или положительный, но неопределенный ответ (элемента в множестве нет, но структура данных сообщает, что он есть), или отрицательный определенный ответ (элемент точно не содержится в данном множестве).
 +
}}
 +
Неформально вероятностное множество {{---}} это структура, позволяющая проверить принадлежность элемента множеству. Ответ может быть:
 +
 
 +
* элемент точно не принадлежит множеству,
 +
* элемент возможно принадлежит множеству.
 +
'''Фильтр Блума''' (англ. ''Bloom filter'') — это реализация вероятностного множества, придуманная Бёртоном Блумом в 1970 году, позволяющая компактно хранить элементы и проверять принадлежность заданного элемента к множеству. При этом существует возможность получить ложноположительное срабатывание (элемента в множестве нет, но структура данных сообщает, что он есть), но не ложноотрицательное.
  
 
Фильтр Блума может использовать любой объём памяти, заранее заданный пользователем, причем чем он больше, тем меньше вероятность ложного срабатывания. Поддерживается операция добавления новых элементов в множество, но не удаления существующих (если только не используется модификация со счётчиками). С увеличением размера хранимого множества повышается вероятность ложного срабатывания.
 
Фильтр Блума может использовать любой объём памяти, заранее заданный пользователем, причем чем он больше, тем меньше вероятность ложного срабатывания. Поддерживается операция добавления новых элементов в множество, но не удаления существующих (если только не используется модификация со счётчиками). С увеличением размера хранимого множества повышается вероятность ложного срабатывания.
Строка 5: Строка 14:
 
== Описание структуры данных ==
 
== Описание структуры данных ==
  
[[Файл:bloom_filter.png|thumb|360px|Пример фильтра Блума с <tex>m = 9</tex> и <tex>k = 3</tex>, хранящего множество из элементов <tex>A</tex> и <tex>B</tex>. Цветные стрелки указывают на места в битовом массиве, соответствующие каждому элементу множества. Этот фильтр Блума может определить, что элемент <tex>C</tex> входит в множество, хотя он и не добавлен в него.]]
+
[[Файл: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>p(h_i(x) \neq j) = 1 - \dfrac {1}{m} </tex>
  
Фильтр Блума представляет собой битовый массив из <tex>m</tex> бит. Изначально, когда структура данных хранит пустое множество, все <tex>m</tex> бит обнулены. Далее определяются <tex>k</tex> независимых хеш-функций <tex>h_1</tex>, , <tex>h_k</tex>, отображающих каждый элемент в одну из <tex>m</tex> позиций битового массива достаточно равномерным образом.
+
Так как для упрощения анализа мы предполагаем, что значения хеш-функций являются [[Независимые случайные величины#Независимость в совокупности|независимыми в совокупности]] [[Дискретная случайная величина|случайными величинами]], то вероятность, что <tex> j </tex>-ый бит останется нулевым после добавления очередного элемента, равна:
  
Для добавления элемента <tex>e</tex> необходимо записать единицы на каждую из позиций <tex>h_1(e)</tex>, …, <tex>h_k(e)</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>e</tex> принадлежит множеству хранимых элементов, необходимо проверить состояние битов  <tex>h_1(e)</tex>, …, <tex>h_k(e)</tex>. Если хотя бы один из них равен нулю, элемент не принадлежит множеству. Если все они равны единице, то структура данных сообщает, что <tex>е</tex> принадлежит множеству. При этом может возникнуть две ситуации: либо элемент действительно принадлежит к множеству, либо все эти биты оказались установлены по случайности при добавлении других элементов, что и является источником ложных срабатываний в этой структуре данных.
+
А вероятность того, что <tex> j </tex>-ый бит будет равен нулю после вставки <tex> n </tex> различных элементов в изначально пустой фильтр:
  
== Вероятность ложноположительного срабатывания ==
+
<tex>(1 - \dfrac {1}{m})^{kn} </tex>
  
Пусть размер битового массива <tex>m</tex> и задано <tex>k</tex> хеш-функций таких, что каждая из них назначает место элементу <tex>x</tex> в битовом массиве с равной вероятностью:
+
В силу второго замечательного предела и достаточно большого <tex> m </tex> можем это записать как:
  
<tex dpi = "150">Pr(h_i(x) = t) = \frac 1m </tex>, где <tex dpi = "150">t = 1 .. m</tex>
+
<tex >(1 - \dfrac {1}{m})^{kn} \approx e^{-kn/m}</tex>
  
Тогда вероятность того, что в некоторый p-й бит не будет записана единица во время операции вставки очередного элемента равна:
+
Ложноположительное срабатывание происходит тогда, когда для несуществующего элемента все <tex> k </tex> бит окажутся ненулевыми, и фильтр Блума ответит, что он входит в число вставленных элементов.
 +
Тогда вероятность такого события равна:
  
<tex dpi = "150">Pr(h_i(x) \ne p)^k = (1 - \frac 1m)^k </tex>
+
<tex>(1 - e^{-kn/m})^k</tex>
  
А вероятность того, что p-й бит останется равным нулю после вставки n различных элементов:
+
Для фиксированных <tex> m </tex> и <tex> n </tex>, оптимальное число хеш-функций <tex> k </tex>, минимизирующих вероятность ложноположительного срабатывания, равно:
  
<tex dpi = "150">(1 - \frac 1m)^{kn} </tex>
+
<tex>k = \ln 2 \dfrac {m}{n} \approx 0.6931 \dfrac {m}{n}</tex>
  
В силу второго замечательного предела и достаточно большого m можем это записать как:
+
== Свойства ==
  
<tex dpi = "150">e^{-kn/m}</tex>
+
Фильтр Блума может хранить универсальное множество всех возможных элементов. При этом все ячейки битового массива будут содержать <tex> 1 </tex>.
  
Ложноположительное срабатывание происходит тогда, когда для несуществующего элемента все <tex>k</tex> бит окажутся ненулевыми, и фильтр Блума ответит, что он входит в число вставленных элементов.
+
При существовании двух фильтров Блума одинаковых размеров и с одинаковыми наборами хеш-функций, их объединение и пересечение может быть реализовано с помощью [[Определение_булевой_функции#Бинарные функции|побитовых операций]] <tex> \vee </tex> и <tex>\wedge </tex> .
Вероятность такого события тогда равна:
 
  
<tex dpi = "150">(1 - e^{-kn/m})^k</tex>
+
== Примеры реализации фильтра Блума ==
 +
В ответ на запрос поиска есть вероятность получить положительный ответ, даже если этого элемента в данном множестве нет. Но если же ответ фильтра был отрицательным, запрашиваемого элемента точно нет. Чем больше размер этого множества, тем меньше вероятность получить некорректный ответ на запрос о наличии какого-либо элемента.
  
Для фиксированных m и n, оптимальное число k (число хеш-функций), минимизирующих её, равно:
+
*Google BigTable<ref>[https://cloud.google.com/bigtable Google BigTable]</ref> использует фильтры Блума, пример вероятностного множества, для уменьшения числа обращений к жесткому диску при проверке на существование заданной строки или столбца в таблице базы данных. Такой подход к нахождению необходимого элемента в базе данных значительно ускоряет сам процесс поиска и уменьшает количество обращений к жесткому диску,
 +
*компьютерные программы для проверки орфографии,
 +
*Bitcoin<ref>[https://en.wikipedia.org/wiki/Bitcoin Wikipedia {{---}} Bitcoin]</ref> использует фильтр Блума, чтобы ускорить синхронизацию с кошельком.
  
<tex dpi = "150">k = \frac mn ln(2) </tex>
+
== Примечания ==
 +
<references/>
  
А сама вероятность ложного срабатывания равна:
+
== Источники информации==
 +
* [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
  
<tex dpi = "150">2^{-k}</tex>
+
[[Категория: Дискретная математика и алгоритмы ]]
 +
[[Категория: Хеширование]]

Текущая версия на 19:27, 4 сентября 2022

Определение:
Вероятностное множество (англ. probabilistic set) — структура данных, способная добавлять элемент в множество, а также выполнять запросы проверки принадлежности элемента множеству. При этом существует возможность получить или положительный, но неопределенный ответ (элемента в множестве нет, но структура данных сообщает, что он есть), или отрицательный определенный ответ (элемент точно не содержится в данном множестве).

Неформально вероятностное множество — это структура, позволяющая проверить принадлежность элемента множеству. Ответ может быть:

  • элемент точно не принадлежит множеству,
  • элемент возможно принадлежит множеству.

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

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

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

Фильтр Блума с [math]m = 9[/math] и [math]k = 3[/math], хранящий множество из элементов [math]A[/math] и [math]B[/math]. Этот фильтр Блума может определить, что элемент [math]C[/math] входит в множество, хотя он и не добавлен в него.

Фильтр Блума представляет собой битовый массив из [math]m[/math] бит и [math]k[/math] различных хеш-функций [math]h_1 \dots h_k[/math], равновероятно отображающих элементы исходного множества во множество [math] \big\{ 0, 1, \dots m - 1 \big\}[/math], соответствующее номерам битов в массиве. Изначально, когда структура данных хранит пустое множество, все [math]m[/math] бит обнулены.

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

Чтобы проверить, что элемент [math]e[/math] принадлежит множеству хранимых элементов, необходимо проверить состояние битов [math] h_1(e) \dots h_k(e) [/math]. Если хотя бы один из них равен нулю, элемент не принадлежит множеству. Если все они равны единице, то структура данных сообщает, что элемент принадлежит множеству. При этом может возникнуть две ситуации: либо элемент действительно принадлежит к множеству, либо все эти биты оказались установлены при добавлении других элементов, что и является источником ложных срабатываний в этой структуре данных.

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

Минимизация вероятности ложноположительного срабатывания

Пусть размер битового массива [math] m [/math], и заданы [math] k [/math] хеш-функций, причем все хеш-функции выбираются случайным образом. Тогда вероятность, что в [math] j [/math]-ый бит не будет записана единица [math] i [/math]-ой хеш-функцией при вставке очередного элемента, равна:

[math]p(h_i(x) \neq j) = 1 - \dfrac {1}{m} [/math]

Так как для упрощения анализа мы предполагаем, что значения хеш-функций являются независимыми в совокупности случайными величинами, то вероятность, что [math] j [/math]-ый бит останется нулевым после добавления очередного элемента, равна:

[math]p(h_i(x) \neq j[/math] для [math] \forall i \in \big\{ 1 \dots k \big\}) = (1 - \dfrac {1}{m})^k [/math]

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

[math](1 - \dfrac {1}{m})^{kn} [/math]

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

[math](1 - \dfrac {1}{m})^{kn} \approx e^{-kn/m}[/math]

Ложноположительное срабатывание происходит тогда, когда для несуществующего элемента все [math] k [/math] бит окажутся ненулевыми, и фильтр Блума ответит, что он входит в число вставленных элементов. Тогда вероятность такого события равна:

[math](1 - e^{-kn/m})^k[/math]

Для фиксированных [math] m [/math] и [math] n [/math], оптимальное число хеш-функций [math] k [/math], минимизирующих вероятность ложноположительного срабатывания, равно:

[math]k = \ln 2 \dfrac {m}{n} \approx 0.6931 \dfrac {m}{n}[/math]

Свойства

Фильтр Блума может хранить универсальное множество всех возможных элементов. При этом все ячейки битового массива будут содержать [math] 1 [/math].

При существовании двух фильтров Блума одинаковых размеров и с одинаковыми наборами хеш-функций, их объединение и пересечение может быть реализовано с помощью побитовых операций [math] \vee [/math] и [math]\wedge [/math] .

Примеры реализации фильтра Блума

В ответ на запрос поиска есть вероятность получить положительный ответ, даже если этого элемента в данном множестве нет. Но если же ответ фильтра был отрицательным, запрашиваемого элемента точно нет. Чем больше размер этого множества, тем меньше вероятность получить некорректный ответ на запрос о наличии какого-либо элемента.

  • Google BigTable[1] использует фильтры Блума, пример вероятностного множества, для уменьшения числа обращений к жесткому диску при проверке на существование заданной строки или столбца в таблице базы данных. Такой подход к нахождению необходимого элемента в базе данных значительно ускоряет сам процесс поиска и уменьшает количество обращений к жесткому диску,
  • компьютерные программы для проверки орфографии,
  • Bitcoin[2] использует фильтр Блума, чтобы ускорить синхронизацию с кошельком.

Примечания

Источники информации