Просто о сложном: что фильтрует фильтр Блума?
Многие разработчики, особенно начинающие, интересуются, что же это такое — фильтр Блума? О чём может спросить Яндекс на собеседовании и о чём знают разработчики BigData?
В нашем курсе мы подробно и понятно рассматриваем фильтр Блума путём последовательных приближений к оптимальному решению нашей задачи, начиная с самого простого и неэффективного варианта решения и улучшая его. Ведь самое лучшее решение — решение, которое студент находит самостоятельно. А пока набросаем некоторые мысли, которые помогут нам приблизиться к решению задачи на интуитивном уровне, без строгих объяснений.
Для начала: какую же задачу мы решаем?
Необходимо определить, принадлежит ли элемент множеству или не принадлежит. Дело осложняется тем, что множества могут быть очень большими, не помещающимися не только в оперативную память, но даже на диск одного компьютера.
Предположим, что мы расположили наш огромный датасет на кластере из множества компьютеров. Нам на вход приходит какой-то элемент. Мы должны сказать, есть он у нас или его нет. Отлично.
Как решить эту задачу? Мы можем проитерироваться по нашему огромному датасету (последовательно перебрать все его элементы) и сравнить каждый его элемент с заданным. Это может занять очень продолжительное время, ведь датасет у нас большой (даже если мы используем техники параллельной обработки данных MapReduce или Spark). А нам хотелось бы получить ответ мгновенно. Это невозможно, скажете вы, и будете неправы.
Что же делать?
Если мы начнём думать на эту тему, в голову может прийти мысль об индексах, как в базах данных. Упрощенно говоря, они содержат сортированные ключи и указатели на соответствующие записи в БД. Ищем в таком индексе ключ и находим запись по её указателю.
Но в данном случае нам даже не нужна сама запись, то есть наши данные, нам просто нужно ответить на вопрос, есть данные или нет. А сами значения наших «ключей» хранить расточительно, потому что они занимают много места.
Как же хранить наши «ключи»?
Нужно использовать какое-то ограниченное по объёму хранилище. Сразу приходит мысль о том, чтобы пропустить все наши элементы через какую-либо хэш-функцию и записать результаты в хэш-таблицу. Так мы кардинально ограничим размер наших данных. Просто считаем хэш от каждого элемента и записываем его в таблицу по смещению «остаток от деления значения хэш-функции на размер таблицы». Всё как обычно с хэш-таблицами. Только мы не будем хранить цепочки, чтобы сэкономить место и использовать метод открытой адресации для упрощения логики работы.
Разве в этом подходе нет проблемы? Ведь хэш-функции будут давать коллизии. Да, при поиске могут быть ложные срабатывания из-за коллизий, но это нас устраивает. Если элемент «скорее всего есть» в нашем импровизированном индексе, то мы запустим «честный поиск» при помощи Spark или чего-то подобного. Но обычно более вероятна ситуация, когда элемента нет. Хоть у нас и большое хранилище, но там есть далеко не все возможные элементы. А наша структура данных гарантированно верно будет утверждать, что элемента нет. Ведь иначе бы хэш-функция дала бы существующее у нас значение.
Всё? Задача решена?
По скорости работы алгоритм нас устроит (O(1) - можно ли желать лучше?), а вот по занимаемому месту — скорее всего, нет. Ведь если задаться целью минимизировать вероятность ложноположительного срабатывания, потребуется большая хэш-таблица.
Улучшим нашу структуру данных
Как ещё более кардинально сэкономить место? И зачем нам вообще хранить значения хэшей? Приходит на ум способ лучше: битовая маска, где мы будем поднимать битик по смещению, соответствующему значению хэш-функции. Вроде всё сходится, но интуитивно понятно, что коллизий будет больше, чем в предыдущем варианте, хотя по занимаемому месту этот вариант уже подходит.
Как уменьшить влияние коллизий на точность результата?
Пойдём дальше: используем несколько хэш-функций и будем поднимать сразу несколько битиков в нашей битовой маске, соответствующих их значениям. Для проверки будем вычислять эти же хэш-функции и проверять битики. Если все битики подняты — значит, элемент у нас, возможно, есть (а может, и нету из-за «постороннего» битика). Если хотя бы один не поднят — значит, точно нет. Это и есть фильтр Блума.
Что же фильтрует фильтр Блума?
Он отфильтровывает заведомо отсутствующие в нашем датасете значения (и пропускает через себя, возможно, присутствующие). Вы согласны? У вас есть вопросы, замечания или предложения по улучшению алгоритма? Поделитесь ими в комментариях.
