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

В: Я только что прочитал о существовании структуры данных под названием фильтр Блума, для чего ее можно использовать

Фильтр Блума можно использовать для эффективного решения проблемы Set Presence.

В. В чем заключается проблема "Установить присутствие"

Предположим, у вас есть набор (однородных) элементов и один элемент запроса, проблема состоит в том, чтобы проверить, присутствует ли элемент запроса в Set

В: Это кажется простым, я просто переберу все элементы в наборе и сравню элемент запроса с i-м элементом, зачем мне для этого нужна особая структура данных

Да, вы, безусловно, можете решить эту проблему, перебирая все элементы в наборе, но это не очень эффективно, поскольку это O (N).
Было бы лучше выбрать что-то, что лучше масштабируется с N = количество элементов в наборе, например O (logN) или O (1)

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

Что ж, это зависит от того, что вы можете предположить о типе элементов в наборе, например, если вы можете предположить, что они доступны для заказа, тогда вы можете решить проблему за O (logN)

В: Как такое свойство, как возможность заказа, приводит к такому улучшению?

Предположим, вы сохраняете свой набор упорядоченным.
Как только вы получите элемент запроса Q, сравните его со средним элементом M: если Q = M, то вы его нашли, если Q ‹M, то ваше пространство поиска становится подмножеством всех элементов меньше M, иначе он станет дополнительным

Это свойство приведет к рекурсивному решению, которое на каждом шаге уменьшает размер области поиска вдвое.
Рекурсия завершится: 1) когда соблюден равный случай и в этом случае элемент запроса присутствует, или 2) когда область поиска пуста и в этом случае элемент запроса отсутствует

Для перехода к случаю 2 потребуется до O (logN), следовательно, его временная сложность составляет O (logN).

В: Хорошо, порядок дает вам возможность разделить пространство поиска пополам и иметь O (logN), но как получить O (1)

Чтобы получить O (1) Search, требуется другое предположение: тип должен быть хешируемым.

Если вы предполагаете, что функция хеширования H: E → I (сопоставление элемента типа E с целым числом) существует, вы можете преобразовать каждый элемент в индекс массива, следовательно, поиск будет O (1)

В: Великолепно, это фильтр Блума?

Не совсем так: вышеупомянутая структура данных - это HashSet, она решит проблему Set Presence детерминированным способом (вплоть до Hash Collisions, но мы займемся этим позже, пока давайте не будем рассматривать хэш-коллизии), в то время как Bloom Filter will - это вероятностная структура данных.
Это означает, что это не гарантирует, что элемент присутствует на 100%, скорее всего, он присутствует.

В: Звучит странно, для чего нужна такая структура данных

Опять же, все сводится к эффективности: фильтр Блума более эффективен, чем HashSet, конечно, не с точки зрения временной сложности, поскольку они оба являются O (1), потому что они оба полагаются на хеширование, а с точки зрения космической сложности как фильтр Блума. очень компактный.

В: Я думал, что стоимость места составляет всего N * sizeof (E), не так ли?

Это зависит от типа структуры данных, которую вы используете, и, в конечном итоге, от конечной цели:

  • если 1) вы должны сохранить элемент и 2) также хотите проверить наличие элементов, то 1 явно требует, чтобы вы сохранили его, но
  • если вы просто хотите решить проблему «Установить присутствие», без фактического хранения элемента, вам разрешается использовать более экономичные представления

Кроме того, говоря о стоимости места, помимо очевидного размера следует учитывать еще один аспект, а именно разреженность: редко занимаемая память может использоваться гораздо менее эффективно, чем компактная.

HashSet O (1) во времени и детерминированном поиске происходит за счет использования разреженной памяти. Bloom Filter использует гораздо более компактный и экономичный объем памяти, но это достигается за счет вероятностного результата.

В: Но не мешает ли эта вероятностная природа его практическому использованию?

Прежде всего, лучше уточнить, что результат фильтра Блума является вероятностным, когда он положительный (элемент найден), но не когда он отрицательный (элемент не найден): это означает, что результат «элемент не найден» гарантированно будет на 100% правильным, в то время как результат «элемент найден» p

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