Фильтр Блума Ложные срабатывания

Я реализую BloomFilter и должен рассчитать количество ложных срабатываний, добавив [0, N] элементов, а затем проверяя, содержит ли фильтр (n, oo) элементы. У меня проблемы с вычислением правильного количества ложных срабатываний. В моем цикле каждый раз, когда средство requirecontains () сообщает мне, что мой фильтр содержит элемент в (n, oo), который я добавляю к ложным срабатываниям.
Но, например, когда у меня есть фильтр из 16 элементов, я получаю 10 ложных срабатываний, а уровень ложных срабатываний равен 0.

Любая помощь будет оценена

for (int numNotInFilter =size+1; numNotInFilter<2*size; numNotInFilter++)
{
if (myBloom.possiblyContains((const uint8_t*)(&numNotInFilter), sizeof(int)))
{
numOfFalsePositives+=1.0;
}
}
double RateOfFalsePositives = (numOfFalsePositives) / ((2 * size) - 1);

1

Решение

Я использовал эту библиотеку в прошлом, когда имел дело с фильтры цветения Вот пример, где вычисляются встречные ложные срабатывания:

https://github.com/ArashPartow/bloom/blob/master/bloom_filter_example02.cpp

Из того, что я могу сказать о том, что происходит в примере, уровень вероятности ложных срабатываний не только основан на количестве встреченных ложных срабатываний, но также является функцией размера фильтра Блума.

1

Другие решения

Других решений пока нет …

По вопросам рекламы ammmcru@yandex.ru
Adblock
detector