Вычисление приблизительной популяции фильтра bloom

Даны фильтр Блюма размером N бит и K хэш-функций, из которых M бит (где M <= N) фильтра заданы.

Можно ли приблизительно определить количество элементов, вставляемых в фильтр Блюма?

Простой пример

Я размышлял над следующим примером, предполагающим BF размером 100 бит и 5 хэш-функций, из которых 10 бит установлены...

Наилучший сценарий: Если предположить, что хэш-функции действительно совершенны и однозначно отображают бит на некоторое X-число значений, то, учитывая, что было установлено 10 бит, можно сказать, что в БФ было вставлено только 2 элемента

Худший сценарий: Если предположить, что хэш-функции плохие и последовательно отображают один и тот же бит (но при этом уникальны между собой), то можно сказать, что в BF было вставлено 10 элементов

Диапазон, похоже, [2,10], где примерно в этом диапазоне, вероятно, определяется вероятностью ложного срабатывания фильтра - я застрял на этом моменте.

7
задан Xander Tulip 2 February 2012 в 04:31
поделиться