Min Value: як оцінити кількість унікальних значень

4. 10. 2022

Kapitoly: Linear Counting, Min Value, LogLog, HyperLogLog

У минулій статті про Linear Counting ми розглянули базові алгоритми обчислення й оцінки кількості унікальних значень у певному наборі даних. Сьогодні на нас чекає ще один імовірнісний алгоритм, який дає змогу з пристойною точністю і малими вимогами до пам'яті оцінити кількість унікальних значень.

Min Value

У цій статті працюватимемо лише з дійсними числами з одиничного проміжку (0; 1). Уявімо рівномірно розподілену множину чисел із цього проміжку, наприклад множину {0,25; 0,5; 0,75}. Сусідні числа завжди розташовані на відстані рівно 0,25 одне від одного (а також від нуля й від одиниці). Як це допоможе нам порахувати кількість унікальних елементів?

Якщо я скажу, що в нас є така рівномірно розподілена множина чисел з одиничного проміжку і відстань між її числами дорівнює рівно 0,2, — чи зможеш ти обчислити, скільки в цій множині елементів? Звісно, це множина {0,2; 0,4; 0,6; 0,8}, і кількість її елементів дорівнює чотирьом. Якщо на вході маємо рівномірно розподілені числа з одиничного проміжку і знаємо відстань між сусідніми числами, легко обчислити кількість елементів.

При цьому відстань між сусідніми числами дорівнює мінімальному елементу множини — відстань між сусідніми елементами множини {0,25; 0,5; 0,75} дорівнює 0,25 тощо. Щоб обчислити кількість елементів рівномірно розподілених чисел, достатньо якось знайти мінімальний елемент. Тоді кількість елементів p можна обчислити простою формулою:

$$\Large p=\frac{1}{m}-1$$

де m — це той самий мінімальний елемент.

І знову хешуватимемо…

Гаразд, але як це використати, якщо на вході в нас рядки чи інші значення, які не задовольняють умову рівномірного розподілу в одиничному проміжку? Допоможе знову стара добра хеш-функція, яка може для будь-якого входу повернути раціональне число з одиничного проміжку. Побудувати таку хеш-функцію неважко.

Так ми отримали б із даних раціональні числа, але як зробити їх рівномірно розподіленими? Цього вже не досягти, проте можна вчинити інакше. З нашого погляду хеш-функція поводиться досить «випадково». Для дуже схожих слів, як-от «ahoj», «ahok» і «ahol», хеш-функція, найімовірніше, повертатиме дуже різні хеші. Іншими словами: якщо ми захешуємо тисячу різних значень в одиничний проміжок, дуже малоймовірно, що переважна більшість чисел виявиться, скажімо, меншою за одну другу. Навпаки, дуже ймовірно, що ці числа розподілені більш-менш рівномірно. Чим більше даних ми захешуємо, тим рівномірнішим буде розподіл.

З цієї ідеї випливає простий алгоритм: проходимо по вхідних даних, кожен елемент хешуємо в одиничний проміжок і запам'ятовуємо мінімальний елемент. Кількість унікальних елементів оцінюємо за попередньою формулою. Реалізація на Python:

from uuid import uuid4

def nhash(item, n):
    return hash(item) % (2 ** n)

def unit_interval_hash(item, n):
    integer_hash = nhash(item, n) + 1
    return integer_hash / float(2 ** n)

def count_unique_using_minimum(values, n):
    numbers_from_unit_interval = (unit_interval_hash(item, n) for item in values)
    minimum = min(numbers_from_unit_interval)
    return int(1 / minimum) - 1

for _ in xrange(10):
    print count_unique_using_minimum((uuid4() for _ in xrange(10000)), 16)

Функція unit_interval_hash повертає нам десяткове число з проміжку (0; 1]. Функція count_unique_using_minimum спершу перетворює всі вхідні значення саме на таке число, знаходить мінімум і повертає 1 / minimum - 1. Зверни увагу, що зовсім не має значення, скільки в наборі даних однакових значень: для двох однакових значень хеш-функція поверне те саме раціональне число, а на підсумковий мінімум це ніяк не вплине. Тому цим алгоритмом ми рахуємо кількість унікальних елементів.

