Что это вообще такое?
Под этим термином понимаются такие структуры данных или алгоритмы, результатом которых является не детерминированное «да» или «нет», а вероятностные ответы, например, «точно нет» и «возможно». Как правило, такие структуры позволяют существенно сэкономить вычислительные ресурсы в задачах, где допустимо получить примерный ответ.
В этой статье я сделаю обзор таких структур данных и расскажу, какую пользу они могут принести на практике. К базовым вероятностным структурам данных можно отнести фильтр Блума, HyperLogLog и Count-Min Sketch.
Фильтр Блума
Зачем нужен: чтобы проверить, принадлежит ли заданный элемент к множеству. Фильтр Блума довольно быстро обрабатывает большие объёмы данных и возвращает ответ в виде «нет»/«возможно». Стоит отметить, что фильтр Блума широко используется при поиске слов в тексте.
Фильтр Блума представляет собой битовый массив из M элементов и k хэш-функций, каждая из которых возвращает значения в диапазоне от 0 до M-1.
Добавление элемента в множество происходит по следующему алгоритму:
Для нового элемента Х вычисляем все k хэш-функций
Берём получившиеся значения h1, h2, …, hk и устанавливаем биты с этими номерами в 1
Второй операцией, которую поддерживает фильтр Блума, является проверка, входит ли заданный элемент в множество: для этого достаточно просто посчитать хэш-суммы и проверить, что все биты равны 1. Однако необходимо помнить, что это возможно и в случае коллизий или когда все элементы фильтра равны 1 (в таком случае стоит увеличить размер массива).
Благодаря высокой эффективности, гибкости и скорости работы фильтры Блума довольно часто используются в реальной жизни. Например:
Apache HBase задействует фильтры Блума для оптимизации доступа по ключу.
В PostgreSQL фильтр Блума доступен в модуле bloom.
HyperLogLog
Зачем нужен: помогает оценить количество уникальных элементов в больших наборах данных, при этом оценка множества в 109 элементов при использовании ~1.5 КБ памяти имеет погрешность около 2%.
HyperLogLog основан на двух математических фактах:
У «хороших» хэш-функций значения распределены равномерно.
В случайном потоке двоичных чисел фиксированной длины (например, 32 или 64-битных чисел) суффикс из нулей длины k встречается в среднем раз в 2k элементов: поскольку вероятность встретить ноль на каждой позиции равна ½, вероятность встретить k нулей будет равна (½)k.
Теперь мы можем построить простой эстиматор: для каждого элемента множества посчитаем хэш и запомним длину максимального нулевого суффикса k. Тогда в нашем множестве будет примерно 2k элементов.
В реальности такая оценка нам не понравится – между 230 и 231 довольно большая разница, да и закон больших чисел нам говорит, что если ждать достаточно долго, то можно встретить суффикс любого размера.
Для того чтобы сделать более точную оценку, можно взять m независимых хэш-функций, затем для каждого элемента подсчитать длины нулевых суффиксов R1,R2,...,RN и усреднить результат:
Так как считать значения хэш-функций для каждого элемента дорого и элементов в множестве много, то в LogLog (пока что без Hyper) придумали такой трюк: давайте откусим первые M бит у хэша и назовём их номером нашей хэш-функции, а оставшаяся часть будет хэшем. Тогда достаточно посчитать всего 1 хэш, а точность не изменится.
В качестве последнего шага авторы HyperLogLog предлагают использовать гармоническое среднее и добавить множитель для поправки, чтобы увеличить точность:
Где HyperLogLog можно встретить в реальной жизни:
Presto и многие другие движки для обработки больших объёмов данных используют HyperLogLog для примерной оценки количества элементов, что требует гораздо меньше памяти по сравнению с COUNT(DISTINCT)
модуль HyperLogLog есть в системе управления базами данных Redis
Count-Min Sketch
Зачем нужен: используется для приближенного подсчёта частоты элементов в потоке данных. Эта структура данных представляет поток данных в компактном виде, тем самым позволяя ему быстро отвечать на запросы о частоте встречаемости элементов. Count-Min Sketch задействуется в различных областях: от машинного обучения до обработки естественного языка.
Как и две предыдущие структуры данных, Count-Min Sketch использует несколько (D) хэш функций, для каждой из которых заводится массив счетчиков длины W:
Затем для каждого входящего элемента вычисляются D хэшей h1,h2,...,hD, соответствующие позициям в массивах, после чего счётчики в каждом массиве увеличиваются на 1.
При запросе частоты встречаемости элемента процесс повторяется – вычисляются D хэшей, а частота вычисляется как min(f1, …, fD), чтобы избежать коллизий.
Основная идея Count-Min Sketch заключается в том, что он хранит только минимальное количество элементов, которое необходимо для подсчёта частоты каждого элемента.
Где это используется на практике:
в приложениях по анализу сетевого трафика, частотности слов или обработке событий;
