amarao (amarao_san) wrote,
amarao
amarao_san

ещё о задаче

Я хочу уменьшить размер данных в блуме так, чтобы вероятность ошибки не возрасла. В замен я готов пожертвовать появлением false negatives, т.е. ответом "такого хэша нет", в то время, когда он есть.

Делается это просто. Мы отрезаем у хеша последний... Допустим, бит. Тогда у равномерно распределеных хэшей у нас получается примерно 50% битых на 1 бит хешей.

При этом умешьнается ли у нас число элементов для добавления в фильтр? Крайне маловероятно, для этого хеши должны различаться на 1 бит.

Сформулируем задачу так: для массива данных с размером n бит и числом элементов m нам надо придумать хэш-функцию, которая даст нам x% коллизий.

Т.к. часть элементов будет иметь коллизию, то общее число уникальных элементов станет меньше, т.е. процент false positive станет меньше. Или не станет?

Если блум говорит "видел", то он бракует сразу же оба варианта с коллизией (для удобства размышления я предполагаю процент равным 50).

Получается, Блум с false negative имеет такой же уровень false positive, как и без "ухудшатора". . .
Subscribe

  • Post a new comment

    Error

    default userpic

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 14 comments