Які результати? (У кожному рядку наведено оцінку кількості унікальних значень, а правильна відповідь — 10 000.)

Ну, не дуже, правда? Алгоритм опрацював десять різних наборів ідентифікаторів, у кожному з яких було по десять тисяч унікальних значень. Отримані оцінки здебільшого сильно відхиляються. Якщо їх усереднити, ми отримаємо 18 352. Усе одно далеко від правди, зате глянь на вимоги до пам'яті — вони сталі! Щоб знайти мінімум, достатньо весь час тримати в пам'яті одну змінну з поточним мінімумом, і все. Тож так, оцінка нікудишня, зате майже нічого не коштує.

Вдосконалюємо

Бачимо, що алгоритм насамперед нестабільний: то дає доволі добру оцінку (9362), то оцінку, що геть не влучає (65536). Як із цим впоратися? Можна розділити вхідні дані на кілька частин, порахувати кількість унікальних елементів для кожної частини, а наприкінці все гарненько усереднити. Групу можна визначати за першим символом нашого ідентифікатора. Отже, окремо порахуємо кількість унікальних значень серед ідентифікаторів, що починаються на літеру «a», потім серед тих, що починаються на «b», і так далі. Код:

from uuid import uuid4

def nhash(item, n):
    return hash(item) % (2 ** n)

def unit_interval_hash(item, n):
    integer_hash = nhash(item, n) + 1
    return integer_hash / float(2 ** n)

def count_unique_using_minimum(values, n):
    min_values = {}
    for item in values:
        first_char = str(item)[0]
        hashed_value = unit_interval_hash(item, n)
        min_values[first_char] = min(min_values.get(first_char, 1), hashed_value)
    average_minimum = sum(min_values.values()) / len(min_values)
    return (int(1 / average_minimum) - 1) * len(min_values)

for _ in xrange(10):
    print count_unique_using_minimum((uuid4() for _ in xrange(10000)), 16)

Зміни — у функції count_unique_using_minimum. У змінній min_values ми зберігаємо мінімуми для кожної групи. Наприкінці додаємо всі мінімуми й ділимо на кількість збережених значень — отримуємо середній мінімум. Виразом 1/average_minimum дізнаємося, яка в середньому кількість унікальних значень у кожній групі, — цю величину ще множимо на кількість груп і отримуємо оцінку кількості унікальних значень у переданому наборі даних. А як працює цей змінений підхід?

Ну, усе ще не ідеально, але точно краще. Алгоритм стабільніший. Можна спробувати змінити функцію так, щоб групи утворювалися не за першим символом, а, скажімо, за двома першими символами ідентифікатора, тобто так:

first_char = str(item)[0:2] # ToDo: choose better name for variable

Результати тоді були б такі:

Оце вже не так і погано, правда? А якщо ще спробувати сто тисяч унікальних значень, перші два символи і n = 24, отримаємо такі результати:

Цілком терпимо. Але існують ще кращі алгоритми, не хвилюйся.

А які вимоги до пам'яті? Нам потрібно зберігати мінімум для кожної групи, більше нічого. Якщо ідентифікатори в шістнадцятковому форматі, то запам'ятовувати треба щонайбільше 16^x мінімумів, де x — кількість символів, з яких складається ключ групи. Один мінімум — це одне раціональне число, тобто якийсь тип double або float.

Зауваження наприкінці: розділити вхід на кілька груп ми могли дозволити собі тому, що на вході були ідентифікатори, які поводилися як випадковий рядок. Якби на вході був не випадковий рядок, а дані певного формату, довелося б розділяти інакше. Якби, наприклад, кожен ідентифікатор починався з префікса userid-, то поділ на групи за першим символом навряд чи спрацювало б, еге ж.

« Попередня: Оцінка кількості унікальних значень

Наступна: LogLog »