Как работает алгоритм HyperLogLog?

Question

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

Это было особенно интересно для меня, потому что вернуло меня в те дни, когда я видел MySQL, это значение "кардинальности" (которое я до недавнего времени всегда предполагал, что оно рассчитывается без оценки).

Итак, я знаю, как написать алгоритм в O(n), который будет вычислять, сколько уникальных элементов в массиве. Я написал это в JavaScript:

function countUniqueAlgo1(arr) {
    var Table = {};
    var numUnique = 0;
    var numDataPoints = arr.length;
    for (var j = 0; j < numDataPoints; j++) {
        var val = arr[j];
        if (Table[val] != null) {
            continue;
        }
        Table[val] = 1;
        numUnique++;
    }
    return numUnique;
}

Но проблема в том, что мой алгоритм, хотя O(n), использует много памяти (сохранение значений в Table).

Я читал эту статью о том, как подсчитать дубликаты в списке за O(n) время и используя минимальное количество памяти.

Это объясняет, что путем хеширования и подсчета битов или чего-то еще можно с определенной вероятностью оценить (при условии, что список распределен равномерно) количество уникальных элементов в списке.

Я прочитал газету, но я не могу понять это. Может ли кто-нибудь дать более понятное объяснение? Я знаю, что такое хэши, но я не понимаю, как они используются в этом алгоритме HyperLogLog.

Answer 1

Основная хитрость этого алгоритма заключается в том, что если вы, наблюдая за потоком случайных целых чисел, видите целое число, двоичное представление которого начинается с некоторого известного префикса, существует более высокая вероятность того, что мощность потока равна 2^(размер префикса),

То есть в случайном потоке целых чисел ~50% чисел (в двоичном виде) начинается с "1", 25% начинается с "01", 12,5% начинается с "001". Это означает, что если вы наблюдаете случайный поток и видите "001", есть большая вероятность того, что этот поток имеет мощность 8.

(Префикс "00..1" не имеет особого значения. Он существует только потому, что в большинстве процессоров легко найти старший значащий бит двоичного числа)

Конечно, если вы наблюдаете только одно целое число, вероятность того, что это значение неверно, высока. Вот почему алгоритм делит поток на "m" независимых подпотоков и сохраняет максимальную длину кажущегося префикса "00...1" каждого подпотока. Затем оценивает окончательное значение, принимая среднее значение каждого подпотока.

Это основная идея этого алгоритма. Есть некоторые недостающие детали (например, поправка для низких оценочных значений), но все это хорошо написано в статье. Извините за ужасный английский.

Answer 2

HyperLogLog - это вероятностная структура данных. Он подсчитывает количество отдельных элементов в списке. Но по сравнению с простым способом сделать это (имея набор и добавляя элементы в набор), он делает это приблизительно.

Прежде чем посмотреть, как это делает алгоритм HyperLogLog, нужно понять, зачем он вам нужен. Проблема с простым способом заключается в том, что он потребляет O(distinct elements) пространства. Почему здесь присутствует большая буква O вместо просто отдельных элементов? Это потому, что элементы могут быть разных размеров. Один элемент может быть 1 другой элемент "is this big string", Поэтому, если у вас огромный список (или огромный поток элементов), это займет много памяти.

---

Вероятностный подсчет

Как можно получить разумную оценку количества уникальных элементов? Предположим, что у вас есть строка длины m который состоит из {0, 1} с равной вероятностью. Какова вероятность того, что он начнется с 0, с 2 нулями, с k нулями? это 1/2, 1/4 а также 1/2^k, Это означает, что если вы встретили строку с k нули, вы примерно просмотрели 2^k элементы. Так что это хорошая отправная точка. Наличие списка элементов, которые равномерно распределены между 0 а также 2^k - 1 Вы можете посчитать максимальное количество наибольшего префикса нулей в двоичном представлении, и это даст вам разумную оценку.

Проблема в том, что предположение о равномерно распределенных числах от 0 T 2^k-1 слишком сложно получить (данные, с которыми мы сталкиваемся, в основном не являются числами, почти никогда не распределяются равномерно, и могут быть между любыми значениями. Но, используя хорошую функцию хеширования, можно предположить, что выходные биты будут распределены равномерно, а большинство функций хеширования имеют выходы между 0 а также 2^k - 1 ( SHA1 дает вам значения между 0 а также 2^160). Итак, мы достигли того, что можем оценить количество уникальных элементов с максимальной мощностью k биты, сохраняя только одно число размера log(k) биты. Недостатком является то, что у нас есть огромная разница в нашей оценке. Классная вещь, что мы почти создали вероятностную счетную бумагу 1984 года (с оценкой она немного умнее, но мы все еще близки).

LogLog

Прежде чем двигаться дальше, мы должны понять, почему наша первая оценка не настолько велика. Причина этого в том, что одно случайное появление высокочастотного 0-префиксного элемента может все испортить. Один из способов улучшить это - использовать множество хеш-функций, рассчитывать max для каждой из хеш-функций и в итоге усреднять их. Это отличная идея, которая улучшит оценку, но в статье LogLog использовался немного другой подход (возможно, потому что хеширование довольно дорогое).

Они использовали один хеш, но разделили его на две части. Один называется ведром (общее количество ведер 2^x) и еще один - в основном такой же, как наш хеш. Мне было трудно понять, что происходит, поэтому я приведу пример. Предположим, у вас есть два элемента и ваша хеш-функция, которая дает форму значений 0 в 2^10 производится 2 значения: 344 а также 387, Вы решили иметь 16 ведер. Так что у тебя есть:

0101 011000  bucket 5 will store 1
0110 000011  bucket 6 will store 4

Имея больше сегментов, вы уменьшаете дисперсию (вы используете немного больше места, но она все еще крошечная). Используя математические навыки, они смогли количественно определить ошибку (которая 1.3/sqrt(number of buckets)).

HyperLogLog

HyperLogLog не вводит никаких новых идей, но в основном использует много математики для улучшения предыдущей оценки. Исследователи обнаружили, что если вы удалите 30% самых больших чисел из сегментов, вы значительно улучшите оценку. Они также использовали другой алгоритм для усреднения чисел. Бумага тяжелая математика.

---

И я хочу закончить с недавней статьей, в которой показана улучшенная версия алгоритма hyperLogLog (до сих пор у меня не было времени, чтобы полностью понять его, но, возможно, позже я улучшу этот ответ).

Answer 3

Интуиция заключается в том, что если вы вводите большой набор случайных чисел (например, хэшированные значения), они должны распределяться равномерно по всему диапазону. Допустим, диапазон составляет до 10 бит для представления значения до 1024. Затем соблюдается минимальное значение. Скажем, это 10. Тогда мощность будет около 100 (10 × 100 ≈ 1024).

Прочитайте статью для реальной логики, конечно.

Еще одно хорошее объяснение с примером кода можно найти здесь:
Чертовски крутые алгоритмы: оценка мощности - Блог Ника