- PVSM.RU - https://www.pvsm.ru -
Фильтр Блума представляет собой структуру данных, которая может эффективно определить является ли элемент возможным элементом набора или определенно не относится к нему. Эта статья продемонстрирует простую реализацию фильтра Блума в C++.
Давайте сначала определим интерфейс данного фильтра. Можно выделить три основные функции:
Несколько задействованных переменных, включая небольшое количество векторов, также содержат состояние фильтра.
#include <vector>
struct BloomFilter {
BloomFilter(uint64_t size, uint8_t numHashes);
void add(const uint8_t *data, std::size_t len);
bool possiblyContains(const uint8_t *data, std::size_t len) const;
private:
uint64_t m_size;
uint8_t m_numHashes;
std::vector<bool> m_bits;
};
Стоит отметить, что std::vector является намного более эффективной специализацией std::vector, требует только один бит на элемент (в отличие от одного байта в типичных реализациях).
Можно обработать эту структуру по шаблону, как расширение. Вместо жесткого кодирования ключевых типов и хеш-функций, мы можем обработать класс по шаблону с чем-то подобным:
template< class Key, class Hash = std::hash<Key> >
struct BloomFilter {
...
};
Это позволит фильтру Блума быть обобщенным для более сложных типов данных.
Есть два параметра для построения фильтра Блума:
Мы можем вычислить ложный положительный коэффициент ошибок — n, на основе размера фильтра — m, числа хэш-функций — K и число вложенных элементов -N, с помощью формулы:
Эта формула не очень полезна в таком виде. Но нам нужно знать насколько большой фильтр должен быть и сколько хеш-функций понадобится, чтобы использовать, учитывая предполагаемое количество элементов набора и коэффициент ошибок. Есть два уравнения, которые мы можем использовать для расчета этих параметров:
Вы можете задаться вопросом, как же реализовать kk хеш-функции; двойное хеширование может использоваться, чтобы генерировать kk значения хэш-функции, не влияя на вероятность ложно-положительного результата! Такой результат можно получить используя формулу, где i — ординал, м — размер фильтра Блума и x — значение, которое будет хешировано:
Для начала нужно написать конструктор. Он просто записывает параметры масштабирования и битовый массив.
#include "BloomFilter.h"
#include "MurmurHash3.h"
BloomFilter::BloomFilter(uint64_t size, uint8_t numHashes)
: m_size(size),
m_numHashes(numHashes) {
m_bits.resize(size);
}
Далее давайте напишем функцию для вычисления 128 — битного хэша данного элемента. В данной реализации используется MurmurHash3 [1], 128 бит хэш — функция, которая имеет хорошие компромиссы между производительностью, распределение, потоковым поведением и сопротивлением противоречиям. Поскольку эта функция генерирует 128 бит хэш и нам нужно 2х64 битные хэши, мы можем разделить возвращенный хэш пополам, чтобы получить хэшa(x) хэшb(x).
std::array<uint64_t, 2> hash(const uint8_t *data,
std::size_t len) {
std::array<uint64_t, 2> hashValue;
MurmurHash3_x64_128(data, len, 0, hashValue.data());
return hashValue;
}
Теперь, когда у нас есть хэш-значения, нужно написать функцию, чтобы вернуть выходной сигнал n хэш-функции.
inline uint64_t nthHash(uint8_t n,
uint64_t hashA,
uint64_t hashB,
uint64_t filterSize) {
return (hashA + n * hashB) % filterSize;
}
Все, что осталось сделать — это написать функции для набора контрольных битов для заданных элементов.
void BloomFilter::add(const uint8_t *data, std::size_t len) {
auto hashValues = hash(data, len);
for (int n = 0; n < m_numHashes; n++) {
m_bits[nthHash(n, hashValues[0], hashValues[1], m_size)] = true;
}
}
bool BloomFilter::possiblyContains(const uint8_t *data, std::size_t len) const {
auto hashValues = hash(data, len);
for (int n = 0; n < m_numHashes; n++) {
if (!m_bits[nthHash(n, hashValues[0], hashValues[1], m_size)]) {
return false;
}
}
return true;
}
С помощью фильтра Блума 4.3MБ и 13 хэш-функции, вставляя элементы 1.8МБ приняли примерно 189 наносекунд для каждого элемента на средней производительности ноутбуке.
Оригинал данного поста Вы можете найти по ссылке [2].
Автор: ua-hosting.company
Источник [3]
Сайт-источник PVSM.RU: https://www.pvsm.ru
Путь до страницы источника: https://www.pvsm.ru/c-3/117826
Ссылки в тексте:
[1] MurmurHash3: https://github.com/aappleby/smhasher
[2] ссылке: http://blog.michaelschmatz.com/2016/04/11/how-to-write-a-bloom-filter-cpp/
[3] Источник: https://habrahabr.ru/post/281517/
Нажмите здесь для печати.