Фильтр Блума

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

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

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

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

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

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

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

Вероятность ложноположительного срабатывания

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

[math]Pr(h_i(x) = t) = \frac 1m [/math], где [math]t = 1 .. m[/math]

Тогда вероятность того, что в некоторый p-й бит не будет записана единица во время операции вставки очередного элемента равна:

[math]Pr(h_i(x) \ne p)^k = (1 - \frac 1m)^k [/math]

А вероятность того, что p-й бит останется равным нулю после вставки n различных элементов:

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

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

[math]e^{-kn/m}[/math]

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

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

Для фиксированных m и n, оптимальное число k (число хеш-функций), минимизирующих её, равно:

[math]k = \frac mn ln(2) [/math]

А сама вероятность ложного срабатывания равна:

[math]2^{-k}[/math]