Rivalry2

HTML Diff

1 added 1 removed

Original 2026-01-01

Modified 2026-03-10

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

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

3 <h2>Для начала: какую же задачу мы решаем?</h2>

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

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

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

7 <h2>Что же делать?</h2>

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

9 <p>Но в данном случае нам даже не нужна сама запись, то есть наши данные, нам просто нужно ответить на вопрос, есть данные или нет. А сами значения наших "ключей" хранить расточительно, потому что они занимают много места.</p>

10 <h2>Как же хранить наши "ключи"?</h2>

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

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

12 + <p><strong>Разве в этом подходе нет проблемы? Ведь хэш-функции будут давать коллизии</strong>. Да, при поиске могут быть ложные срабатывания из-за коллизий, но это нас устраивает. Если элемент "скорее всего есть" в нашем импровизированном индексе, то мы запустим "честный поиск" при помощи Spark или чего-то подобного. Но обычно более вероятна ситуация, к��гда элемента нет. Хоть у нас и большое хранилище, но там есть далеко не все возможные элементы. А наша структура данных гарантированно верно будет утверждать, что элемента нет. Ведь иначе бы хэш-функция дала бы существующее у нас значение.</p>

13 <h2>Всё? Задача решена?</h2>

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

15 <h2>Улучшим нашу структуру данных</h2>

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

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

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

19 <h2>Что же фильтрует фильтр Блума?</h2>

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