Вероятностные структуры данных 2/2.
3. HyperLogLog используют, чтобы узнать примерное количество уникальных элементов в мультимножестве.
Тут у нас опять есть k хеш-функций, каждая из которых выдаёт значения от 0 до 2^64-1. Значение хеш-функции это какая-то последовательность из 64 нулей и единиц. Теперь немного помахаем руками. Будем считать, что наши хеш-функции "хорошие", i.e. плюс-минус равномерно распределены (хотя вообще-то мы хотим этого для всех структур). Тогда хеш равновероятно может начаться с нуля и единицы (с p=1/2). Аналогично с 01 с p=1/4, с 001 с p=1/8, 0001 — 1/16 и т.д. Т.е. если мы встретили хеш с префиксом 0000001 (а такое могло произойти только с p=1/128), то мы можем сказать, что в мультимножестве примерно 128 элементов (на больших числах конечно же). Конечно же такая оценка может легко сломаться, если нам попадётся один случайный хеш с длинным префиксом нулей. Для обхода все элементы потока делят на несколько подпотоков (например по очереди отправляют сначала в 1й, потом во 2й, в 3й и в 4й), считают максимальную длину префикса в каждом подпотоке среди всех хеш-функций (например 1, 5, 8, 3) и считают среднее гармоническое на страшные коэффициенты из тервера:
k*(2^(-1) + 2^(-5) + 2^(-8) + 2^(-3))^(-1)
Примерно столько элементов в нашем мультимножестве. Сейчас есть следующая проблема: если неаккуратно делить на подпотоки, то какой-нибудь частый элемент, дающий маленький хеш, испортит нам все подпотоки. Потому давайте номер подпотока определять по первым k битам хеша. Т.е. если у нас пришёл объект с хешом
0010|0010...01, то по первым например 4 битам мы определим, что его подпоток номер 2, а считать позицию первой единицы будем начиная с 5ого бита (в этом примере она равна 3). Если в этом подпотоке уже был элемент с единицей дальше, то просто забываем эту тройку, иначе, если это дальше, чем было до текущего момента, считаем, что 3 у нас самая далёкая. Таким образом частые элементы будут портить один и тот же подпоток.Такая структура легко мержится. Предположим у нас есть посчитанный HLL для мультимножества A (массив из n чисел, где n — кол-во подпотоков, а i-е число в нём — позиция самой правой единицы в этом подпотоке) и HLL для B, то смержить их это за O(n) посчитать максимум из двух для каждой ячейки. Соответственно HLL легко параллелится (каждый чанк мультимножества считаем независимо, а потом мержим).
Если немного покумекать-покрутить включения-исключения, можно научиться пересекать/вычитать несколько HLL.
HLL юзается в redis (или статья), или например под капотом для approx_count_distinct в других бд.
4. MinHash используется для оценки мощности пересечения множеств (например будем считать два текста похожими, если множества их слов похожи; можем не храня эти огромные тексты таким примитивным методом задетектить плагиат). Тут вводится коэффициент Жаккара:
J(A, B) = |пересечения|/|объединения|
Как это работает.Берём k хеш-функций. Считаем значения всех хеш-функций для каждого элемента множества A. Среди значений каждой хеш-функции берём минимум. Получаем массив из k элементов, каждый из которых равен минимальному значению некоторой хеш-функции на этом множестве. Повторяем то же для множества B. И теперь считаем коэффициент Жаккара двух векторов с хешами. Утверждается, что он очень хорошо приближает
J(A, B). Тут можно считать пересечение двух векторов не как множеств, а совпадение по позициям.Иногда вместо k хеш-функций берут одну, но считают k её минимальных значений. Или одну по разным простым модулям.
Ну и тут link на какие-то юзкейсы.
Вот такую магию люди придумывают, а у нас до сих пор горячую воду отключают на две недели. Мир контрастов.