Показать меню

Фильтр Блума

08.12.2020
313

Фильтр Блума (англ. Bloom filter) — это вероятностная структура данных, придуманная Бёртоном Блумом в 1970 году, позволяющая проверять принадлежность элемента к множеству. При этом существует возможность получить ложноположительное срабатывание (элемента в множестве нет, но структура данных сообщает, что он есть), но не ложноотрицательное.

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

Описание структуры данных

Фильтр Блума представляет собой битовый массив из m бит. Изначально, когда структура данных хранит пустое множество, все m бит обнулены. Пользователь должен определить k независимых хеш-функций h1, …, hk, каждая из которых отображает множество элементов в множество мощностью m. (Иными словами, каждому элементу хеш-функция сопоставляется число от 1 до m.) Для каждого элемента e биты массива с номерами h1(e), …, hk(e) равными значениям хеш-функций устанавливаются в 1.

Для проверки принадлежности элемента e к множеству хранимых элементов необходимо проверить состояние битов h1(e), …, hk(e). Если хотя бы один из них равен нулю, элемент не может принадлежать множеству (иначе бы при его добавлении все эти биты были установлены). Если все они равны единице, то структура данных сообщает, что е принадлежит множеству. При этом может возникнуть две ситуации: либо элемент действительно принадлежит множеству, либо все эти биты оказались установлены по случайности при добавлении других элементов, что и является источником ложных срабатываний в этой структуре данных.

Независимость хеш-функций обеспечивает минимальную вероятность повторения индексов hk(e), минимизируя число бит установленных в 1 несколько раз. (А это главный источник ложноположительных срабатываний.)

Вероятность ложноположительного срабатывания

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

Pr ( h i ( x ) = p ) = 1 m , p = 1 … m , {displaystyle Pr(h_{i}(x)=p)={frac {1}{m}},quad p=1ldots m,}

и, кроме того, значения h i ( x ) {displaystyle h_{i}(x)} являются независимыми в совокупности случайными величинами (для упрощения последующего анализа).

Тогда вероятность того, что в некоторый p-й бит не будет записана единица во время операции вставки очередного элемента равна

Pr ( h 1 ( x ) ≠ p ∩ … ∩ h k ( x ) ≠ p ) = Pr ( h i ( x ) ≠ p ) k = ( 1 − 1 m ) k . {displaystyle Pr(h_{1}(x) eq pcap ldots cap h_{k}(x) eq p)=Pr(h_{i}(x) eq p)^{k}=left(1-{frac {1}{m}} ight)^{k}.}

А вероятность того, что p-й бит останется равным нулю после вставки n различных элементов x1, …, xn в изначально пустой фильтр Блума равна

Pr ( ∀ i ∈ { 1 … k } ,   ∀ j ∈ { 1 … n } ,   h i ( x j ) ≠ p ) = ( 1 − 1 m ) k n ≈ e − k n / m {displaystyle Pr left(forall iin {1dots k}, forall jin {1ldots n}, h_{i}(x_{j}) eq p ight)=left(1-{frac {1}{m}} ight)^{kn}approx e^{-kn/m}}

для достаточно большого m ввиду второго замечательного предела.

Ложноположительное срабатывание состоит в том, что для некоторого элемента y, не равного ни одному из вставленных, все k бит с номерами hi(y) окажутся ненулевыми, и фильтр Блума ошибочно ответит, что y входит во множество вставленных элементов. Вероятность такого события примерно равна

( 1 − e − k n / m ) k . {displaystyle (1-e^{-kn/m})^{k}.}

Очевидно, что эта вероятность уменьшается с ростом m (размера битового массива) и увеличивается с ростом n (числа вставленных элементов). Для фиксированных m и n оптимальное число k (число хеш-функций), минимизирующих её, равно

k = m n ln ⁡ 2 ≈ 0,693 1 m n . {displaystyle extstyle k={frac {m}{n}}ln 2approx 0{,}6931{frac {m}{n}}.}

При этом сама вероятность ложного срабатывания равна

2 − k ≈ 0,618 5 m / n . {displaystyle 2^{-k}approx {0{,}6185}^{m/n}.}

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

Свойства

  • В отличие от многих других структур данных (например, хеш-таблиц), также хранящих множество элементов, фильтр Блума может представлять универсальное множество всех возможных элементов. В этом случае все биты в его битовом массиве равны единице.
  • Объединение и пересечение двух фильтров Блума одинакового размера и c одинаковым множеством хеш-функций может быть реализовано побитовыми операциями OR и AND над их битовыми массивами.

Применение

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

Примеры практических применений:

  • Прокси-сервер Squid использует фильтры Блума для опции cache digests.
  • Google BigTable использует фильтры Блума для уменьшения числа обращений к жесткому диску при проверке на существование заданной строки или столбца в таблице базы данных.
  • Компьютерные программы для проверки орфографии.
Еще по этой теме:
Конечное кольцо
21:26, 07 декабрь
Конечное кольцо
Конечное кольцо в общей алгебре — это кольцо, содержащее конечное число элементов (которое называется порядком кольца). Другими словами, это (непустое) конечное множество R
Кольцевой буфер
04:34, 07 декабрь
Кольцевой буфер
Кольцевой буфер, или циклический буфер (англ. ring-buffer) — это структура данных, использующая единственный буфер фиксированного размера, как будто бы после последнего элемента сразу же снова идет
Anope
04:49, 05 декабрь
Anope
Anope — сервисы для IRC-серверов. Поддерживается множество IRC-серверов, в том числе UnrealIRCd. История Вначале Anope был всего-лишь исправлением ошибок в сервисах Epona, так как их разработчик
Обратный элемент
23:38, 01 декабрь
Обратный элемент
Обратный элемент — термин в общей алгебре, обобщающий понятия обратного числа (для умножения) и противоположного числа (для сложения). Определения Пусть ( M
Методы построения педотрансферных функций
14:34, 13 март
Методы построения педотрансферных функций
Статистический регрессионный анализ был традиционным инструментом развития ПТФ в течение многих десятилетий. Преимущество регрессионной техники - возможность получить строгие статистические оценки
Метод треугольной нерегулярной сети
14:15, 13 март
Метод треугольной нерегулярной сети
Детерминистские методы могут быть разделены на две группы: глобальные и локальные. Глобальные методы при описании поверхности используют весь набор данных, локальные методы используют опорные точки,
Комментарии:
Добавить комментарий
Ваше Имя:
Ваш E-Mail: