В другом языковом разделе есть более полная статья Counting Bloom filter (англ.). |
Фильтр Блума с подсчётом (англ. Counting Bloom filter) — это обобщённая структура данных фильтра Блума, которая используется для добавления и удаления элементов в наборе данных. Как обобщённая форма фильтра Блума, ложноположительное срабатывание возможно, но ложноотрицательное — нет. Фильтр Блума с подсчётом был представлен Fan et al. (2000).
Описание алгоритма править
В отличие от фильтра Блума, фильтр Блума с подсчётом представляет собой m счётчиков с несколькими битами вместо битов. Изначально, когда структура данных хранит пустое множество, все m счётчиков обнулены. Пользователь должен определить k независимых хеш-функций h1, …, hk, отображающих каждый элемент в одну из m позиций массива достаточно равномерным образом. Когда элемент добавляется или удаляется из набора данных, к элементу применяются k хеш-функций и все из k местоположений в массиве увеличиваются или уменьшаются на единицу. Операция поиска проверяет, что каждый из требуемых счётчиков не равен нулю.
Арифметическое переполнение счётчиков является проблемой, и счётчики должны быть достаточно большими, чтобы сделать этот случай редким. Если это произойдёт, то операции увеличения должны оставить для счётчика максимально возможное значение.
Фильтр Блума можно рассматривать как фильтр Блума с подсчётом с размером счётчика в один бит.
Примечания править
Литература править
- Fan, Li; Cao, Pei; Almeida, Jussara; Broder, Andrei (2000), "Summary Cache: A Scalable Wide-Area Web Cache Sharing Protocol" (PDF), IEEE/ACM Transactions on Networking, 8 (3): 281—293, CiteSeerX 10.1.1.41.1487, doi:10.1109/90.851975 Архивная копия от 22 сентября 2017 на Wayback Machine. A preliminary version appeared at SIGCOMM '98.