Что это вообще такое?

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

В этой статье я сделаю обзор таких структур данных и расскажу, какую пользу они могут принести на практике. К базовым вероятностным структурам данных можно отнести фильтр Блума, HyperLogLog и Count-Min Sketch.

Фильтр Блума

Зачем нужен: чтобы проверить, принадлежит ли заданный элемент к множеству. Фильтр Блума довольно быстро обрабатывает большие объёмы данных и возвращает ответ в виде «нет»/«возможно». Стоит отметить, что фильтр Блума широко используется при поиске слов в тексте.

Фильтр Блума представляет собой битовый массив из M элементов и k хэш-функций, каждая из которых возвращает значения в диапазоне от 0 до M-1.

Добавление элемента в множество происходит по следующему алгоритму:

1. Для нового элемента Х вычисляем все k хэш-функций

2. Берём получившиеся значения h₁, h₂, …, h_k и устанавливаем биты с этими номерами в 1

Второй операцией, которую поддерживает фильтр Блума, является проверка, входит ли заданный элемент в множество: для этого достаточно просто посчитать хэш-суммы и проверить, что все биты равны 1. Однако необходимо помнить, что это возможно и в случае коллизий или когда все элементы фильтра равны 1 (в таком случае стоит увеличить размер массива).

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

• Apache HBase задействует фильтры Блума для оптимизации доступа по ключу.

• CloudFlare использует их для анализа спуфинга IP-адресов.

• В PostgreSQL фильтр Блума доступен в модуле bloom.

HyperLogLog

Зачем нужен: помогает оценить количество уникальных элементов в больших наборах данных, при этом оценка множества в 10⁹ элементов при использовании ~1.5 КБ памяти имеет погрешность около 2%.

HyperLogLog основан на двух математических фактах:

1. У «хороших» хэш-функций значения распределены равномерно.

2. В случайном потоке двоичных чисел фиксированной длины (например, 32 или 64-битных чисел) суффикс из нулей длины k встречается в среднем раз в 2^k элементов: поскольку вероятность встретить ноль на каждой позиции равна ½, вероятность встретить k нулей будет равна (½)^k.

Теперь мы можем построить простой эстиматор: для каждого элемента множества посчитаем хэш и запомним длину максимального нулевого суффикса k. Тогда в нашем множестве будет примерно 2^k элементов.

В реальности такая оценка нам не понравится – между 2³⁰ и 2³¹ довольно большая разница, да и закон больших чисел нам говорит, что если ждать достаточно долго, то можно встретить суффикс любого размера.

Для того чтобы сделать более точную оценку, можно взять m независимых хэш-функций, затем для каждого элемента подсчитать длины нулевых суффиксов R₁,R₂,...,R_N и усреднить результат:

Так как считать значения хэш-функций для каждого элемента дорого и элементов в множестве много, то в LogLog (пока что без Hyper) придумали такой трюк: давайте откусим первые M бит у хэша и назовём их номером нашей хэш-функции, а оставшаяся часть будет хэшем. Тогда достаточно посчитать всего 1 хэш, а точность не изменится.

В качестве последнего шага авторы HyperLogLog предлагают использовать гармоническое среднее и добавить множитель для поправки, чтобы увеличить точность:

Где HyperLogLog можно встретить в реальной жизни:

• Presto и многие другие движки для обработки больших объёмов данных используют HyperLogLog для примерной оценки количества элементов, что требует гораздо меньше памяти по сравнению с COUNT(DISTINCT)

• модуль HyperLogLog есть в системе управления базами данных Redis

Count-Min Sketch

Зачем нужен: используется для приближенного подсчёта частоты элементов в потоке данных. Эта структура данных представляет поток данных в компактном виде, тем самым позволяя ему быстро отвечать на запросы о частоте встречаемости элементов. Count-Min Sketch задействуется в различных областях: от машинного обучения до обработки естественного языка.

Как и две предыдущие структуры данных, Count-Min Sketch использует несколько (D) хэш функций, для каждой из которых заводится массив счетчиков длины W:

Затем для каждого входящего элемента вычисляются D хэшей h₁,h₂,...,h_D, соответствующие позициям в массивах, после чего счётчики в каждом массиве увеличиваются на 1.

При запросе частоты встречаемости элемента процесс повторяется – вычисляются D хэшей, а частота вычисляется как min(f₁, …, f_D), чтобы избежать коллизий.

Основная идея Count-Min Sketch заключается в том, что он хранит только минимальное количество элементов, которое необходимо для подсчёта частоты каждого элемента.

Где это используется на практике:

• в приложениях по анализу сетевого трафика, частотности слов или обработке событий;

• в Redis