Вычисление правильного количества битов в фильтре Блума - PullRequest
Новая
       13

Вычисление правильного количества битов в фильтре Блума

1 голос
/ 07 февраля 2012

Я пытаюсь сделать настраиваемый фильтр Блума. В конструкторе вы устанавливаете прогнозируемую необходимую емкость фильтра (n), желаемую частоту появления ошибок (p) и список хеш-функций (размером k).

Согласно Википедии , имеет место следующее соотношение (m - количество бит): 

p = (1 - k * n / m) ** k

Поскольку я получаю p, n и k в качестве параметров, мне нужно найти для m; Я получаю следующее: 

m = k * n / (1 - p ** (1 / k))

Однако есть несколько вещей, которые заставляют меня думать, что я сделал что-то не так. Для начала, p ** (1 / k) будет стремиться к 1 для достаточно большого k, что означает, что вся фракция плохо определена (потому что вы можете предположительно разделить на 0).

Еще одна вещь, которую вы можете заметить, это то, что с ростом p (допустимая максимальная частота появления ошибок) растет и m, что полностью наоборот.

Где я ошибся?

1 Ответ

4 голосов
/ 07 февраля 2012

Вы действительно решили уравнение правильно, однако обратите внимание, что Википедия утверждает: 

The probability of all of them being 1, which would cause
the algorithm to erroneously claim that the element is in
the set, is often given as:

p ~= (1 - (1 - 1 / m) ** (k * n)) ** k ~= (1 - Exp(-k * n / m)) ** k

Это очень отличается от того, что вы заявили: 

p = (1 - k * n / m) ** k

Так что вы действительно хотитедля начала это 

p = (1 - (1 - 1 / m) ** (k * n)) ** k

Я решил, что это будет 

(1 - 1 / m) ** (k * n) = 1 - p ** (1 / k)
1 - 1 / m = (1 - p ** (1 / k)) ** (1 / (k * n))
m - 1 = m * (1 - p ** (1 / k)) ** (1 / (k * n))
m - m * (1 - p ** (1 / k)) ** (1 / (k * n)) = 1
m * (1 - (1 - p ** (1 / k)) ** (1 / (k * n))) = 1
m = 1 / (1 - (1 - p ** (1 / k)) ** (1 / (k * n)))
...