0x00 Предисловие

Фильтр Блума — это структура бинарных векторных данных, предложенная Бертоном Х. Блумом в 1970 году. Она имеет хорошую пространственную и временную эффективность и используется для определения того, является ли элемент членом множества.

Оригинальная статья Bloom Filter была опубликована в ACM под названием «Компромисс пространства/времени в хеш-кодировании с допустимыми ошибками», которую можно скачать и прочитать, если вам интересно. В этой статье в основном рассказывается об основных принципах, реализации кода и расчете ложных срабатываний фильтра Блума.Для детей, которые прочитали статью о BitMap, будет очень просто прочитать эту статью.

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

0x01 Принцип

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

Непосредственно над рисунком, по рисунку, чтобы примерно разобраться в алгоритме процесса.

1. Инициализировать битовый массив длины m и установить все элементы в 0;

2. для сбораS={a1, a2,…,an}Для любого элемента a в , используйте k хэш-функций для его вычисления: , и установите th позицию в битовом массиве на 1;

3. Сделайте то же самое для всех членов S.

Есть так много основных принципов, просто посмотрите на пример на рисунке, чтобы понять. такой как сейчасdantezhaoОбозначается BF, мы будем использовать две хэш-функции соответственноdantezhaoВычислите, результаты вычислений равны 5 и 19, а затем установите 5-й и 19-й биты в битовом массиве равными 1 соответственно.

При запросеdantezhaoНезависимо от того, находится ли он в коллекции, просто используйте ту же хеш-функцию для вычисления, если биты соответствующего битового массива равны 1, это означает, что он существует. Пока любой бит равен 0, это означает, что он не существует.

0x02 Реализация

Конкретная реализация может напрямую смотреть на код, простая версия, написанная на Python, всего около 20 строк. Код очень близок к реализации кода BitMap, разница в том, что хеш-функция становится множественной.

0x03 частота ложных срабатываний

Основной принцип БФ тоже очень прост, но есть еще некоторые моменты знаний, на которые нужно обратить внимание. Например, в BF будет ошибочное суждение, то есть член, которого нет в наборе изначально, но будет оцениваться как находящийся в наборе. Чтобы контролировать частоту ложных срабатываний в приемлемом диапазоне, нам необходимо правильно использовать несколько факторов, которые могут повлиять на частоту ложных срабатываний: размер набора n, количество хэш-функций k и размер битового массива m.

Среди этих трех влияющих факторов влияние m и n на частоту ошибочных оценок является более интуитивным.

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

Размер битового массива m: Точно так же, когда другие условия фиксированы, чем больше значение размера битового массива m, тем больше битов, остающихся нулевыми в массиве, поэтому частота ложных срабатываний будет меньше.

Количество хеш-функций k: сложнее анализировать.Например, если m и n фиксированы, то чем больше используется хеш-функций, тем больше позиций в битовом массиве будет установлено в 1, то есть повышенный процент ложных срабатываний, но при запросе , Чем больше хэш-функций, тем меньше вероятность неправильной оценки.

Тогда как найти наилучшее значение для трех факторов? Процесс вывода здесь опущен, а вывод дан непосредственно.

При заданных m и n значение частоты ложных срабатываний p является наименьшим, когда k принимает следующие значения:

В это время частота ложных срабатываний p равна:

В практических приложениях более распространенным требованием является знание размера множества n и задание частоты ложных срабатываний p.Необходимо рассчитать, сколько памяти следует выделить для BF, то есть подтвердить размер m, который может быть решена следующей формулой задачи:

С помощью этих трех формул можно гибко задавать различные параметры для разумного использования BF в практических приложениях.

0xFF Сводка

Традиционный BF может только добавлять элементы, не может считать элементы и не может удалять элементы. Действия подсчета и удаления могут поддерживаться, если биты базового массива заменены целыми числами. При вставке элемента добавлять единицу к соответствующим k целым числам, при запросе возвращать минимальное значение из k целых чисел, при удалении уменьшать соответствующие k целых чисел на единицу. Это улучшенная версия BF: Couting Bloom Filter, которая будет опубликована позже.