LogLog — находим число уникальных элементов

Здравствуй, Хабр! Мы с тобой уже побаловались фильтрами Блума и MinHash. Сегодня разговор пойдёт о ещё одном вероятностном-рандомизированном алгоритме, который позволяет с минимальными затратами памяти определить примерное число уникальных элементов в больших объёмах данных.

Для начала, поставим себе задачу: предположим, что у нас имеется большой объём текстовых данных — скажем, плоды литературного творчества небезызвестного Шекспира, и нам необходимо подсчитать количество различных слов встречающихся в этом объёме. Типичное решение — счётчик с урезанной хеш-таблицей, где ключами будут слова без ассоциированных с ними значений.

Способ всем хорош, но требует относительно большой объём памяти для своей работы, ну а мы с вами, как известно, неугомонные гении эффективности. Зачем много, если можно мало — примерный размер словарного запаса упомянутого выше Шекспира, можно вычислить используя всего 128 байт памяти.

Как обычно нам понадобится какая-нибудь хеш-функция, соответственно на вход алгоритму будут поступать не сами данные, а их хеши. Задача хеш-функции, как это обычно и бывает в рандомизированных алгоритмах, состоит в превращении упорядоченных данных в «случайные», то-бишь в более-менее равномерном размазывании области определения по области значений. Для тестовой реализации я выбрал FNV-1a, как неплохую и простую хеш-функцию:

Ну что ж, включим мозг и посмотрим на хеши, которые она выдаёт в двоичном представлении:

fnv1a('aardvark') = 1001100000000001110100100011001 1 fnv1a('abyssinian') = 00101111000100001010001000111 100 fnv1a('accelerator') = 10111011100010100010110001010 100 fnv1a('accordion') = 0111010111000100111010000001100 1 fnv1a('account') = 00101001010011111100011101011 100 fnv1a('accountant') = 0010101001101111110011110010110 1 fnv1a('acknowledgment') = 0000101000010011100000111110 1000 fnv1a('acoustic') = 111100111010111111100101011000 10 fnv1a('acrylic') = 1101001001110011011101011101 1000 fnv1a('act') = 0010110101001010010001011000101 1

Обратим внимание на индекс первого ненулевого младшего бита для каждого хеша, прибавим к этому индексу единицу и назовём это рангом (rank(1) = 1, rank(10) = 2, . ):

Вероятность того, что мы встретим хеш с рангом 1 равна 0.5, с рангом 2 — 0.25, с рангом r — 2 -r . Иначе говоря, среди 2 r хешей обязан встретиться один хеш ранга r. Совсем иначе говоря, если запоминать наибольший обнаруженный ранг R, то 2 R сгодится в качестве грубой оценки количества уникальных элементов среди уже просмотренных.

Ну, теория вероятностей штука такая, что мы можем обнаружить большой ранг R в маленькой выборке, а можем и маленький в преогромнейшей выборке, и вообще 2 31 и 2 32 — это две большие разницы, скажите вы и будете правы, именно поэтому такая единичная оценка очень груба. Что же делать?

Можно вместо одной хеш-функции использовать пачку оных, а потом каким-то образом «усреднить» оценки полученные по каждой из них. Такой подход плох тем, что функций нам потребуется много и их все придётся считать. Поэтому сделаем следующую хитрость – будем отгрызать k старших битов у каждого из хешей и, используя значение этих битов в качестве индекса, будем вычислять не одну оценку, а массив из 2 k оценок, а затем на их основе получим интегральную.

На самом деле, существует несколько вариаций алгоритма LogLog, мы рассмотрим относительно свежий вариант — HyperLogLog. Эта версия позволяет достичь величины стандартной ошибки:

Следовательно, при использовании 8 старших битов в качестве индекса, мы получим стандартную ошибку в 6.5% (σ = 0.065) от истинного числа уникальных элементов. И самое главное, если вооружиться мэд скилзами по теории вероятностей, можно прийти к следующей финальной оценке:

, где αm — корректирующий коэффициент, m — общее количество оценок (2 k ), M — массив самих оценок. Теперь мы знаем почти всё, пришло время для реализации:

Прикинем, сколько байт памяти мы используем, k равно 8, следовательно, массив M состоит из 256 элементов, каждый из них, условно, занимает 4 байта, что в сумме составляет 1 Кбайт. Неплохо, но хотелось бы меньше. Если задуматься, размер единичной оценки из массива M можно уменьшить — необходимо всего ceil(log2(32 + 1 — k)) битов, что, при k = 8, есть 5 бит. В сумме имеем 160 байт, что уже гораздо лучше, но я обещал ещё меньше.

Чтобы было меньше, необходимо заранее знать максимальное возможное количество уникальных элементов в наших данных — N. И действительно, если мы его знаем, нет никакой необходимости использовать все возможные биты из хеша для определения ранга, достаточно ceil(log2(N/m)) битов. Не забываем, что от этого числа нам ещё раз нужно взять логарифм, чтобы получить размер одного элемента массива M.

Предположим, что, в случае с нашим небольшим набором слов, максимальное их количество составляет 3 000, тогда нам необходимо всего 64 байта. В случае с Шекспиром, положим N равным 100 000, и будем иметь обещанные 128 байт при ошибке в 6.5%, 192 байта при 4.6%, 768 при 3.3%. Кстати, реальный размер словарного запаса Шекспира составляет около 30 000 слов.

Конечно, использовать мелкие «байты», например, по 3 бита не очень эффективно с точки зрения производительности. На практике лучше не сходить с ума выстраивая довольно длинные цепочки битовых операций, а применить обычные родные для архитектуры байты. Если вы всё-таки решитесь «мельчить», не забудьте поправить корректирующий оценку код.

Небольшая ложка дёгтя, ошибка σ — это не максимальная ошибка, а, так называемая, стандартная ошибка. Для нас это означает, что 65% результатов будут иметь ошибку не более σ, 95% — не более 2σ и 99% — не более 3σ. Вполне приемлемо, но всегда есть вероятность получить ответ с ошибкой больше ожидаемой.

Судя по моим экспериментам, не следует слишком увлекаться её уменьшением, особенно если данных предполагается мало. В этом случае, начинает работать процедура коррекции, которая не всегда справляется со своими обязанностями. Похоже, алгоритм требует тестирования и настройки под конкретную задачу, если, конечно, это не какая-то глупая ошибка в моей реализации. Это не совсем так.

При использовании хеш-функции шириной 32 бита, алгоритм позволяет подсчитать до 10 9 уникальных элементов при минимальной достижимой стандартной ошибке около 0.5%. Памяти, при такой ошибке, понадобиться порядка 32-64 Кбайт. В целом, LogLog идеально подходит для on-line работы с живыми потоками данных.