LogLog: hogyan becsüljük meg az egyedi értékek számát
A Linear Counting és a Min Value előző részei után végre eljutottunk az adathalmazban lévő egyedi értékek számát becslő valószínűségi algoritmusok szinte legeslegjobbikához, a LogLoghoz. Nála már csak a kistestvére, a HyperLogLog jobb, amely a LogLogból indul ki, de róla majd legközelebb.
Idézzük fel a feladatot. A bemeneten van valamilyen adathalmaz vagy multihalmaz, például egy tömb vagy generátor, amely azonosítókat ad. Ebben a tömbben egyes értékek többször is szerepelnek, mi pedig meg szeretnénk számolni az egyedi értékeket. Ezt a számot számosságnak nevezzük. Azt várjuk, hogy ez a számosság igazán nagy lesz, különben használhatnánk hagyományos algoritmusokat.
A LogLog algoritmus ötlete
Képzeljük el, hogy van egy bináris vektorokból álló halmazunk. Ne ijedj meg, például a 0001011001001100 egy 16 hosszúságú bináris vektor. Tegyük fel, hogy 32 hosszúságú bináris vektoraink vannak, és összesen egymillió van belőlük, mindegyiket teljesen véletlenszerűen generáltuk. Hány vektor végződik nullára?
Ezt természetesen nem tudhatjuk pontosan, de ha a vektorokat valóban véletlenszerűen generáltuk, akkor nagyjából a felük, azaz 500 ezer végződik nullára. Hány vektor végződik 00-ra? A negyedük. 000-ra? A nyolcaduk. És így tovább. Nagyjából így ábrázolhatjuk:
a vektor mintája az összes vektor hányada
...xxxxxx0 50%
...xxxxx00 25%
...xxxx000 12,5%
...xxx0000 6,25%
... ...
Ha egy d hosszúságú utótagról (az utótag az a karakterlánc, amelyre egy másik karakterlánc végződik – az előtag ellentéte) megkérdezzük, hogy hány vektor végződik rá, azt várjuk, hogy v darabot találunk. A v értékét így számoljuk ki:
ahol N a halmazban lévő összes vektor száma. A 3 hosszúságú utótag (például …010) a vektorok 1/2^3 N = 1/8 N részében fordul elő, azaz az összes vektor 12,5%-ában.
Most jön egy kis agyfacsarás. Vegyünk egy 1024 egyedi vektorból álló multihalmazt. Hány vektornak kellene a 0000000000 utótagra végződnie? (tíz nulla) Behelyettesítünk a képletbe, és azt kapjuk, hogy
Ejha, egy! Ezer véletlenszerűen generált bináris vektor között pontosan egy olyan vektornak kell lennie, amely tíz nullára végződik. És hogyan használhatjuk fel ezt az információt az egyedi elemek számának becslésére? Eljárhatunk ugyanis fordítva is. Mi lesz, ha végigmegyünk az összes bemeneti bináris vektoron, és azt találjuk, hogy a halmazban egyetlen vektor végződik tíz nullára? Akkor bizonyára megbecsülhetjük, hogy a halmazban 1024 vektor volt!
Általánosítunk és felépítjük az algoritmust
A cél az volna, hogy találjunk olyan utótagot, amely csak egyetlen vektorban szerepel, és ráadásul a lehető legrövidebb. Ez azonban csak nagyon nehezen megy, mert hogy tényleg megtaláljunk egy ilyen vektort, minden utótagot el kellene tárolnunk, amit nem akarunk, mert túl sok memóriát foglalna. Ehelyett beérjük azzal, hogy a vektor végén keressük a nullák leghosszabb sorozatát.
Végigmegyünk tehát az összes vektoron, mindegyiknél megszámoljuk, hány nulla van a végén, és egyetlen változóban tároljuk ezeknek az értékeknek a maximumát. Amikor az összes vektoron végigmentünk, ismerni fogjuk a csak nullákból álló leghosszabb utótag hosszát. Ezt a hosszt d betűvel jelöljük. Most úgy alakítjuk át az előző képletet, hogy az N változót kifejezzük, azaz az algoritmus kimenete legyen, ne a bemenete. Közben v helyére egyet írhatunk, mert azt várjuk, hogy pontosan egy ilyen vektort találunk, vagyis v=1 teljesül.
Ha tehát megtaláljuk a leghosszabb nullás utótag d hosszát, a számosságot az N=2d képlettel becsüljük.
Hogyan szerezzünk véletlen bináris vektorokat?
Véletlen bináris vektorokkal az algoritmus már működik, de hogyan alkalmazzuk az eljárást valódi adatokra? Mint általában, itt is használunk valamilyen megfelelő hash-függvényt. Ha a bemeneten adathalmaz van, például azonosítók (sztringek), először kiszámoljuk a hash-üket. Az n bites hash-függvény kimenete n bit, amely gyakorlati szempontból úgy néz ki, mint a véletlenszerűen generált bináris vektor.
Most már leírhatjuk az algoritmusunkat:
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
A trailing_zeroes függvény a szám végén álló nullák számát adja vissza. Hogyan csinálja? Ha a kódból nem érted, inkább ne is kérdezd. És milyen pontos a függvény? Egy százezer egyedi elemet tartalmazó halmazra 524 288 lett a becslés.
Hát…
Ugye, ez nem túl jó? De nem baj! Az algoritmust pontosan úgy javítjuk, mint az előző Min Value esetében. A bemeneti adatokat felosztjuk több diszjunkt csoportra, minden csoportra kiszámoljuk a legnagyobb nullás utótagot, végül kiszámoljuk a nullás utótag átlagos hosszát, és ezt használjuk az egyedi elemek számának becslésére.
Mondhatjuk például, hogy minden vektor utolsó két bitje határozza meg annak a csoportnak a számát, amelyhez a vektor tartozik. Ezt a hat vektort
1101110111111011 1110110010100101
1011001111110010 1111101100000011
1010101000100000 0110010110011000
négy csoportra oszthatjuk aszerint, hogy mi a végződésük:
00 01 1010101000100000 1110110010100101 0110010110011000 10 11 1011001111110010 1101110111111011 1111101100000011
Ezután kiszámoljuk a leghosszabb nullás utótag hosszát minden vektorban, de közben átugorjuk azokat a biteket, amelyeket a csoport számának megadására használtunk. A nullás „utótagokat” zölddel jelöljük:
00 01 1010101000100000 1110110010100101 0110010110011000 10 11 1011001111110010 1101110111111011 1111101100000011 00: 3 01: 0 10: 2 11: 6
A végén ott vannak az adott csoportok leghosszabb nullás utótagjainak hosszai. Ezekből kiszámolhatjuk a számtani közepet, ami 2,75. Az értéket behelyettesítjük a képletbe, és azt kapjuk, hogy
Ez az egyedi elemek átlagos száma egy csoportban. Ami persze egyáltalán nem stimmel, de emiatt ne bánkódjunk, kis halmazokra a LogLog algoritmus borzalmas eredményeket ad.
Az egész halmaz számosságának becsléséhez ezt az értéket még meg kell szorozni a csoportok számával: 6,727 · 4 = 26,908. Az algoritmus szerint tehát a halmazban nagyjából 27 egyedi érték van. Hat volt benne, szóval teljesen mellément, de ez most tényleg nem számít.
Az algoritmus megvalósítása
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
A k paraméter azt adja meg, hány bitet vegyünk a csoport indexének. Ez a paraméter határozza meg az algoritmus pontosságát – minél nagyobb a k, annál pontosabb. A bucket_index változóban a csoport száma van eltárolva. Hogyan működik az a varázslat az egyenlőségjel jobb oldalán?
A num_buckets változóban a csoportok száma van, ami mindig kettő hatványa. Ha például k = 3, akkor num_buckets=8. A 8 kettes számrendszerben 1000. Ha levonunk belőle egyet, megkapjuk a 7-et, ami 0111. A num_buckets értékéből egyet levonva mindig olyan számot kapunk, amelynek a végén k darab egyes áll, előtte pedig csupa nulla. Ezután elvégezzük a logikai szorzást (ez az & operátor). Az 1110110010100101 vektorra ez a művelet így néz ki:
1110110010100101
& 0000000000000111
------------------
0000000000000101
Az egész varázslat célja, hogy olyan számot kapjunk, amelynek az elején csupa nulla áll, az utolsó k bitje pedig megegyezik az adott h hash utolsó k bitjével.
Ezután kiszámoljuk a bucket_hash értéket, vagyis az eredeti hasht, amelyből úgy távolítjuk el az utolsó k bitet, hogy az egész hasht k bittel jobbra toljuk. Az eltolás úgy működik, hogy a szám minden bitjét k bittel jobbra mozgatja, balról pedig nullákkal tölti fel a számot. (Az eggyel való jobbra tolás ugyanúgy viselkedik, mintha a számot elosztanád kettővel, és a maradékot eldobnád.) Az 1110110010100101 vektorból hárommal való eltolás után 0001110110010100 lesz. Ez a vektor kerülne a bucket_hash változóba.
Ezután megszámoljuk a nullákat ennek a vektornak a végén, és ha ez az érték nagyobb, mint a max_zeroes tömbben a bucket_index indexen tárolt jelenlegi maximum, felülírjuk az értéket.
A végén már csak kiszámoljuk a nullák átlagos számát az összes csoportban, és kiszámoljuk, hogy átlagosan hány egyedi elem van egy csoportban (2 ** average_max_zeros). Mivel összesen num_buckets csoportunk van, ezt az értéket megszorozzuk a csoportok számával, és megkapjuk az egyedi elemek számának végső becslését. Hú, és még csak nem is fájt. Az eredmények néhány olyan adathalmazra, amely 250 000 egyedi elemet tartalmaz, k=10 mellett:
331774.56203
323349.39265
307343.444439
309430.914045
294512.379123
Neeeem, még mindig rossz :-(. De már elég közel vagyunk, ne aggódj. Vedd észre, hogy minden eredmény nagyobb a helyes eredménynél. Az algoritmus futása közben ugyanis különféle hibák halmozódnak fel, ezért a becslés érezhetően nagyobb a helyes eredménynél. Ezek a hibák viszont meglehetősen állandóak, és megbecsülhető, mekkora hiba keletkezett. Ha a becslést megszorozzuk a 0,79402 tapasztalati szorzóval, lényegesen jobb eredményeket kapunk:
263435.63774306054
256745.88475195298
244036.84175345476
245694.33437001088
233848.71927124445
Kipróbáltam egy olyan multihalmazt is, amelynek a számossága egymillió, az eredmények:
Eredmény Hiba
1017297.17411 1.01729717411
1022820.99717 1.02282099717
984108.725487 0.984108725487
1018675.32683 1.01867532683
1007020.2853 1.0070202853
Szépen, nagyon szépen! A hiba 2,5% alatt marad, ami tisztességes teljesítmény. És ez, hölgyeim és uraim, a LogLog algoritmus. A végleges megvalósítás a tapasztalati szorzóval együtt így néz ki:
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
Hogy hogyan kell ezt az algoritmust átalakítani, hogy megkapjuk a mesés és legeslegjobb HyperLogLogot, azt majd legközelebb elmondjuk. Egyelőre nézzük meg, mekkora az algoritmus memóriaigénye.
Memóriaigény
Az algoritmus memóriahasználata nagyon hatékony. Az egyetlen, amit meg kell jegyeznünk, a maximumokat tároló tömb. Ennek a tömbnek a hosszát a k értéke befolyásolja, vagyis hogy a vektor hány bitjét vesszük a csoport indexének. Adott k mellett összesen 2k különböző csoportunk van, ezért a maximumok tömbjének hossza 2k. Ezt az értéket hívtuk a megvalósításban num_buckets-nek.
Mekkora legyen a tömb egy cellája? A nullás utótagok hosszát fogjuk beleírni. Előre elárulhatom, hogy a 64 bites hash valószínűleg elég a világ minden elképzelhető multihalmazához, tehát a tömbbe 0-tól 64-ig kell tudnunk számokat tárolni (a csupa egyesből álló vektor 0, a csupa nullából álló 64). Ha ráadásul feltesszük, hogy k mindig nagyobb nullánál, akkor elég a 0 és 63 közötti számokat tárolni. Ehhez, kérlek szépen, 6 bit elég, mert 26 = 64.
Igen, elég egy „tömb”, amelyben egy cella 6 bit méretű. Azt is elárulhatom, hogy a k=10 érték elég ahhoz, hogy a számosságot egész jól megbecsüljük a százmilliós nagyságrendig. Az így beállított algoritmus egy 210 = 1024 méretű tömböt hozna létre, amelyben minden cella 6 bitet foglal. Ez a tömb összesen 6144 bitet foglalna, vagyis 768 bájtot. Egy kilobájtot sem.
És ez minden.
Mást nem kell tárolnunk, a kiszámolt hasheket rögtön eldobhatjuk, elég tudnunk a nullák számát a vektor végén.
Vedd észre, hogy ha nagyobb hash-függvényt használnál, például olyat, amely 128 bitet ad vissza, a memóriaigény nem sokat változna. Ekkor ugyanis 0-tól 127-ig kellene számokat tárolnunk, amihez 7 bit elég. A memóriaigényt tehát elsősorban a k paraméter, vagyis a csoportok száma határozza meg.
A LogLog főleg ott hasznos, ahol igazán nagy számosságú multihalmazokat kell megszámolnunk. Ahogy a fenti egyszerű példa is mutatta, a LogLog nem a legjobban boldogul a kis számosságú multihalmazokkal. Ezen viszont szintén lehet segíteni, például úgy, hogy ha kiderül, hogy a multihalmaz számossága alacsony, a becslésre másik algoritmust használunk, például a korábban leírt Linear Countingot. Erről is lesz szó legközelebb.
Források:
- Loglog Counting of Large Cardinalities [PDF]
- Damn Cool Algorithms: Cardinality Estimation (a LogLog kódja nagyjából innen való)
Fejezetek: Linear Counting, Min Value, LogLog, HyperLogLog
