Фильтр Блума с подсчётом () — обобщённая структура данных фильтра Блума, которая используется для добавления и удаления элементов в наборе данных. Как обобщённая форма фильтра Блума, ложноположительное срабатывание возможно, но ложноотрицательное — нет. Фильтр Блума с подсчётом был представлен .
Описание алгоритма В отличие от фильтра Блума, фильтр Блума с подсчётом представляет собой m счётчиков с несколькими битами вместо битов. Изначально, когда структура данных хранит пустое множество, все m счётчиков обнулены. Пользователь должен определить k независимых хеш-функций h1, …, hk, отображающих каждый элемент в одну из m позиций массива достаточно равномерным образом. Когда элемент добавляется или удаляется из набора данных, к элементу применяются k хеш-функций и все из k местоположений в массиве увеличиваются или уменьшаются на единицу. Операция поиска проверяет, что каждый из требуемых счётчиков не равен нулю.
Арифметическое переполнение счётчиков является проблемой, и счётчики должны быть достаточно большими, чтобы сделать этот случай редким. Если это произойдёт, то операции увеличения должны оставить для счётчика максимально возможное значение.
Фильтр Блума можно рассматривать как фильтр Блума с подсчётом с размером счётчика в один бит.
Примечания
Литература . A preliminary version appeared at SIGCOMM '98.
Категория:Структуры данных Категория:Хеширование