Bloom Filter

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

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

Описание алгоритма

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

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

Операции

Фильтр Блума может выполнять две основные операции: вставка и поиск . Поиск может привести к ложным срабатываниям. Удаление не возможно.

Другими словами, фильтр может принимать элементы. Когда мы идем, чтобы проверить, был ли элемент ранее вставлен, он может сказать нам «нет» или «возможно».

И вставка, и поиск являются O(1)операциями.

Изготовление фильтра

Фильтр Блума создается путем выделения определенного размера. В нашем примере мы используем 100длину по умолчанию. Все места инициализированы в false.

Вставка

Во время вставки несколько хеш-функций, в нашем случае 3хеш-функции, используются для создания хешей ввода. Эти хеш-функции выводят индексы. При каждом получении индекса мы просто меняем значение в нашем фильтре Блума на true.

Поиск

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

Однако, это не точно, потому что возможно, что другие ранее вставленные значения перевернули значения в true. Значения не обязательно trueсвязаны с тем, что в данный момент выполняется поиск. Абсолютная уверенность невозможна, если только ранее не был вставлен только один элемент.

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

Ложные срабатывания

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

Формула для расчета вероятности ложного срабатывания:

(1 - е- кн / м ) к

k = количество хеш-функций

m = размер фильтра

n = количество вставленных предметов

Эти переменные, k, m, и n, должны быть выбраны на основе того, насколько приемлемо ложные срабатывания. Если значения выбраны и результирующая вероятность слишком высока, значения должны быть изменены, а вероятность пересчитана.

Приложения

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

Некоторые статьи неизбежно будут отфильтрованы по ошибке, но стоимость приемлема. Это нормально, если пользователь никогда не видит несколько статей, если у них есть другие, совершенно новые, чтобы видеть каждый раз, когда они посещают сайт.