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

4. 10. 2022

Kapitoly: Linear Counting, Min Value, LogLog, HyperLogLog

Після попередніх частин про 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 обчислимо так:

$$\Large 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}}\cdot1024=\frac{1}{1024}\cdot1024=1$$

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

Узагальнюємо і складаємо алгоритм

Мета — знайти такий суфікс, який міститься лише в одному векторі, причому цей суфікс має бути якомога коротшим. Це, однак, дуже важко, бо щоб справді знайти такий вектор, довелося б зберігати всі суфікси, а цього ми не хочемо, адже це забрало б забагато пам'яті. Натомість вдовольнимося пошуком найдовшої послідовності нулів у кінці вектора.

Отже, проходимо по всіх векторах, для кожного вектора обчислюємо, скільки нулів він має в кінці, і в одній змінній зберігаємо максимум із цих значень. Коли пройдемо по всіх векторах, знатимемо довжину найдовшого суфікса, що складається лише з нулів. Цю довжину позначаємо літерою d. Тепер перетворимо попередню формулу так, щоб виразити змінну N, тобто щоб вона була виходом алгоритму, а не входом. При цьому замість v можна підставити одиницю, бо ми очікуємо знайти рівно один такий вектор, тобто очікуємо, що v=1.

$$\begin{eqnarray} v&=&\frac{N}{2^d}\\ v\cdot2^d&=&N\\ 2^d&=&N \end{eqnarray}$$

Отже, знайшовши довжину 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}\approx6{,}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)

« Попередня: Min Value

Наступна: HyperLogLog »