Min Value: как да оценим броя на уникалните стойности

В предишната статия за 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 с проста формула:

$$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.)

5957
16384
13107
9362
65536
8192
21845
13107
21845
8192

Не е кой знае какво, нали? Алгоритъмът мина през десет различни набора от идентификатори, в които винаги имаше десет хиляди уникални стойности. Пресметнатите оценки в повечето случаи са доста далеч от истината. Ако ги усредним, стигаме до стойността 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 откриваме какъв е средният брой уникални стойности във всяка група — накрая умножаваме тази стойност по броя на групите и получаваме оценения брой на уникалните стойности в подадения набор от данни. И как работи този променен подход?

11312
7504
10560
8160
9344
12688
10976
11616
16240
6832

Още не е добре, но със сигурност е по-добре. Алгоритъмът е по-стабилен. Можем да опитаме да променим функцията така, че групите да не се образуват по първия знак, а например по първите два знака на идентификатора, т.е. така:

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

Тогава резултатите биха били такива:

9728
9728
9984
10240
8960
10752
9728
9472
11264
9472

Оооо, това вече не е съвсем лошо, нали? Ако опитаме още със сто хиляди уникални стойности, първите два знака и n = 24, получаваме тези резултати:

103936
110080
102656
101120
101376
108288
97536
97024
107776
92416

Горе-долу става. Но все пак има по-добри алгоритми, не се безпокой.

А каква е нуждата от памет? Трябва да пазим минимума за всяка група, нищо повече. Ако идентификаторите са в hex формат, това означава, че трябва да помним най-много 16^x минимума, където x е броят на знаците, от които образуваме ключа на групата. Един минимум е едно рационално число, т.е. някакъв тип double или float.

Бележка накрая: можехме да си позволим да разделим входа на няколко групи, защото на входа имахме идентификатори, които се държаха като случаен низ. Ако на входа нямаме случаен низ, а някакви данни в определен формат, би трябвало да направим разделянето по друг начин. Ако например всеки идентификатор започваше с префикса userid-, разделянето на групи по първия знак едва ли би проработило, нали така.