Фильтр Блума: «точно нет» или «может быть»

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

Как думаешь, можно ли проверять наличие, не храня сами элементы

Хеш-множество отвечает на «есть ли x» точно, но хранит сами элементы - память порядка их суммарного размера. А если элементов миллиарды (все виденные URL, все пароли из утечек), а памяти мало? Тут возникает смелая идея: а что если НЕ хранить элементы вообще, а держать лишь следы их присутствия - несколько битов на каждый? Тогда память резко падает. Плата очевидна: без самих элементов мы не сможем отличить «этот бит выставил именно x» от «его выставил кто-то другой». Значит ответ «есть» станет неточным. Вопрос - в какую сторону будет ошибка и можно ли сделать её ПОЛЕЗНОЙ. Фильтр Блума устраивает ошибку так, что «нет» всегда правда, а это часто именно то, что нужно.

На что это похоже

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

Механизм: m бит, k хеш-функций

Фильтр Блума - битовый массив длины m (сначала все нули) и k независимых хеш-функций, каждая даёт номер бита в [0, m).

добавить(x):
    for i in 1..k:
        bits[ h_i(x) ] = 1          # выставить k битов в единицу

проверить(x):
    for i in 1..k:
        если bits[ h_i(x) ] == 0:
            вернуть «ТОЧНО НЕТ»      # хоть один ноль - элемента не было
    вернуть «ВОЗМОЖНО ЕСТЬ»          # все k единиц - но могли выставить другие

Асимметрия ответов - суть структуры:

• «Точно нет» - НАДЁЖНО. Если бы x добавляли, все его k битов были бы 1; раз хоть один 0 - его не добавляли. Ложноотрицательных НЕТ.
• «Возможно есть» - НЕнадёжно. Все k битов x могут оказаться 1 не потому, что добавляли x, а потому, что их по отдельности выставили ДРУГИЕ элементы. Это ложноположительное срабатывание, и его вероятность p растёт с заполнением.

Удалять из обычного фильтра Блума НЕЛЬЗЯ: сбросив биты x в 0, можно погасить биты, нужные другому элементу (появятся ложноотрицательные).

Правило

Фильтр Блума - m бит и k хеш-функций. Добавить x: выставить биты h₁(x)…hₖ(x) в 1. Проверить x: хоть один из этих битов 0 → «ТОЧНО НЕТ» (надёжно, ложноотрицательных нет); все 1 → «ВОЗМОЖНО ЕСТЬ» (ложноположительное с вероятностью p). Удалять нельзя. Память - около 1.44·log₂(1/p) бит на элемент (≈ 10 бит на элемент для p = 1%), в разы меньше хранения самих элементов. Применяют как ДЕШЁВЫЙ предфильтр: «точно нет» сразу экономит дорогую полную проверку.

Разбор: почему нет ложноотрицательных, но есть ложноположительные

Асимметрия ошибок - главное свойство, и она логична. Биты только ВЫСТАВЛЯЮТСЯ в 1, никогда не сбрасываются (пока не удаляем). Значит если элемент x когда-то добавили, все его k битов стоят в 1 НАВСЕГДА - проверка увидит все единицы и не скажет ложно «нет». Отсюда: «нет» - всегда правда, ложноотрицательных не бывает. Обратная сторона: бит 1 не помнит, КТО его выставил. Все k битов проверяемого y могут оказаться единицами, даже если y не добавляли, - просто эти биты по отдельности зажгли другие элементы (h₁(y) совпал с чьим-то битом, h₂(y) - с другим, и т.д.). Тогда фильтр ошибочно скажет «возможно есть» - это ложноположительное. Чем больше элементов добавлено, тем больше единиц, тем чаще случайно «все единицы» - тем выше p. Ошибка строго ОДНОСТОРОННЯЯ, и это делает фильтр полезным: доверяй «нет», перепроверяй «да».

Разбор: как прикинуть размер под заданную долю ошибок

Размер фильтра подбирают под нужную долю ложных срабатываний p. Три параметра связаны: число элементов n, число бит m, число функций k. Вероятность ложного срабатывания p ≈ (1 − e^{−k·n/m})^k. Из неё выводят рабочие формулы:

• Оптимальное число функций при заданных m, n: k ≈ 0.69 · m/n (примерно ln 2 на бит на элемент). Слишком мало функций - легко случайно совпасть; слишком много - быстро забиваем все биты единицами.
• Бит на элемент под целевую p: m/n ≈ 1.44 · log₂(1/p). Подставим: для p = 1% (1/p = 100, log₂ 100 ≈ 6.64) выходит ≈ 9.6 бит на элемент; для p = 0.1% - ≈ 14.4 бита. Правило «около 10 бит на элемент даёт 1% ошибок» - отсюда.

Смысл: чтобы ужать ошибку в 10 раз, добавляют лишь несколько бит на элемент (log₂ растёт медленно) - вот почему фильтр так экономен. Хранить сами URL или пароли стоило бы десятки-сотни БАЙТ на штуку, а фильтр обходится десятком БИТ.

Что ломается без этого

Первая ошибка - доверять ответу «возможно есть» как точному: он врёт с вероятностью p, его надо ПЕРЕПРОВЕРЯТЬ настоящим источником. Доверять можно только «точно нет». Второе - пытаться УДАЛИТЬ элемент, сбросив его биты: погасишь биты, общие с другими элементами, - появятся ложноотрицательные, и главное свойство («нет всегда правда») сломается. Для удаления берут другой вариант (счётный фильтр Блума, где вместо битов счётчики). Третье - взять слишком маленький m для своего n: биты быстро забьются единицами, p подскочит к 100%, фильтр станет бесполезным (всегда «возможно есть»). Размер надо считать под n и целевую p. Четвёртое - брать слишком много или мало функций k: оптимум ≈ 0.69·m/n, отклонение в любую сторону ухудшает p.

Зачем это в работе

Фильтр Блума - рабочая лошадка систем с ОГРОМНЫМ числом элементов и дефицитом памяти, где ответ «точно нет» экономит дорогую операцию. Базы данных (Cassandra, HBase, RocksDB) держат фильтр Блума на диск-таблицу: прежде чем лезть за ключом на медленный диск, спрашивают фильтр - «точно нет» отменяет чтение диска, огромная экономия. Браузеры и антивирусы проверяют URL по фильтру известных вредоносных: «точно нет» - пропускаем сразу, «возможно» - идём в полную (медленную) базу. CDN и кеши так отсекают «этого точно нет в кеше». Сервисы проверки паролей на утечку - тем же приёмом. Общий паттерн: дешёвый фильтр отвечает мгновенно и по памяти почти бесплатно, беря на себя массовые «нет», а дорогую точную проверку зовут лишь на редкие «может быть». Это и есть инженерная ценность вероятностной структуры: пожертвовать точностью ответа «да» ради колоссальной экономии памяти и времени на ответах «нет».

Теперь сам

Фильтр Блума ответил на запрос «есть ли x» - «возможно есть». Можно ли на основании этого утверждать, что x точно добавляли? А если бы ответ был «точно нет»?