Site icon AppTractor

Что такое Фильтр Блума

AppTractor

Фильтр Блума (Bloom filter) — это вероятностная структура данных, которая позволяет очень быстро и эффективно проверять, принадлежит ли элемент множеству, используя очень мало памяти. Однако у неё есть особенность: фильтр может дать ложно-положительный ответ, но никогда не ошибается, говоря, что элемента точно нет.

Блум-фильтр отвечает на вопрос: «Принадлежит ли элемент множеству?»

Если ответ «нет» — элемент точно не принадлежит множеству.

Если ответ «да» — элемент возможно принадлежит множеству (может быть ложное срабатывание).

Простыми словами

Фильтр Блума — это такая особая проверка, которая быстро говорит, встречался ли нам объект раньше. Он работает как память, которая не всё запоминает точно, но зато делает это очень быстро и почти не занимает места. Представь, что у тебя есть коробка с лампочками, и когда ты видишь новое слово, ты зажигаешь несколько из них по определённым правилам. Позже, когда ты снова видишь слово, ты просто смотришь — те же лампочки уже горят или нет. Если хоть одна из нужных лампочек не горит — точно такого слова не было. А если все горят — может быть, было, а может и случайно так совпало. То есть фильтр никогда не скажет «да», если на самом деле «нет», но иногда может сказать «да», когда правильный ответ — «нет, просто похоже». Это делает его полезным, когда нужно быстро проверять, что-то мы уже видели или ещё нет, особенно когда таких проверок миллионы.

Где используется

Фильтры Блума применяются там, где:

Примеры: кеширование в Redis, проверка спама, база данных Bigtable от Google, криптовалютные кошельки, маршрутизация в сетях.

Как работает Фильтр Блума

  1. Создаём битовый массив фиксированной длины (например, 1000 бит).
  2. Используем k хеш-функций, которые преобразуют элемент в k индексов битов.
  3. При добавлении элемента:
    • Вычисляем k хешей.
    • Устанавливаем соответствующие биты в массиве в 1.
  4. При проверке:
    • Считаем те же хеши.
    • Если хотя бы один бит равен 0, элемента точно нет.
    • Если все соответствующие биты равны 1, элемент возможно есть.

Пример на Swift

Вот простая реализация Фильтра Блума на Swift:

import Foundation

struct BloomFilter {
    private var bitArray: [Bool]
    private let size: Int
    private let hashCount: Int

    init(size: Int, hashCount: Int) {
        self.size = size
        self.hashCount = hashCount
        self.bitArray = Array(repeating: false, count: size)
    }

    private func hash(_ value: String, seed: Int) -> Int {
        var hasher = Hasher()
        hasher.combine(seed)
        hasher.combine(value)
        return abs(hasher.finalize()) % size
    }

    mutating func add(_ item: String) {
        for i in 0..<hashCount {
            let index = hash(item, seed: i)
            bitArray[index] = true
        }
    }

    func mightContain(_ item: String) -> Bool {
        for i in 0..<hashCount {
            let index = hash(item, seed: i)
            if !bitArray[index] {
                return false
            }
        }
        return true
    }
}

Пример использования:

var filter = BloomFilter(size: 1000, hashCount: 3)

filter.add("apple")
filter.add("banana")

print(filter.mightContain("apple"))   // true
print(filter.mightContain("banana"))  // true
print(filter.mightContain("orange"))  // возможно true, но скорее false

Плюсы и минусы

Плюсы:

Минусы:

Расширенные версии

Заключение

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

Если вы работаете с большим количеством данных и часто задаётесь вопросом: «Был ли уже этот элемент?» — фильтр Блума может стать отличным решением.

Ссылки

Exit mobile version