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

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

0x01 Принцип

1. Почему BF не поддерживает удаление

Почему BF не может удалять элементы? Мы можем привести пример для иллюстрации.

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

Вот проблема! Теперь предположим, что сам yyj является элементом множества.Если нам нужно проверить, находится ли yyj в множестве, мы будем судить, равны ли 16-й и 26-й биты 1 после вычисления с помощью хэш-функции, и тогда мы получим 16-й бит , Результат 0, то есть yyj не принадлежит множеству. Очевидно, здесь просчет.

2. Что такое фильтр Блума?

Появление Counting Bloom Filter решает указанные выше проблемы, он расширяет каждый бит стандартного битового массива Bloom Filter в небольшой счетчик (Counter), и при вставке элементов выдает соответствующее k (k — количество хеш-функций). счетчика увеличивается на 1, а значение соответствующих k счетчиков уменьшается на 1 при удалении элемента. Счетный фильтр Блума добавляет операции удаления в фильтр Блума за счет того, что занимает в несколько раз больше места для хранения. Основной принцип прост? Посмотрите на картинку ниже, чтобы понять это и В чем разница между фильтрами Блума.

3. Выбор размера счетчика

Одно из основных отличий между CBF и BF заключается в том, что CBF использует счетчик для замены одного бита в BF.Так каков подходящий размер счетчика? Здесь мы должны рассмотреть вопрос использования пространства.С точки зрения использования, конечно, чем больше, тем лучше, потому что чем больше Счетчик, тем больше информации он может отображать. Однако больший счетчик означает большее использование ресурсов, и во многих случаях это приведет к большой трате места.

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

Согласно описанию в статье, вероятность того, что значение определенного счетчика больше или равно i, может быть описана следующей формулой, где n — размер набора, m — количество счетчиков, а k количество хеш-функций.

В предыдущей статье «Математические основы фильтра Блума» был сделан вывод, что оптимальное значение k равноk = m/n * ln2, который можно получить, подставив его в формулу.

Если бы каждому счетчику было выделено 4 бита, счетчик переполнился бы, когда значение достигло 16. Эта вероятность такова, это значение достаточно мало, так что для большинства приложений достаточно 4 бита.

Что касается выбора размера счетчика в CBF, в основном обратитесь к этому документу: «Сводный кэш: масштабируемый протокол общего доступа к веб-кэшу глобальной сети», который специально объяснен на 6-й и 7-й страницах документа. Детали здесь не выводятся, а дается только общее описание.Заинтересованные детской обуви могут обратиться к оригинальной статье.

0x03 Простая реализация

Или реализовать простую программу для ознакомления с принципом CBF.Между этим и BF есть два отличия:

• Во-первых, мы использовали не массив битов, предоставленный bitarray, а массив байтов, предоставленный bytearray, поэтому диапазон значений каждого счетчика составляет 0–255.

• Другой способ — добавить метод удаления для удаления элементов из коллекции.

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

Хотя CBF решает проблему неспособности BF удалять элементы, в нем все еще есть много недочетов, требующих доработки, например, введение Counter принесет много растраты ресурсов, а FP CBF по-прежнему имеет много возможностей для уменьшения Таким образом, в реальных сценариях использования будет много обновленных версий CBF.

Например, SBF (спектральный фильтр Блума) предлагает концепцию запроса частоты элемента на основе CBF, расширяя применение CBF на область мультимножества; dlCBF (d-Left Counting Bloom Filter) использует хеширование d-left для хранения отпечатков пальцев. , чтобы решить проблему балансировки нагрузки хэш-таблицы; ACBF (фильтр Блума с точным подсчетом) использует индексацию смещения для Массив счетчика разделен на несколько уровней, чтобы уменьшить количество ложных срабатываний. Это содержимое, есть возможность поделиться.