Фильтр Блума - NiNa.Az

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

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

Конструкция

Пример фильтра Блума с ${\displaystyle m=18}$ и ${\displaystyle k=3}$, хранящего множество ${\displaystyle \{x,y,z\}}$. Цветные стрелки указывают на места в битовом массиве, соответствующие каждому элементу множества. Этот фильтр Блума может определить, что элемент ${\displaystyle w}$ не входит в множество, так как один из соответствующих ему битов равен нулю.

Фильтр Блума организуется как битовый массив из ${\displaystyle m}$ бит; изначально, когда структура данных хранит пустое множество, все ${\displaystyle m}$ бит обнулены. Пользователь должен определить ${\displaystyle k}$ независимых хеш-функций ${\displaystyle h_{1},\dots ,h_{k}}$, каждая из которых отображает множество элементов в множество мощностью ${\displaystyle m}$ — иными словами, каждому элементу хеш-функция сопоставляет число от 1 до ${\displaystyle m}$. Для каждого элемента ${\displaystyle e}$ биты массива с номерами ${\displaystyle h_{1}(e),\dots ,h_{k}(e)}$ равными значениям хеш-функций устанавливаются в 1.

Для проверки принадлежности элемента ${\displaystyle e}$ к множеству хранимых элементов необходимо проверить состояние битов ${\displaystyle h_{1}(e),\dots ,h_{k}(e)}$. Если хотя бы один из них равен нулю, элемент не может принадлежать множеству (иначе бы при его добавлении все эти биты были установлены). Если все они равны единице, то структура данных сообщает, что ${\displaystyle e}$ может принадлежать множеству. При этом может возникнуть две ситуации: либо элемент действительно принадлежит множеству, либо все эти биты оказались установлены по случайности при добавлении других элементов, что и является источником ложных срабатываний в этой структуре данных.

Независимость хеш-функций обеспечивает минимальную вероятность повторения индексов ${\displaystyle h_{k}(e)}$, минимизируя число бит установленных в 1 несколько раз. (А это главный источник ложноположительных срабатываний.)

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

Объединение и пересечение двух фильтров Блума одинакового размера и c одинаковым множеством хеш-функций может быть реализовано побитовыми операциями OR и AND над их битовыми массивами.

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

Оценка вероятности ложного срабатывания ${\displaystyle p}$ как функция от числа вставленных элементов ${\displaystyle n}$ и размера битового массива ${\displaystyle m}$, при оптимальном числе хеш-функций ${\displaystyle k=(m/n)\ln 2}$.

Если размер битового массива равен ${\displaystyle m}$ бит, задано ${\displaystyle k}$ хеш-функций, множество хеш-функций выбирается случайно, и для любого элемента ${\displaystyle x}$ каждая хеш-функция ${\displaystyle h_{i}}$ назначает ему одно из мест в битовом массиве с равной вероятностью:

${\displaystyle \Pr(h_{i}(x)=p)={\frac {1}{m}},\quad p=1\ldots m}$,

и, кроме того, значения ${\displaystyle h_{i}(x)}$ являются независимыми в совокупности случайными величинами (для упрощения последующего анализа), то вероятность того, что в некоторый ${\displaystyle p}$-й бит не будет записана единица во время операции вставки очередного элемента равна:

${\displaystyle \Pr(h_{1}(x)\neq p\cap \ldots \cap h_{k}(x)\neq p)=\Pr(h_{i}(x)\neq p)^{k}=\left(1-{\frac {1}{m}}\right)^{k}}$.

Вероятность того, что ${\displaystyle p}$-й бит останется равным нулю после вставки ${\displaystyle n}$ различных элементов ${\displaystyle x_{1},\dots ,x_{n}}$ в изначально пустой фильтр Блума равна:

${\displaystyle \Pr \left(\forall i\in \{1\dots k\},\ \forall j\in \{1\ldots n\},\ h_{i}(x_{j})\neq p\right)=\left(1-{\frac {1}{m}}\right)^{kn}\approx e^{-kn/m}}$

для достаточно большого ${\displaystyle m}$ ввиду второго замечательного предела.

Ложноположительное срабатывание состоит в том, что для некоторого элемента ${\displaystyle y}$, не равного ни одному из вставленных, все ${\displaystyle k}$ бит с номерами ${\displaystyle h_{i}(y)}$ окажутся ненулевыми, и фильтр Блума ошибочно ответит, что ${\displaystyle y}$ входит во множество вставленных элементов. Вероятность такого события примерно равна:

${\displaystyle (1-e^{-kn/m})^{k}}$.

Очевидно, что эта вероятность уменьшается с ростом ${\displaystyle m}$ (размера битового массива) и увеличивается с ростом ${\displaystyle n}$ (числа вставленных элементов). Для фиксированных ${\displaystyle m}$ и ${\displaystyle n}$ оптимальное число ${\displaystyle k}$ (число хеш-функций), минимизирующих её, равно:

${\displaystyle \textstyle k={\frac {m}{n}}\ln 2\approx 0{,}6931{\frac {m}{n}}}$.

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

${\displaystyle 2^{-k}\approx {0{,}6185}^{m/n}}$.

Как следствие, заметим, что для того, чтобы фильтр Блума поддерживал заданную ограниченную вероятность ложного срабатывания, размер битового массива должен быть линейно пропорционален числу вставленных элементов.

Применение

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

Прокси-сервер Squid использует фильтры Блума для опции дайджетов кэша. Google BigTable использует фильтры Блума для уменьшения числа обращений к подсистеме хранения при проверке на существование заданной строки или столбца в таблице базы данных. Также многие программы для проверки орфографии используют фильтры Блума.

Примечания

1. Bloom, Burton H. (1970), Space/time trade-offs in hash coding with allowable errors, Communications of the ACM, 13 (7): 422–426, doi:10.1145/362686.362692
2. Bigtable: A Distributed Storage System for Structured Data  (неопр.). Дата обращения: 30 июля 2012. Архивировано 8 февраля 2015 года.