Фильтр Блума
Фильтр Блума - это пространственно-эффективная вероятностная структура данных, созданная для проверки наличия элемента в множестве. Он спроектирован невероятно быстрым при минимальном использовании памяти ценой потенциальных ложных срабатываний. Существует возможность получить ложноположительное срабатывание (элемента в множестве нет, но структура данных сообщает, что он есть), но не ложноотрицательное. Другими словами, очередь возвращает или "возможно в наборе", или "определённо не в наборе". Фильтр Блума может использовать любой объём памяти, однако чем он больше, тем меньше вероятность ложного срабатывания.
Блум предложил эту технику для применения в областях, где количество исходных данных потребовало бы непрактично много памяти, в случае применения условно безошибочных техник хеширования.
Описание алгоритма
Пустой фильтр Блума представлен битовым массивом из m битов, все биты которого обнулены. Должно быть определено k
независимых хеш-функций, отображающих каждый элемент множества в одну из m позиций в массиве, генерируя единообразное
случайное распределение. Обычно k задана константой, которая много меньше m и пропорциональна
количеству добавляемых элементов; точный выбор k и постоянной пропорциональности m определяются уровнем ложных
срабатываний фильтра.
Вот пример Блум фильтра, представляющего набор {x, y, z}. Цветные стрелки показывают позиции в битовом массиве,
которым привязан каждый элемент набора. Элемент w не в наборе {x, y, z}, потому что он привязан к позиции в битовом
массиве, равной 0. Для этой формы , m = 18, а k = 3.
Фильтр Блума представляет собой битовый массив из m бит. Изначально, когда структура данных хранит пустое множество, все
m бит обнулены. Пользователь должен определить k независимых хеш-функций h1, …, hk,
отображающих каждый элемент в одну из m позиций битового массива достаточно равномерным образом.
Для добавления элемента e необходимо записать единицы на каждую из позиций h1(e), …, hk(e)
битового массива.
Для проверки принадлежности элемента e к множеству хранимых элементов, необходимо проверить состояние битов
h1(e), …, hk(e). Если хотя бы один из них равен нулю, элемент не может принадлежать множеству
(иначе бы при его добавлении все эти биты были установлены). Если все они равны единице, то структура данных сообщает,
что е принадлежит множеству. При этом может возникнуть две ситуации: либо элемент действительно принадлежит множеству,
либо все эти биты оказались установлены по случайности при добавлении других элементов, что и является источником ложных
срабатываний в этой структуре данных.
Применения
Фильтр Блума может быть использован для блогов. Если цель состоит в том, чтобы показать читателям только те статьи, которые они ещё не видели, фильтр блума идеален. Он может содержать хешированные значения, соответствующие статье. После того, как пользователь прочитал несколько статей, они могут быть помещены в фильтр. В следующий раз, когда пользователь посетит сайт, эти статьи могут быть убраны из результатов с помощью фильтра.
Некоторые статьи неизбежно будут отфильтрованы по ошибке, но цена приемлема. То, что пользователь не увидит несколько статей в полне приемлемо, принимая во внимание тот факт, что ему всегда показываются другие новые статьи при каждом новом посещении.