Фильтр Блума

Алгоритмы   25 июля 2012  Автор статьи:  

Фильтр Блума — вероятностная структура данных, позволяющая компактно хранить множество элементов и поддерживать две операции: добавление элемента в множество и проверка принадлежности элемента множеству.
Одним способов организации фильтра является использование битовой таблицы необходимого размера, а добавление и поиск элемента будет осуществляться с помощью хэш-функции. При операциях хэш-функция определяет бит, при добавлении элемента у этого бита состояние изменится с 0 на 1, а при поиске — наличие этого элемента будет определяться состоянием бита. Недостаток этого способа заключается в том, что при работе хэш-функции возможны коллизии и из-за этого велика вероятность ложного срабатывания(поиск для несуществующего элемента поиск даст положительный результат). В ныне используемом фильтре Блума количество ложных срабатываний уменьшается путем использования вместо одной k отличных друг от друга хэш-функций. В этом случае при добавлении элемента будут помечаться сразу k различных бит, а при поиске — проверка этих k бит, но поиск даст положительный результат только если у всех k бит их состояния будут равны 1. Оптимальное количество хэш-функций определяется следующей формулой: k = \ln{2}\frac{m}{n}\approx \frac{m}{n}. Где m — мощность(т.е количество возвращаемых значений) хэш-функции, а n — количество элементов битовой таблицы. При использовании k различных хэш-функций, вероятность ложного срабатывания составляет 2^{-k}.

Научиться программировать

  • на Delphi

  • на Java

  • на C++