LogLog: cum estimăm numărul de valori unice
După părțile anterioare despre Linear Counting și Min Value, ajungem în sfârșit la aproape cel mai bun algoritm probabilistic de estimare a numărului de valori unice dintr-un set de date, LogLog. Mai bun este doar fratele lui mai mic, HyperLogLog, care pornește de la LogLog, dar despre el data viitoare.
Să repetăm enunțul problemei. La intrare avem un set de date/o multimulțime, de exemplu un tablou/generator de ID-uri. În acest tablou unele valori apar de mai multe ori, iar noi vrem să calculăm numărul de valori unice din tablou. Acest număr îl vom numi cardinalitate. Ne așteptăm ca această cardinalitate să fie cu adevărat foarte mare, altfel putem folosi algoritmi convenționali.
Ideea algoritmului LogLog
Să ne imaginăm că avem un set de vectori binari. Nu te speria, de exemplu acesta 0001011001001100 este un vector binar de lungime 16. Să zicem că avem vectori binari de lungime 32 și că avem în total un milion dintre ei, toți generați complet aleatoriu. Câți vectori se vor termina cu cifra zero?
Desigur, nu putem ști exact, dar dacă vectorii au fost într-adevăr generați aleatoriu, aproximativ jumătate dintre ei ar trebui să se termine cu zero, adică 500 de mii. Câți vectori se vor termina cu 00? O pătrime. Cu 000? O optime. Și așa mai departe. Putem reprezenta aceasta aproximativ așa:
model de vector ponderea din toți vectorii
...xxxxxx0 50 %
...xxxxx00 25 %
...xxxx000 12,5 %
...xxx0000 6,25 %
... ...
Dacă ne întrebăm despre un sufix (sufixul este șirul cu care se termină un alt șir – opusul prefixului) de lungime d, ne așteptăm să găsim v vectori care se termină cu acest sufix. Valoarea v o calculăm astfel:
unde N este numărul tuturor vectorilor din set. Un sufix de lungime 3 (de exemplu …010) ar trebui să apară în 1/2^3 N = 1/8 N dintre vectori, adică 12,5% din toți vectorii.
Acum facem un mic mindfuck. Fie o multimulțime de 1024 de vectori unici. Câți vectori ar trebui să se termine cu sufixul 0000000000? (zece zerouri) Înlocuim în formulă și obținem
Huh, unul! Dintr-o mie de vectori binari generați aleatoriu ar trebui să existe exact un vector care se termină cu zece zerouri. Și cum folosim această informație ca să estimăm numărul de elemente unice? Noi putem să procedăm invers. Ce-ar fi dacă parcurgem toți vectorii binari de la intrare și constatăm că în set există un singur vector care se termină cu zece zerouri? Atunci putem estima că în set au fost 1024 de vectori!
Generalizăm și construim algoritmul
Scopul ar trebui să fie să găsim un sufix care este conținut într-un singur vector, iar acest sufix să fie cât mai scurt. Dar asta este foarte greu de realizat, pentru că, pentru a găsi cu adevărat un astfel de vector, ar trebui să stocăm toate sufixele, ceea ce nu vrem, pentru că ar ocupa prea multă memorie. În loc de asta, ne mulțumim să căutăm cea mai lungă secvență de zerouri de la sfârșitul unui vector.
Parcurgem deci toți vectorii, pentru fiecare vector numărăm câte zerouri are la sfârșit și într-o singură variabilă păstrăm maximul acestor valori. După ce am parcurs toți vectorii, vom cunoaște lungimea celui mai lung sufix format doar din zerouri. Această lungime o notăm cu litera d. Acum modificăm formula anterioară astfel încât să izolăm variabila N, adică să fie ieșirea algoritmului, nu intrarea. În același timp, în locul lui v putem înlocui unu, pentru că ne așteptăm să găsim exact un astfel de vector, adică ne așteptăm ca v=1.
Dacă găsim așadar lungimea d a celui mai lung sufix nul, estimăm cardinalitatea cu formula N=2d.
Cum obținem vectori binari aleatorii?
Cu vectori binari aleatorii algoritmul funcționează deja, dar cum aplicăm acest procedeu pe date reale? Ca de obicei, și aici folosim o funcție hash potrivită. Dacă avem la intrare un set de date, de exemplu ID-uri (string-uri), le trecem mai întâi prin funcția hash. Ieșirea unei funcții hash de n biți este de n biți care, din punct de vedere practic, arată ca niște vectori binari generați aleatoriu.
În acest moment putem scrie algoritmul nostru:
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
Funcția trailing_zeroes returnează numărul de zerouri de la sfârșitul numărului. Cum face asta? Dacă n-ai înțeles din cod, mai bine nici nu întreba. Și ce succes are funcția? Pentru o mulțime care conținea o sută de mii de elemente unice, funcția a returnat estimarea 524.288.
Ei bine…
Deci, nu e chiar bine, nu? Dar nu face nimic! Încercăm să îmbunătățim algoritmul exact ca la Min Value anterior. Împărțim datele de intrare în mai multe grupuri disjuncte, pentru fiecare grup calculăm cel mai lung sufix nul, apoi calculăm lungimea medie a sufixului nul și o folosim pentru a estima numărul de valori unice.
Putem decide, de exemplu, că ultimii doi biți ai fiecărui vector vor determina numărul grupului din care face parte vectorul. Acești șase vectori
1101110111111011 1110110010100101
1011001111110010 1111101100000011
1010101000100000 0110010110011000
îi putem împărți în patru grupuri după terminația pe care o au:
00 01 1010101000100000 1110110010100101 0110010110011000 10 11 1011001111110010 1101110111111011 1111101100000011
Apoi calculăm lungimea celui mai lung sufix nul din fiecare vector, sărind însă peste biții pe care i-am folosit ca număr al grupului. „Sufixele” nule le marcăm cu verde:
00 01 1010101000100000 1110110010100101 0110010110011000 10 11 1011001111110010 1101110111111011 1111101100000011 00: 3 01: 0 10: 2 11: 6
La final avem lungimile celor mai lungi sufixe nule din fiecare grup. Din aceste valori putem calcula media aritmetică, care ne iese 2,75. Înlocuim valoarea în formulă și obținem
Am obținut numărul mediu de elemente unice din fiecare grup. Ceea ce, desigur, nu se potrivește deloc, dar nu ne chinuim cu asta, pentru mulțimi mici algoritmul LogLog dă rezultate îngrozitoare.
Ca să estimăm cardinalitatea întregii mulțimi, trebuie să înmulțim încă această valoare cu numărul de grupuri: 6,727 · 4 = 26,908. Algoritmul a calculat că în set sunt aproximativ 27 de valori unice. Erau șase, deci este complet pe lângă, dar acum chiar nu contează.
Implementarea algoritmului
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
Parametrul k determină câți biți se iau drept index al grupului. Acest parametru determină precizia algoritmului – cu cât k este mai mare, cu atât precizia este mai mare. În variabila bucket_index este păstrat numărul grupului. Cum funcționează magia aceea din dreapta semnului egal?
În variabila num_buckets se află numărul de grupuri, care este întotdeauna o putere a lui doi. Dacă, de exemplu, k = 3, atunci num_buckets=8. Numărul 8 are în baza 2 forma 1000. Dacă scădem unu, obținem numărul 7, care are forma 0111. Dacă scădem unu din num_buckets, obținem întotdeauna un număr care are la sfârșit k unu și înainte numai zerouri. Apoi efectuăm conjuncția pe biți (este operatorul &). Pentru vectorul 1110110010100101 această operație ar arăta astfel:
1110110010100101
& 0000000000000111
------------------
0000000000000101
Scopul întregii magii este să obținem un număr care la început conține numai zerouri, iar ultimii k biți îi are identici cu cei ai hash-ului h dat.
Apoi calculăm bucket_hash, adică hash-ul inițial din care eliminăm ultimii k biți, deplasând întregul hash cu k biți la dreapta. Deplasarea se comportă astfel: pur și simplu mută toți biții din număr cu k poziții la dreapta, iar la stânga numărul se completează cu zerouri. (Deplasarea la dreapta cu unu se comportă la fel ca și cum ai împărți numărul la doi și ai arunca restul.) Din vectorul 1110110010100101, după deplasarea cu trei, am obține 0001110110010100. Acest vector ar fi stocat în variabila bucket_hash.
Apoi calculăm numărul de zerouri de la sfârșitul acestui vector și, dacă această valoare este mai mare decât maximul curent stocat în tabloul max_zeroes la indexul bucket_index, rescriem valoarea.
La final calculăm doar numărul mediu de zerouri din toate grupurile și calculăm care este numărul mediu de elemente unice din fiecare grup (2 ** average_max_zeros). Pentru că avem în total num_buckets grupuri, înmulțim această valoare tocmai cu numărul de grupuri și obținem astfel estimarea finală a numărului de elemente unice. Uf, și nici n-a durut. Rezultatele pentru mai multe seturi de date care conțin 250.000 de valori unice și k=10:
331774.56203
323349.39265
307343.444439
309430.914045
294512.379123
Neee, tot greșit :-(. Dar suntem deja destul de aproape, nu te teme. Observă că toate rezultatele sunt mai mari decât rezultatul corect. Pe parcursul algoritmului se acumulează diverse erori și, de aceea, estimarea este vizibil mai mare decât rezultatul corect. Totuși, aceste erori sunt relativ constante și se poate estima cât de mare a fost eroarea. Dacă înmulțim estimarea cu constanta magică 0,79402, obținem rezultate fundamental mai bune:
263435.63774306054
256745.88475195298
244036.84175345476
245694.33437001088
233848.71927124445
Am încercat și o multimulțime cu cardinalitatea de un milion, rezultatele:
Rezultat Eroare
1017297.17411 1.01729717411
1022820.99717 1.02282099717
984108.725487 0.984108725487
1018675.32683 1.01867532683
1007020.2853 1.0070202853
Foarte frumos! Eroarea se situează sub 2,5%, ceea ce este o performanță rezonabilă. Și acesta este, doamnelor și domnilor, algoritmul LogLog. Implementarea finală, cu constanta magică, arată astfel:
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
Cum modificăm acest algoritm ca să obținem mult-lăudatul HyperLogLog, cel mai bun, vom afla data viitoare. Deocamdată să vedem cât de mare este consumul de memorie al algoritmului.
Consumul de memorie
Algoritmul este foarte eficient în ceea ce privește memoria ocupată. Singurul lucru pe care trebuie să-l ținem minte este tabloul care păstrează maximele. Lungimea acestui tablou este influențată de valoarea k, adică de numărul de biți din vector pe care îi luăm drept index al grupului. Pentru un k dat avem în total 2k grupuri diferite, deci tabloul de maxime are lungimea 2k. Această valoare am numit-o în implementare num_buckets.
Cât de mare trebuie să fie o celulă a tabloului? În ea vom stoca lungimile sufixelor nule. Îți pot dezvălui dinainte că un hash de 64 de biți ajunge probabil pentru toate multimulțimile imaginabile din lume, deci în acest tablou trebuie să putem stoca numere de la 0 (vector egal cu numai unu) până la 64 (vector egal cu numai zerouri). Mai departe, dacă presupunem că k va fi mereu mai mare decât zero, atunci ne ajunge să stocăm numere de la 0 la 63. Pentru asta, te rog frumos, ne ajung 6 biți, pentru că 26 = 64.
Da, ne ajunge un „tablou” în care o celulă are dimensiunea de 6 biți. Îți mai pot dezvălui că valoarea k=10 ajunge ca să estimăm destul de bine cardinalități până în ordinul sutelor de milioane. Un algoritm configurat astfel ar crea un tablou de dimensiune 210 = 1024, în care fiecare celulă ocupă 6 biți. În total, acest tablou ar ocupa 6144 de biți, adică 768 de octeți. Nici măcar un kilooctet.
Și asta e tot.
Nu avem nevoie să stocăm nimic altceva, hash-urile calculate le putem arunca imediat, ne ajunge să cunoaștem numărul de zerouri de la sfârșitul vectorului.
Observă că, dacă ai folosi o funcție hash mai mare, care ar returna, de exemplu, 128 de biți, consumul de memorie nu s-ar schimba prea mult. Ar trebui să stocăm numere de la 0 la 127, iar pentru asta ne ajung 7 biți. Consumul de memorie este determinat, așadar, în primul rând de parametrul k, adică de numărul de grupuri.
LogLog se potrivește mai ales acolo unde trebuie să numărăm multimulțimi cu cardinalitate cu adevărat foarte mare. După cum s-a văzut și din exemplul simplu de mai sus, LogLog nu se descurcă tocmai ideal cu multimulțimile care au cardinalitate mică. Și acest lucru se poate remedia, de exemplu, astfel: dacă aflăm că multimulțimea are o cardinalitate mică, folosim pentru estimare un alt algoritm, de exemplu Linear Counting, descris mai devreme. Despre asta vom vorbi tot data viitoare.
Surse:
- Loglog Counting of Large Cardinalities [PDF]
- Damn Cool Algorithms: Cardinality Estimation (de acolo este preluat, mai mult sau mai puțin, codul LogLog)
Capitole: Linear Counting, Min Value, LogLog, HyperLogLog
