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

След предишните части за Linear Counting и Min Value най-после стигаме до почти най-най-добрия вероятностен алгоритъм за оценка на броя на уникалните стойности в набор от данни, LogLog. По-добър от него е само неговото братче HyperLogLog, което произлиза от LogLog, но за него — следващия път.

Да повторим задачата. На входа имаме някакъв набор от данни/мултимножество, например някакъв масив/генератор на идентификатори. В този масив някои стойности се срещат по няколко пъти и искаме да пресметнем броя на уникалните стойности в този масив. На този брой ще казваме кардиналност. Очакваме тази кардиналност да е наистина голяма, иначе можем да използваме конвенционални алгоритми.

Идея на алгоритъма LogLog

Нека си представим, че имаме набор от двоични вектори. Не се плаши, например това 0001011001001100 е двоичен вектор с дължина 16. Да речем, че имаме двоични вектори с дължина 32 и че са общо един милион, всички напълно случайно генерирани. Колко вектора ще завършват с цифрата нула?

Това, разбира се, не можем да знаем точно, но ако наистина сме генерирали векторите случайно, приблизително половината от тях трябва да завършват с нула, т.е. 500 хиляди. Колко вектора ще завършват на 00? Една четвърт. На 000? Една осма. И така нататък. Можем да го изобразим приблизително така:

образец на вектора   дял от всички вектори
...xxxxxx0           50%
...xxxxx00           25%
...xxxx000           12,5%
...xxx0000           6,25%
     ...             ...

Ако питаме за суфикс (суфикс е низът, с който завършва друг низ — обратното на префикс) с дължина d, очакваме да намерим v вектора, които завършват с този суфикс. Стойността v пресмятаме като:

$v = \frac{1}{2^{d}} \cdot N$

където N е броят на всички вектори в набора. Суфикс с дължина 3 (например …010) би трябвало да се среща в 1/2^3 N = 1/8 N вектора, т.е. 12,5% от всички вектори.

Сега ще направим един малък мисловен фокус. Нека имаме мултимножество от 1024 уникални вектора. Колко вектора трябва да завършват със суфикса 0000000000? (десет нули) Заместваме във формулата и получаваме

$v = \frac{1}{2^{10}} \cdot 1024 = \frac{1}{1024} \cdot 1024 = 1$

Хм, един! В хиляда случайно генерирани двоични вектора трябва да има точно един вектор, който завършва с десет нули. И как да използваме тази информация, за да оценим броя на уникалните елементи? Можем да действаме и в обратна посока. Ами ако минем през всички двоични вектори, които имаме на входа, и установим, че в набора има един-единствен вектор, който завършва с десет нули? Тогава можем да оценим, че в набора е имало 1024 вектора!

Обобщаваме и съставяме алгоритъма

Целта трябва да е да намерим такъв суфикс, който се съдържа само в един вектор, като този суфикс е възможно най-кратък. Това обаче е много трудно, защото за да намерим наистина такъв вектор, би трябвало да запазваме всички суфикси, което не искаме, защото би заело твърде много памет. Вместо това се задоволяваме с търсене на най-дългата редица от нули в края на вектора.

Минаваме следователно през всички вектори, за всеки вектор пресмятаме колко нули съдържа в края и в една променлива пазим максимума от тези стойности. След като минем през всички вектори, ще знаем дължината на най-дългия суфикс, който се състои само от нули. Тази дължина означаваме с буквата d. Сега променяме предишната формула така, че да отделим променливата N, т.е. тя да е изход на алгоритъма, а не вход. При това вместо v можем да заместим едно, защото очакваме да намерим точно един такъв вектор, т.е. очакваме да е в сила v=1.

$\begin{array}{rcl} v & = & \frac{N}{2^{d}} \\ v \cdot 2^{d} & = & N \\ 2^{d} & = & N \end{array}$

Ако намерим дължината d на най-дългия нулев суфикс, оценяваме кардиналността с формулата N=2^d.

Как да получим случайни двоични вектори?

Със случайни двоични вектори алгоритъмът вече работи, но как да приложим този подход към реални данни? Както обикновено, и тук ще използваме подходяща хеш функция. Ако на входа имаме набор от данни, например идентификатори (низове), първо ги хешираме. Изходът на n-битовата хеш функция са n бита, които от практическа гледна точка изглеждат като случайно генерирани двоични вектори.

В този момент вече можем да запишем нашия алгоритъм:

def trailing_zeroes(number):
    if number == 0: 
        return 0

    zeroes = 0
    while (number & 1) == 0:
        zeroes += 1
        number = number >> 1
    return zeroes

def count_unique(values):
    max_zero_suffix_length = 0
    for value in values:
        zeroes_length = trailing_zeroes(hash(value))
        max_zero_suffix_length = max(zeroes_length, max_zero_suffix_length)
    return 2 ** max_zero_suffix_length

