Фильтр Блума
Фильтр Блума
Фильтр Блума – вероятностная структура данных, которая позволяет компактно хранить информацию о принадлежности элемента множеству. Фильтр отличает возможность ложноположительного срабатывания, но не ложноотрицательного (ложноположительное срабатывание – это когда фильтр говорит, что элемент в множестве, но его там нет. Ложноотрицательное, когда фильтр говорит, что элемента в множестве нет, но он там присутствует). Для нас фильтр интересен, в первую очередь, как тренировка работы с отдельными битами на языке си.
Фильтр Блума представляет собой битовое поле, например, длиной в 4 байта. Добавление элемента в фильтр происходит следующим образом – для значения высчитывается несколько разных хэшей, после чего выставляются соответствующие биты в битовом поле. Проверка на вхождение осуществляется похоже – сначала высчитываются хэши для значения, после чего проверяется, выставлены ли соответствующие биты. Так как разные значения могут иметь одинаковые хэш-коды, то возможны ложноположительные срабатывания. Но если хэш-коды разные, то однозначно, значения тоже разные, так что ложноотрицательного срабатывания быть не может.
Пример. Будем фильтровать строки. Пусть наш фильтр состоит из 16 бит и работает всего с двумя хэш-функциями.
Мы добавляем строку “Elephant”, первая функция даёт хэш код, равный 25425, а вторая 894346520. Всего у нас 16 бит, так что находим значения по модулю 16. Итого, первый хэш 1, а второй 8. Выставляем соответствующие биты.
Теперь мы хотим добавить строку “Hokkey”, первый хэш равен 8, а второй 7, выставляем соответствующие биты.
Из рисунка видно, что пересеклись биты под номером 8 двух строк, так что удалить одну из строк из фильтра просто теперь не получится. Для удаления одного значения придётся пересчитать хэши всех других значений до тех пор, пока хотя бы одно из значений не даст те же биты, либо пока не пересчитаем все значения.
Пусть теперь мы хотим узнать, проходит ли строка “Okorok” фильтр. Высчитаем для неё хэши, пусть они равны 3 и 7. Бит 3 не выставлен (равен нулю), так что, однозначно, эта строка не входит в фильтр. Между тем, хэши строки “Zigmund” имеют значения 1 и 8, хотя данного значения в фильтре нет.
Небольшой вывод: фильтр позволяет добавлять новые значения, но удалять их затратно. Чем больше битовое поле фильтра, тем выше вероятность «хорошей» работы (вероятность ложного положительного срабатывания падает). Когда все биты фильтра равны нулю, очевидно, ни одно из значений не добавлено, и ни одно из значения не сможет пройти фильтр. Когда все биты выставлены, то фильтр пропускает все значения.
Фильтр Блума применяется достаточно редко, в основном в качестве первоначального фильтра в системах кэширования (кэширующие прокси-сервера, кэширование в браузерах, системах оплаты), также фильтры используются для быстрой оценки "похожести" множеств, их пересечения и объединения.
Для начала, следует определить функции, которые будут работать с отдельными битами.
Для того, чтобы выставить k-й бит, следует произвести логическое сложение этого бита с единицей. Чтобы получить один бит на k-й позиции, можно сдвинуть единицу на k позиций влево. Таким образом, получаем
byte = byte | (1 << k)
Поле фильтра может иметь произвольную длину в байтах. Операция сдвига работает с отдельным регистром, так что, например, на 32-разрядной машине не получится произвести сдвиг на 55 бит, максимум на 31.
Реализуем, в ущерб производительности, размер поля кратным одному байту. Таким образом, операции работы с отдельными битами будем проводить с помощью переменной типа char. Для доступа до k-го бита сначала получим этот байт, а затем, относительно полученного байта, изменим бит.
__inline void setbit(void *field, size_t index) {
char *thebyte = NULL;
assert(field);
thebyte = (char*)field + index / CHAR_BIT;
*thebyte = *thebyte | (1 << (index % CHAR_BIT));
}
Например, поле равно 5 байтам, а мы хотим изменить 21-й бит. 21-й бит находится в 21/8 = 2 байте (индексация с нуля), номер бита равен 5.
Для того, чтобы изменить значение бита (0 на 1 и 1 на 0), следует провести операцию XOR (исключающее или) с этим битом.
__inline void togglebit(void *field, size_t index) {
char *thebyte = NULL;
assert(field);
thebyte = (char*)field + index / CHAR_BIT;
*thebyte = *thebyte ^ (1 << (index % CHAR_BIT));
}
Функция обнуления бита.
__inline void unsetbit(void *field, size_t index) {
char *thebyte = NULL;
assert(field);
thebyte = (char*)field + index / CHAR_BIT;
*thebyte = *thebyte & ~(1 << (index % CHAR_BIT));
}
Для проверки n-го бита умножим этот бит на 1. Чтобы получить конкретно это бит, придётся сдвинуть его в самое начало байта.
__inline unsigned checkbit(const void* field, size_t index) {
char *thebyte = NULL;
assert(field);
thebyte = (char*)field + index / CHAR_BIT;
return (*thebyte >> (index % CHAR_BIT)) & 1;
}
Результатом работы этой функции будет либо 0, либо 1. Можно, конечно, сдвигать единицу до нужного бита, но в этом случае, результатами будут положительные числа 1, 2, 4, 8 и т.д.
Функция cntsetbits считает все биты, равные 1
__inline unsigned cntsetbits(void *field, size_t size) {
char t;
size_t i, j;
unsigned counter = 0;
assert(field);
for (i = 0; i < size; i++) {
t = *((char*) field + i);
for (j = 0; j < CHAR_BIT; j++) {
if (1 & (t >> j)) {
counter++;
}
}
}
return counter;
}
Вспомогательная функция, которая выводи все биты поля
void printbits(void *field, size_t size) {
size_t i, j;
char t;
assert(field);
for (i = 0; i < size; i++) {
t = *((char*)field + i);
for (j = 0; j < CHAR_BIT; j++) {
printf("%d", (t >> j) & 1);
}
}
printf("\n");
}
Теперь сам фильтр
#define DEBUG
#ifdef DEBUG
#define debug(msg, ...) fprintf(stdout, msg, __VA_ARGS__);
#else
#define debug
#endif
typedef enum Errors {
OUT_OF_MEMORY = 1
} Errors;
const char* errors[] = {
"OK",
"OUT_OF_MEMORY"
};
typedef struct BloomFilter {
void *bitfield;
size_t size; //num of bits
size_t bytesize; //num of bytes
unsigned inserted;
} BloomFilter;
Здесь будет два поля “размер”. Одно поле хранит размер в байтах, а другое в битах. Поле inserted хранит число добавленных в фильтр значений.
Функция, которая создаёт фильтр
BloomFilter* createBloomFilter(size_t fieldsize) {
BloomFilter *tmp = (BloomFilter*)malloc(sizeof(BloomFilter));
if (!tmp) {
debug("createBloomFilter:: can't allocate memory for filter");
exit(OUT_OF_MEMORY);
}
tmp->bitfield = malloc(fieldsize);
if (!tmp->bitfield) {
debug("createBloomFilter:: can't allocate memory for filter->bitfield");
exit(OUT_OF_MEMORY);
}
memset(tmp->bitfield, 0, fieldsize);
tmp->size = fieldsize * CHAR_BIT;
tmp->bytesize = fieldsize;
tmp->inserted = 0;
return tmp;
}
И удаление
void deleteBloomFilter(BloomFilter **filter) {
assert(*filter);
free((*filter)->bitfield);
free(*filter);
*filter = NULL;
}
Для нахождения хэшей воспользуемся murmur и fnv хэш-функциями. Качество реализации и их внутреннее устройство опустим.
#define mmix(h,k) { k *= m; k ^= k >> r; k *= m; h *= m; h ^= k; }
uint32_t MurmurHash2A(const void * key, int len, uint32_t seed) {
const uint32_t m = 0x5bd1e995;
const int r = 24;
uint32_t l = len;
uint32_t t = 0;
const unsigned char * data = (const unsigned char *)key;
uint32_t h = seed;
while (len >= 4) {
uint32_t k = *(uint32_t*)data;
mmix(h, k);
data += 4;
len -= 4;
}
switch (len) {
case 3: t ^= data[2] << 16;
case 2: t ^= data[1] << 8;
case 1: t ^= data[0];
};
mmix(h, t);
mmix(h, l);
h ^= h >> 13;
h *= m;
h ^= h >> 15;
return h;
}
#define FNV_PRIME_32 16777619
#define FNV_OFFSET_32 2166136261U
uint32_t FNV32(const void *s, size_t size)
{
uint32_t hash = FNV_OFFSET_32, i;
for (i = 0; i < size; i++) {
hash = hash ^ (*((char*)s + i));
hash = hash * FNV_PRIME_32;
}
return hash;
}
Замечание: это неполная реализация murmur. Полную реализацию смотри здесь.
Для нахождения нескольких хэшей определим функцию, находящую сразу массив кодов. В нашем случае длина массива будет два
#define HASH_QTY 2
__inline void gethashes(const void *value, size_t fieldsize, const size_t size, unsigned *out) {
//suppose number of hashes known and equals to HASH_QTY
out[0] = MurmurHash2A(value, size, 0) % fieldsize;
out[1] = FNV32(value, size) % fieldsize;
}
Добавление значения в фильтр
void addValueToFilter(BloomFilter *filter, const void *value, size_t size) {
unsigned hashes[HASH_QTY];
size_t i;
assert(filter);
assert(value);
gethashes(value, filter->size, size, hashes);
for (i = 0; i < HASH_QTY; i++) {
setbit(filter->bitfield, hashes[i]);
}
filter->inserted++;
}
И фильтрация
int filter(BloomFilter *filter, void *value, size_t size) {
unsigned hashes[HASH_QTY];
assert(filter);
assert(value);
gethashes(value, filter->size, size, hashes);
return checkbits(filter->bitfield, hashes, HASH_QTY);
}
Здесь используется вспомогательная функция checkbits, которая проверяет сразу несколько битов
__inline unsigned checkbits(const void *field, const size_t *indexes, size_t size) {
size_t i;
assert(field);
for (i = 0; i < size; i++) {
if (!checkbit(field, indexes[i])) {
return 0;
}
}
return 1;
}
Для подсчёта вероятности ложного положительного срабатывания можно воспользоваться функцией
__inline double getFalsePosProb(BloomFilter *filter) {
return pow((1.0 - exp(-HASH_QTY * (double)(filter->inserted) / (double)filter->size)), HASH_QTY)*100.0;
}
Как показано в какой-то научной работе, которую можно найти в какой-нибудь публичной онлайн-энциклопедии, оценить число элементов в фильтре можно по следующей формуле
double approxNumOfItems(BloomFilter *filter) {
double ones = (double)cntsetbits(filter->bitfield, filter->bytesize);
return -(double)filter->size * log(1 - ones / (double)filter->size) / HASH_QTY;
}
Пример использования
void main() {
double prob;
BloomFilter *f = createBloomFilter(1024);
char *values[] = {
"Holland",
"Russia",
"Canada"
};
addValueToFilter(f, values[0], strlen(values[0]));
printbits(f->bitfield, 4);
printf("if contains 'Holland' = %d\n", filter(f, "Holland", strlen("Holland")));
printf("false positive probability = %.3%%f\n", getFalsePosProb(f));
printf("estimated num of items = %.3f\n", approxNumOfItems(f));
addValueToFilter(f, values[1], strlen(values[1]));
printbits(f->bitfield, 4);
printf("if contains 'Russia' = %d\n", filter(f, "Russia", strlen("Russia")));
printf("false positive probability = %.3%%f\n", getFalsePosProb(f));
printf("estimated num of items = %.3f\n", approxNumOfItems(f));
addValueToFilter(f, values[2], strlen(values[2]));
printbits(f->bitfield, 4);
printf("if contains 'China' = %d\n", filter(f, "China", strlen("China")));
printf("false positive probability = %.3%%f\n", getFalsePosProb(f));
printf("estimated num of items = %.3f\n", approxNumOfItems(f));
deleteBloomFilter(&f);
_getch();
}
