Фильтр Блума: как сказать «возможно есть» или «точно нет», почти не тратя память
Существует структура, которая на вопрос «видела ли ты этот элемент?» честно отвечает «точно нет» или осторожно «возможно, да» — и при этом занимает в разы меньше места, чем настоящее множество. Цена — допущение редких ошибок.
Иногда выгодно пожертвовать абсолютной точностью ради огромной экономии памяти — и получить структуру, которая ошибается лишь в одну, безопасную сторону.
Фильтр Блума отвечает либо «точно нет», либо «возможно, да». Он никогда не пропустит то, что есть, но иногда переоценит — за это его терпят ради колоссальной экономии памяти.
Зачем жертвовать точностью
Обычное хеш-множество отвечает на «есть ли элемент?» точно — но хранит сами элементы, а это память. Когда элементов миллиарды (все когда-либо виденные URL, все известные пароли из утечек), даже множество становится слишком тяжёлым.
А теперь хитрая мысль: что, если нам не нужна стопроцентная точность? Что, если редкая ошибка в безопасную сторону допустима — лишь бы структура занимала крохи памяти? Именно на этом размене построен фильтр Блума — вероятностная структура данных.
Как он устроен
Внутри фильтра — длинный ряд битов (нулей и единиц), поначалу все нули. И несколько разных хеш-функций. Вот и вся конструкция: ряд лампочек и несколько способов выбирать, какие зажечь.
Добавление элемента
Чтобы добавить элемент, прогоняем его через все хеш-функции. Каждая укажет на какую-то позицию в ряду битов. В этих позициях ставим единицы (зажигаем лампочки). Скажем, для слова «кот» три функции дали позиции 2, 5 и 9 — зажигаем биты 2, 5 и 9. Сам «кот» нигде не хранится — остаются только следы в виде зажжённых битов.
Проверка наличия
Спрашиваем «есть ли кот?» — снова считаем те же хеши, получаем позиции 2, 5, 9 и смотрим на биты. Тут два исхода. Если хоть один из этих битов — ноль, значит «кот» точно не добавляли (иначе все три горели бы). Ответ — точно нет, без вариантов. А если все три бита — единицы, ответ осторожный: возможно, есть.
Откуда берутся ошибки
Почему «возможно», а не «точно да»? Потому что нужные биты могли зажечься от других элементов. Добавили «пёс» и «рыбу», и так совпало, что вместе они зажгли как раз биты 2, 5 и 9. Тогда фильтр на вопрос про «кота» ответит «возможно, есть», хотя кота не добавляли. Это называется ложное срабатывание.
Ключевой момент: ошибка возможна только в одну сторону. Фильтр может ложно сказать «возможно, есть» — но никогда не скажет «нет» про то, что на самом деле добавлено. Ведь при добавлении мы зажгли все нужные биты, и потухнуть они не могут. Поэтому ответ «нет» абсолютно надёжен, а ответ «да» требует перепроверки.
Фильтр Блума в коде
class BloomFilter:
def __init__(self, size=100):
self.size = size
self.bits = [0] * size
def _positions(self, item):
# две простые «разные» хеш-функции
h1 = hash(item) % self.size
h2 = hash(item + "salt") % self.size
return [h1, h2]
def add(self, item):
for p in self._positions(item):
self.bits[p] = 1 # зажигаем биты
def maybe_contains(self, item):
return all(self.bits[p] for p in self._positions(item))
bloom = BloomFilter()
bloom.add("кот")
bloom.add("пёс")
print(bloom.maybe_contains("кот")) # True — возможно, есть
print(bloom.maybe_contains("слон")) # False — точно нет (почти наверняка)
Здесь «слон» вернёт False, потому что хотя бы один из его битов наверняка погашен. А вот любой добавленный элемент всегда даст True. Чем больше ряд битов и чем больше хеш-функций (в меру), тем реже случаются ложные срабатывания.
Где это окупается
Размен «капля памяти в обмен на редкие ложные да» окупается в больших системах. Базы данных через фильтр Блума быстро отсеивают запросы к данным, которых точно нет, не трогая медленный диск. Браузеры так проверяют адреса по списку опасных сайтов: «точно нет» — пропускаем мгновенно, «возможно, да» — идём перепроверять по полной базе. Сервисы используют его, чтобы не показывать пользователю уже виденные новости.
Логика везде одна: дешёвый фильтр Блума отбивает основную массу запросов своим надёжным «нет», а к точной (и дорогой) проверке обращаются лишь в редких случаях «возможно, да». Фильтр Блума — отличный пример того, что иногда «почти правильный, но крошечный» ответ полезнее, чем «идеально точный, но огромный».