Функцията trailing_zeroes връща броя на нулите в края на числото. Как го прави? Ако не си го разбрал от кода, по-добре дори не питай. И какъв е успехът на функцията? За мултимножество, което съдържаше сто хиляди уникални елемента, функцията върна оценка 524 288.

Е…

Не е съвсем добре, нали? Но няма значение! Ще опитаме да подобрим алгоритъма точно както предишния Min Value. Разделяме входните данни на няколко непресичащи се групи и за всяка група пресмятаме максималния нулев суфикс и накрая пресмятаме средната дължина на нулевия суфикс и я използваме за оценка на броя на уникалните стойности.

Можем например да кажем, че последните два бита на всеки вектор определят номера на групата, към която принадлежи векторът. Тези шест вектора

1101110111111011     1110110010100101
1011001111110010     1111101100000011
1010101000100000     0110010110011000

можем да разделим на четири групи според това какво завършване имат:

00                   01              
1010101000100000     1110110010100101
0110010110011000                     

10                   11
1011001111110010     1101110111111011
                     1111101100000011

След това пресмятаме дължината на най-дългия нулев суфикс във всеки вектор, като при това прескачаме онези битове, които използвахме като номер на групата. Нулевите „суфикси“ ще оцветим в зелено:

00                   01                     
1010101000100000     1110110010100101    
0110010110011000

10                   11
1011001111110010     1101110111111011
                     1111101100000011

00: 3                01: 0
10: 2                11: 6

В края са дължините на най-дългите нулеви суфикси от съответната група. От тези суфикси можем да пресметнем средно аритметично, което ни се получава 2,75. Стойността заместваме във формулата и получаваме

$2^{2, 75} \approx 6,727$

Получаваме среден брой уникални елементи във всяка група. Това, разбира се, изобщо не отговаря на действителността, но не се притесняваме, за малки множества алгоритъмът LogLog дава ужасни резултати.

За да оценим кардиналността на цялото множество, трябва още да умножим тази стойност по броя на групите: 6,727 · 4 = 26,908. Алгоритъмът пресметна, че в набора има приблизително 27 уникални стойности. А те бяха шест, така че оценката е съвсем погрешна, но сега наистина няма значение.

Реализация на алгоритъма

def trailing_zeroes(number):
    if number == 0: 
        return 0
    zeroes = 0
    while (number & 1) == 0:
        zeroes += 1
        number = number >> 1
    return zeroes

def estimate_cardinality(values, k):
    num_buckets = 2 ** k
    max_zeroes = [0] * num_buckets
    for value in values:
        h = hash(value)
        bucket_index = h & (num_buckets - 1)
        bucket_hash = h >> k
        num_zeros = trailing_zeroes(bucket_hash)
        max_zeroes[bucket_index] = max(max_zeroes[bucket_index], num_zeros)
    average_max_zeros = float(sum(max_zeroes)) / num_buckets
    return (2 ** average_max_zeros) * num_buckets

Параметърът k определя колко бита ще се вземат като индекс на групата. Този параметър определя точността на алгоритъма — колкото по-голямо е k, толкова по-голяма е точността. В променливата bucket_index се пази номерът на групата. Как работи магията от дясната страна на знака за равенство?

В променливата num_buckets е броят на групите, който винаги е степен на числото две. Ако например k = 3, то num_buckets=8. Числото 8 има в двоична бройна система вида 1000. Ако извадим единица, получаваме числото 7, което има вида 0111. След изваждането на единица от num_buckets винаги получаваме число, което има в края k единици, а преди тях само нули. След това извършваме логическо произведение (това е операторът &). За вектора 1110110010100101 тази операция би изглеждала така:

  1110110010100101
& 0000000000000111
------------------
  0000000000000101

Целта на цялата тази магия е да получим число, което в началото съдържа само нули, а последните му k бита са същите като на дадения хеш h.

След това пресмятаме bucket_hash, който е първоначалният хеш, от който махаме последните k бита, като целия хеш изместим с k бита надясно. Изместването действа така, че просто всички битове в числото се изместват с k бита надясно и отляво числото се допълва с нули. (Побитовото изместване надясно с едно се държи точно както ако разделиш числото на две и отхвърлиш остатъка.) От вектора 1110110010100101 след изместване с три бихме получили 0001110110010100. Този вектор би бил запазен в променливата bucket_hash.

След това пресмятаме броя на нулите в края на този вектор и ако тази стойност е по-голяма от текущата максимална стойност, запазена в масива max_zeroes на индекс bucket_index, презаписваме стойността.

Накрая само пресмятаме средния брой нули във всички групи и пресмятаме какъв е средният брой уникални елементи във всяка група (2 ** average_max_zeros). Тъй като имаме общо num_buckets групи, умножаваме тази стойност по броя на групите, с което получаваме крайната оценка на броя на уникалните елементи. Уф, и дори не боля. Резултати за няколко набора от данни, които съдържат 250 000 уникални стойности, при k=10:

