Что такое фильтр Блума?

Мы говорим о не очень распространенной структуре данных, но у нее есть интересные случаи использования, и это также хороший вариант, когда мы хотим уменьшить использование памяти. Поскольку это фильтр, ожидаемый ответ — хранится ли то, о чем я спрашиваю, в наших системах или нет.

Исходя из этого, мы должны знать, что это вероятностная структура с двумя возможными исходами, а именно:

  • Конечно, нет ❌
  • Скорее всего, да 🤞

Если он говорит «нет», это означает, что его там нет, и это точно, но он не может гарантировать, что он есть, поэтому, если ответ, вероятно, «да», нам придется убедиться в этом, отправившись на проверку во второй раз, но в другое место, а не в фильтр. Это может произойти из-за коллизий в хэш-функциях, а также потому, что при уменьшении объема памяти коллизии будут присутствовать.

Теперь мы видим, как это работает

Мы говорили о вероятностях, хэшах, коллизиях и так далее, давайте объясним на конкретном примере.

Предположим, что dev.to не хочет рекомендовать пост, который вы читали в последнее время, поэтому мы собираемся загружать посты, видимые в фильтре, определенным образом, который мы сейчас подробно объясним.

Для нашего фильтра мы будем использовать массив (slice, если вы суслик) с известным нам числом, в данном случае 100, чтобы он не рос беспорядочно, поскольку основная идея заключается в том, чтобы сохранить низкое использование памяти. Мы используем bool для обозначения 0 и 1.
Каждая хэш-функция (мы можем использовать несколько, я настоятельно рекомендую использовать более одной) вернет целое число в качестве результата, а каждая запись будет представлена n числами, т.е. n — это количество хэш-функций, которые мы используем. Затем все результаты будут переведены в этот же индекс, он будет установлен в true. Например, если у нас есть срез 10 bool и три функции возвращают 2, 3 и 6, мы получим что-то вроде этого:

Тогда…

var filter [100] bool //100 para tener una buena distribución
Войдите в полноэкранный режим Выход из полноэкранного режима

Теперь хэш-функции

var h1 = func(i interface{}) int{...}
var h2 = func(i interface{}) int{...}
var h3 = func(i interface{}) int{...}
Войдите в полноэкранный режим Выход из полноэкранного режима

Несмотря на то, что они являются заполнителями, идея заключается в том, чтобы взять любое значение и вернуть целое число, которое находится в пределах диапазона, поэтому мы будем применять оператор modulo к ответу. Какую бы реализацию мы ни использовали, мы должны знать, что результат должен быть всегда одинаковым для одного и того же входа, как чисто детерминированная функция.

index1 := h1("dev.to/post-x") % 100
index2 := h2("dev.to/post-y") % 100
index3 := h3("dev.to/post-z") % 100

filter[index1] = true
filter[index2] = true
filter[index3] = true
Войдите в полноэкранный режим Выход из полноэкранного режима

Таким образом, мы решили, как написать фильтр bloom, для чтения, в принципе, все то же самое, но мы должны спросить, являются ли индексы true, и здесь мы имеем, как мы можем изучить ответы, которые мы видели ранее.

Если любой из индексов ложный, мы знаем, что URL, который мы отправили, не находится в нашем фильтре.

Если все индексы верны, мы говорим, что, вероятно, да, потому что, поскольку у нас «маленький» массив и хэш-функции имеют коллизии, возможно, другой URL сгенерировал те же числа или что-то более простое, как в этом примере:
Урл 1 дает нам результат 1, 3 и 6.
Урл 2 дает нам результат 2, 5 и 7
url 3 дает нам результат 2, 3 и 7 -> он дает нам, что все они истинны, но сам url 3, не был сохранен, поэтому во второй проверке (может быть базы данных) дает нам, что его не было.

Заключение

Блум-фильтр — хороший вариант, когда мы хотим сэкономить время и место. Его можно использовать как альтернативу хэшмапу или кэшу, чтобы выполнять операции в памяти и избегать выходов в сеть. Надеюсь, вы попробуете его в своих проектах!

Увидимся в следующий раз!

Оцените статью
devanswers.ru
Добавить комментарий