Просто о сложном: что фильтрует фильтр Блума? | OTUS

Курсы

Курсы в разработке Подготовительные курсы
Работа в компаниях Компаниям Блог +7 499 110-61-65

Просто о сложном: что фильтрует фильтр Блума?

Algo_Deep_2.10-5020-9475ea.png

Многие разработчики, особенно начинающие, интересуются, что же это такое — фильтр Блума? О чём может спросить Яндекс на собеседовании и о чём знают разработчики BigData? Если вы начнёте изучение предмета со статьи в Википедии, скорее всего, вы испуганно отшатнётесь при виде логарифмов, вероятностей и прочих непонятных слов.

В нашем курсе мы подробно и понятно рассматриваем фильтр Блума путём последовательных приближений к оптимальному решению нашей задачи, начиная с самого простого и неэффективного варианта решения и улучшая его. Ведь самое лучшее решение — решение, которое студент находит самостоятельно. А пока набросаем некоторые мысли, которые помогут нам приблизиться к решению задачи на интуитивном уровне, без строгих объяснений.

Для начала: какую же задачу мы решаем?

Необходимо определить, принадлежит ли элемент множеству или не принадлежит. Дело осложняется тем, что множества могут быть очень большими, не помещающимися не только в оперативную память, но даже на диск одного компьютера.

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

Как решить эту задачу? Мы можем проитерироваться по нашему огромному датасету (последовательно перебрать все его элементы) и сравнить каждый его элемент с заданным. Это может занять очень продолжительное время, ведь датасет у нас большой (даже если мы используем техники параллельной обработки данных MapReduce или Spark). А нам хотелось бы получить ответ мгновенно. Это невозможно, скажете вы, и будете неправы.

Что же делать?

Если мы начнём думать на эту тему, в голову может прийти мысль об индексах, как в базах данных. Упрощенно говоря, они содержат сортированные ключи и указатели на соответствующие записи в БД. Ищем в таком индексе ключ и находим запись по её указателю.

Но в данном случае нам даже не нужна сама запись, то есть наши данные, нам просто нужно ответить на вопрос, есть данные или нет. А сами значения наших «ключей» хранить расточительно, потому что они занимают много места.

Как же хранить наши «ключи»?

Нужно использовать какое-то ограниченное по объёму хранилище. Сразу приходит мысль о том, чтобы пропустить все наши элементы через какую-либо хэш-функцию и записать результаты в хэш-таблицу. Так мы кардинально ограничим размер наших данных. Просто считаем хэш от каждого элемента и записываем его в таблицу по смещению «остаток от деления значения хэш-функции на размер таблицы». Всё как обычно с хэш-таблицами. Только мы не будем хранить цепочки, чтобы сэкономить место и использовать метод открытой адресации для упрощения логики работы.

Разве в этом подходе нет проблемы? Ведь хэш-функции будут давать коллизии. Да, при поиске могут быть ложные срабатывания из-за коллизий, но это нас устраивает. Если элемент «скорее всего есть» в нашем импровизированном индексе, то мы запустим «честный поиск» при помощи Spark или чего-то подобного. Но обычно более вероятна ситуация, когда элемента нет. Хоть у нас и большое хранилище, но там есть далеко не все возможные элементы. А наша структура данных гарантированно верно будет утверждать, что элемента нет. Ведь иначе бы хэш-функция дала бы существующее у нас значение.

Всё? Задача решена?

По скорости работы алгоритм нас устроит (O(1) - можно ли желать лучше?), а вот по занимаемому месту — скорее всего, нет. Ведь если задаться целью минимизировать вероятность ложноположительного срабатывания, потребуется большая хэш-таблица.

Улучшим нашу структуру данных

Как ещё более кардинально сэкономить место? И зачем нам вообще хранить значения хэшей? Приходит на ум способ лучше: битовая маска, где мы будем поднимать битик по смещению, соответствующему значению хэш-функции. Вроде всё сходится, но интуитивно понятно, что коллизий будет больше, чем в предыдущем варианте, хотя по занимаемому месту этот вариант уже подходит.

Как уменьшить влияние коллизий на точность результата?

Пойдём дальше: используем несколько хэш-функций и будем поднимать сразу несколько битиков в нашей битовой маске, соответствующих их значениям. Для проверки будем вычислять эти же хэш-функции и проверять битики. Если все битики подняты — значит, элемент у нас, возможно, есть (а может, и нету из-за «постороннего» битика). Если хотя бы один не поднят — значит, точно нет. Это и есть фильтр Блума.

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

Он отфильтровывает заведомо отсутствующие в нашем датасете значения (и пропускает через себя, возможно, присутствующие). Вы согласны? У вас есть вопросы, замечания или предложения по улучшению алгоритма? Поделитесь ими в комментариях.

Не пропустите новые полезные статьи!

Спасибо за подписку!

Мы отправили вам письмо для подтверждения вашего email.
С уважением, OTUS!

Автор
0 комментариев
Для комментирования необходимо авторизоваться