331774.56203
323349.39265
307343.444439
309430.914045
294512.379123

Неееее, пак е лошо :-(. Но вече сме доста близо, не се безпокой. Забележи, че всички резултати са по-големи от правилния резултат. По време на алгоритъма се натрупват различни грешки и затова оценката е осезаемо по-голяма от правилния резултат. Тези грешки обаче са сравнително постоянни и може да се прецени колко голяма е настъпилата грешка. Ако умножим оценката по корекционната константа 0.79402, получаваме резултати, които са значително по-добри:

263435.63774306054
256745.88475195298
244036.84175345476
245694.33437001088
233848.71927124445

Опитах още с мултимножество, което има кардиналност един милион, резултатите:

Резултат              Грешка
1017297.17411         1.01729717411
1022820.99717         1.02282099717
984108.725487         0.984108725487
1018675.32683         1.01867532683
1007020.2853          1.0070202853

Чудесно! Грешката е под 2,5%, което е прилична стойност. И това, дами и господа, е алгоритъмът LogLog. Окончателната реализация с корекционната константа изглежда така:

def trailing_zeroes(number):
    if number == 0: 
        return 0
    zeroes = 0
    while (number & 1) == 0:
        zeroes += 1
        number = number >> 1
    return zeroes

def estimate_cardinality(values, k):
    num_buckets = 2 ** k
    max_zeroes = [0] * num_buckets
    for value in values:
        h = hash(value)
        bucket_index = h & (num_buckets - 1)
        bucket_hash = h >> k
        num_zeros = trailing_zeroes(bucket_hash)
        max_zeroes[bucket_index] = max(max_zeroes[bucket_index], num_zeros)
    average_max_zeros = float(sum(max_zeroes)) / num_buckets
    return (2 ** average_max_zeros) * num_buckets * 0.79402

Как да променим този алгоритъм, за да получим онзи легендарен и най-най-добър HyperLogLog, ще разкажем следващия път. Засега ще разгледаме колко памет изисква алгоритъмът.

Изисквания към паметта

Алгоритъмът е много ефективен откъм заета памет. Единственото, което трябва да помним, е масивът, който пази максимумите. Дължината на този масив се определя от стойността k, т.е. от броя на битовете от вектора, които вземаме като индекс на групата. За дадено k имаме общо 2^k различни групи и масивът на максимумите има затова дължина 2^k. Тази стойност в реализацията наричахме num_buckets.

Колко голяма трябва да е една клетка на масива? В нея ще запазваме дължините на нулевите суфикси. Мога да ти издам предварително, че 64-битов хеш стига най-вероятно за всички мислими мултимножества на света, така че в този масив трябва да можем да запазим числата от 0 (вектор само от единици) до 64 (вектор само от нули). Освен това, ако предположим, че k винаги ще е по-голямо от нула, то ни стига да запазваме числата от 0 до 63. За това ни стигат, моля ти се, 6 бита, защото 2⁶ = 64.

Да, достатъчен ни е „масив“, в който една клетка има големина 6 бита. Мога да ти издам още, че стойността k=10 е достатъчна, за да оценим кардиналността съвсем прилично до порядъка на стотици милиони. Така настроеният алгоритъм би създал масив с големина 2¹⁰ = 1024, в който всяка клетка заема 6 бита. Общо този масив би заемал 6144 бита, което са 768 байта. Дори не е килобайт.

И това е всичко.

Нищо друго не е нужно да запазваме, пресметнатите хешове можем веднага да изхвърляме, достатъчно е да знаем броя на нулите в края на вектора.

Забележи, че ако използваш по-голяма хеш функция, която например връща 128 бита, изискванията към паметта няма да се променят особено. Би трябвало да запазваме числата от 0 до 127, а за това ни стигат 7 бита. Изискванията към паметта следователно определя най-вече параметърът k, т.е. броят на групите.

LogLog е подходящ най-вече там, където трябва да броим мултимножества с наистина голяма кардиналност. Както се видя и от простия пример по-горе, LogLog не се справя особено добре с мултимножества, които имат малка кардиналност. Това обаче също може да се поправи, например като установим, че мултимножеството има ниска кардиналност, и използваме за оценката друг алгоритъм, например описания по-рано Linear Counting. И за това ще говорим следващия път.

Източници:

Loglog Counting of Large Cardinalities [PDF]
Damn Cool Algorithms: Cardinality Estimation (оттам е повече или по-малко преписан кодът на LogLog)

Глави: Linear counting: как да оценим броя на уникалните стойности, Min Value: как да оценим броя на уникалните стойности, LogLog: как да оценим броя на уникалните стойности, HyperLogLog: как да оценим много точно броя на уникалните стойности

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

Следваща: HyperLogLog: как да оценим много точно броя на уникалните стойности »