Фильтр Блума

Вспомним про абстрактную структуру данных множество. Для её адекватной реализации в любом случае требуется достаточно много памяти. Мы можем попытаться ослабить это требования за счёт возможности ошибаться.

Мы хотим создать такую структуру данных, в которую можно будет добавлять объекты и пытаться определять наличие в ней объектов. На запрос «есть ли в множестве объект $x$ ?» можно получить или определенный отрицательный ответ «объекта $x$ точно нет» или неопределенный положительный ответ «объект $x$ , возможно, в множестве есть».

Пусть все наши объекты — элементы какого-то универсума $\UUU$ .

Про удаление объектов из нашей структуры пока не думаем и не говорим.

Реализацией нашей идеи служит структура фильтр Блума (Bloom filter). Эта структура данных использует хеширование.

Заведем битовый массив $b \in \{0, 1\}^m$ , состоящий из $m$ элементов. Этот битовый массив будет хранить информацию о наличии и отсутствии объектов в нашем множестве.

Создадим еще $k$ независимых хеш-функций $h_1, h_2, \dotsc, h_k \colon \UUU \surjto \{1, 2, \dotsb, m\}$ .

const array h[k]
array[bool] b[m]

Добавление элемента

При добавлении элемента $x$ в множество нужно записать $1$ в массив $b$ на каждую из позиций $h_1(x), h_2(x), \dotsc, h_k(x)$ .

function add(x):
    for int i = 0; i < k:
        int index = h[i](x)
        b[index] = true

Временная сложность выполнения операции — $O(k)$ .

Проверка наличия

Чтобы проверить, что элемент $x$ принадлежит множеству, нужно проверить, что все биты в массиве $b$ на позициях $h_1(x), h_2(x), \dotsc, h_k(x)$ установлены в $1$ . Если хотя бы один бит равен $0$ , то элемента $x$ в множестве быть не может.

function check(x) -> bool:
    bool contains = true
    for int i = 0; i < k:
        int index = h[i](x)
        contains &= b[index]

    return contains

Временная сложность выполнения операции — $O(k)$ .

Как уже упоминалось выше, операция check(x) может вернуть или определенный отрицательный ответ, или неопределенный положительный. Из-за этого свойства фильтр Блума нельзя использовать напрямую, если важна точность. Но он очень сильно пригождается тогда, когда надо выполнять много дорогостоящих запросов к другой структуре.

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

Вероятность ошибки и её минимизация

Давайте посчитаем вероятность ложного положительного срабатывания операции check(x). Как и прежде, размер битового массива $m$ , количество хеш-функций $k$ . Пусть в нашем множестве уже содержится $n$ элементов.

Посчитаем вероятность того, что конкретный бит $j$ не будет установлен в $1$ хеш-функцией $h_i$ при вставке очередного элемента $x$ .

\prob \big( h_i(x) \neq j \big) = 1 - \frac{1}{m}

Тогда для $k$ хеш-функций вероятность того, что конкретный бит $j$ не будет установлен в $1$ равна

\prob \big( h_i(x) \neq j \? \forall\, i \big) = \left( 1 - \frac{1}{m} \right)^k

Теперь можем посчитать вероятность того, что $j$ -ый бит будет равен $0$ после вставки $n$ элементов в изначально пустой фильтр Блума

\prob \big( b[j] = 0 \big) = \left( 1 - \frac{1}{m} \right)^{kn}

Ложное положительное срабатывание check(x) происходит тогда, когда для несуществующего элемента $x$ все $k$ бит окажутся ненулевыми. Вероятность такого события равна

\prob (\text{ложное срабатывание}) = \Bigg( 1 - \left( 1 - \frac{1}{m} \right)^{kn} \Bigg)^k

Можно вычислить оптимальное значение $k$ , которое минимизирует ошибку. В таком виде задача минимизации не решается, придется прибегнуть к асимптотическим оценкам. Используя второй замечательный предел, можно упростить

\left( 1 - \frac{1}{m} \right)^{kn} \approx e^{-kn/m}

Тогда

\prob (\text{ошибка}) \approx \left( 1 - e^{-kn/m} \right)^k

И вот уже в такой форме можно найти такое $k$ , при котором вероятность ошибки минимальная. Достаточно прологарифмировать вероятность ошибки и найти ноль производной. В итоге получается

\argmin\limits_k \prob (\text{ошибка}) \approx \frac{m}{n} \cdot \ln 2

Подставив это значение $k$ можно найти эту самую минимальную вероятность ошибки

\min\limits \prob (\text{ошибка}) \approx \left( 1 - \frac{1}{e} \right) ^{m/n \cdot \ln 2}