LogLog: så uppskattar du antalet unika värden
Efter de tidigare delarna om Linear Counting och Min Value kommer vi äntligen till den nästan allra bästa probabilistiska algoritmen för att uppskatta antalet unika värden i en datamängd: LogLog. Bättre är bara lillebror HyperLogLog, som bygger på LogLog, men den tar vi nästa gång.
Vi repeterar problemet. Som indata har vi någon datamängd/multimängd, till exempel en array eller generator av ID:n. I den här arrayen finns vissa värden flera gånger, och vi vill räkna antalet unika värden i den. Det här antalet kallar vi kardinalitet. Vi förväntar oss att kardinaliteten är riktigt stor, annars kan vi använda konventionella algoritmer.
Idén bakom LogLog-algoritmen
Tänk dig att vi har en mängd binära vektorer. Var inte rädd, till exempel 0001011001001100 är en binär vektor med längden 16. Säg att vi har binära vektorer med längden 32 och att vi har en miljon av dem, alla helt slumpmässigt genererade. Hur många vektorer slutar på en nolla?
Det kan vi förstås inte veta exakt, men om vi verkligen genererade vektorerna slumpmässigt bör ungefär hälften av dem sluta på noll, alltså 500 000. Hur många vektorer slutar på 00? En fjärdedel. På 000? En åttondel. Och så vidare. Vi kan åskådliggöra det ungefär så här:
vektormönster andel av alla vektorer
...xxxxxx0 50 %
...xxxxx00 25 %
...xxxx000 12,5 %
...xxx0000 6,25 %
... ...
Om vi frågar efter ett suffix (ett suffix är den sträng som en annan sträng slutar med — motsatsen till prefix) med längden d, förväntar vi oss att hitta v vektorer som slutar med just det suffixet. Värdet v räknar vi ut som:
där N är antalet vektorer i mängden. Ett suffix med längden 3 (till exempel …010) borde förekomma i 1/2^3 N = 1/8 N av vektorerna, alltså i 12,5 % av alla vektorer.
Nu kommer en liten hjärnvridare. Säg att vi har en multimängd med 1024 unika vektorer. Hur många vektorer borde sluta på suffixet 0000000000? (tio nollor) Vi sätter in i formeln och får
Oj, en enda! Bland tusen slumpmässigt genererade binära vektorer borde det finnas just en vektor som slutar på tio nollor. Och hur använder vi den informationen för att uppskatta antalet unika element? Vi kan nämligen gå åt andra hållet. Tänk om vi går igenom alla binära vektorer i indata och upptäcker att det finns en enda vektor som slutar på tio nollor? Då kan vi väl uppskatta att det fanns 1024 vektorer i mängden!
Vi generaliserar och bygger algoritmen
Målet borde vara att hitta ett suffix som finns i bara en enda vektor och som dessutom är så kort som möjligt. Det är dock mycket svårt, eftersom vi för att verkligen hitta en sådan vektor skulle behöva spara alla suffix, vilket vi inte vill eftersom det skulle ta för mycket minne. I stället nöjer vi oss med att leta efter den längsta följden av nollor i slutet av en vektor.
Vi går alltså igenom alla vektorer, för varje vektor räknar vi hur många nollor den har på slutet, och i en enda variabel sparar vi maximum av de här värdena. När vi har gått igenom alla vektorer känner vi till längden på det längsta suffixet som bara består av nollor. Den här längden betecknar vi med bokstaven d. Nu ändrar vi den tidigare formeln så att vi löser ut variabeln N, så att den blir algoritmens utdata och inte indata. I stället för v kan vi sätta in ett, eftersom vi förväntar oss att hitta just en sådan vektor, alltså förväntar oss att v=1 gäller.
Om vi hittar längden d på det längsta nollsuffixet, uppskattar vi alltså kardinaliteten med formeln N=2d.
Hur får vi tag i slumpmässiga binära vektorer?
Med slumpmässiga binära vektorer fungerar algoritmen redan, men hur tillämpar vi metoden på riktiga data? Som vanligt använder vi också här en lämplig hashfunktion. Om indata är en datamängd, till exempel ID:n (strängar), hashar vi dem först. Utdata från en n-bitars hashfunktion är n bitar som i praktiken ser ut som slumpmässigt genererade binära vektorer.
Nu kan vi skriva ner vår algoritm:
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
Funktionen trailing_zeroes returnerar antalet nollor i slutet av talet. Hur gör den det? Om du inte förstod det av koden är det bäst att inte ens fråga. Och hur träffsäker är funktionen? För en mängd som innehöll hundra tusen unika element returnerade funktionen uppskattningen 524 288.
Tja…
Det är inte särskilt bra, eller hur? Men det gör inget! Vi försöker förbättra algoritmen precis som i förra delen, Min Value. Vi delar upp indata i flera disjunkta hinkar, för varje hink räknar vi det längsta nollsuffixet, och till sist räknar vi ut den genomsnittliga längden på nollsuffixen och använder den för att uppskatta antalet unika värden.
Vi kan till exempel bestämma att de två sista bitarna i varje vektor anger numret på den hink som vektorn tillhör. De här sex vektorerna
1101110111111011 1110110010100101
1011001111110010 1111101100000011
1010101000100000 0110010110011000
kan vi dela upp i fyra hinkar efter vilken ändelse de har:
00 01 1010101000100000 1110110010100101 0110010110011000 10 11 1011001111110010 1101110111111011 1111101100000011
Därefter räknar vi längden på det längsta nollsuffixet i varje vektor, men hoppar över de bitar som vi använde som hinknummer. Nollsuffixen markerar vi med grönt:
00 01 1010101000100000 1110110010100101 0110010110011000 10 11 1011001111110010 1101110111111011 1111101100000011 00: 3 01: 0 10: 2 11: 6
Till sist har vi längderna på de längsta nollsuffixen i varje hink. Av de här längderna kan vi räkna ut det aritmetiska medelvärdet, som blir 2,75. Vi sätter in värdet i formeln och får
Vi får det genomsnittliga antalet unika element i varje hink. Det stämmer förstås inte alls, men det bryr vi oss inte om — för små mängder ger LogLog-algoritmen hemska resultat.
För att uppskatta kardinaliteten för hela mängden måste vi också multiplicera det här värdet med antalet hinkar: 6,727 · 4 = 26,908. Algoritmen räknade ut att det finns ungefär 27 unika värden i mängden. Det fanns sex, så det är helt fel, men det spelar faktiskt ingen roll just nu.
Implementation av algoritmen
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
Parametern k anger hur många bitar som används som hinkindex. Den här parametern avgör algoritmens noggrannhet — ju högre k, desto högre noggrannhet. I variabeln bucket_index finns hinknumret. Hur fungerar magin till höger om likhetstecknet?
I variabeln num_buckets finns antalet hinkar, som alltid är en potens av talet två. Om till exempel k = 3 är num_buckets=8. Talet 8 skrivs 1000 i det binära talsystemet. Om vi subtraherar ett får vi talet 7, som skrivs 0111. När vi subtraherar ett från num_buckets får vi alltså alltid ett tal som har k ettor i slutet och bara nollor före. Sedan utför vi ett logiskt OCH (det är operatorn &). För vektorn 1110110010100101 skulle den här operationen se ut så här:
1110110010100101
& 0000000000000111
------------------
0000000000000101
Syftet med hela den här magin är att vi ska få ett tal som börjar med bara nollor och vars sista k bitar är desamma som i den givna hashen h.
Sedan räknar vi ut bucket_hash, alltså den ursprungliga hashen utan de sista k bitarna, genom att vi skiftar hela hashen k bitar åt höger. Skiftet fungerar så att alla bitar i talet flyttas k steg åt höger och att talet fylls på med nollor från vänster. (Ett bitskift ett steg åt höger fungerar på samma sätt som om du delade talet med två och kastade resten.) Av vektorn 1110110010100101 får vi efter ett skift på tre steg 0001110110010100. Den vektorn skulle sparas i variabeln bucket_hash.
Sedan räknar vi antalet nollor i slutet av den här vektorn, och om värdet är större än det nuvarande maximivärdet som finns i arrayen max_zeroes på index bucket_index skriver vi över värdet.
Till sist räknar vi bara ut det genomsnittliga antalet nollor i alla hinkar och beräknar det genomsnittliga antalet unika element i varje hink (2 ** average_max_zeros). Eftersom vi har sammanlagt num_buckets hinkar multiplicerar vi det här värdet med antalet hinkar och får den slutliga uppskattningen av antalet unika element. Puh, och det gjorde inte ens ont. Resultat för några datamängder som innehåller 250 000 unika element och k=10:
331774.56203
323349.39265
307343.444439
309430.914045
294512.379123
Neeej, fortfarande fel :-(. Men vi är redan ganska nära, oroa dig inte. Lägg märke till att alla resultat är större än det rätta. Under algoritmens gång ackumuleras nämligen olika fel, och uppskattningen blir därför märkbart större än det rätta resultatet. De här felen är dock ganska konstanta, och man kan uppskatta hur stort felet blev. När vi multiplicerar uppskattningen med det magiska talet 0,79402 (en s.k. fudge factor) får vi resultat som är betydligt bättre:
263435.63774306054
256745.88475195298
244036.84175345476
245694.33437001088
233848.71927124445
Jag provade också en multimängd med kardinaliteten en miljon, och resultaten blev:
Resultat Fel
1017297.17411 1.01729717411
1022820.99717 1.02282099717
984108.725487 0.984108725487
1018675.32683 1.01867532683
1007020.2853 1.0070202853
Fint så! Felet ligger under 2,5 %, vilket är en bra prestation. Och det, mina damer och herrar, är algoritmen LogLog. Den slutliga implementationen med det magiska talet ser ut så här:
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
Hur vi ändrar den här algoritmen för att få den sagolika och allra bästa HyperLogLog tar vi nästa gång. Tills vidare tittar vi på hur minneskrävande algoritmen är.
Minnesbehov
Algoritmen är mycket effektiv när det gäller minne. Det enda vi behöver komma ihåg är arrayen som håller maximivärdena. Längden på arrayen bestäms av värdet på k, alltså antalet bitar från vektorn som vi använder som hinkindex. För ett givet k har vi sammanlagt 2k olika hinkar, och maxarrayen har därför längden 2k. Det här värdet kallade vi num_buckets i implementationen.
Hur stor måste en cell i arrayen vara? Vi ska spara längderna på nollsuffix i den. Jag kan i förväg avslöja att en 64-bitars hash troligen räcker för alla tänkbara multimängder i världen, så vi måste kunna spara tal från 0 (en vektor med bara ettor) till 64 (en vektor med bara nollor). Om vi dessutom antar att k alltid är större än noll räcker det att spara tal från 0 till 63. Det räcker, minsann, med 6 bitar eftersom 26 = 64.
Ja, vi klarar oss med en ”array” där en cell är 6 bitar stor. Jag kan också avslöja att värdet k=10 räcker för att uppskatta kardinaliteten hyfsat bra upp till hundratals miljoner. En algoritm som är inställd så skulle skapa en array med storleken 210 = 1024, där varje cell tar 6 bitar. Sammanlagt skulle arrayen ta 6144 bitar, alltså 768 byte. Inte ens ett kilobyte.
Och det är allt.
Något annat behöver vi inte spara, de beräknade hasharna kan vi kasta direkt, vi behöver bara känna till antalet nollor i slutet av vektorn.
Lägg märke till att om du skulle använda en större hashfunktion som till exempel returnerade 128 bitar, skulle minnesbehovet knappt ändras. Vi skulle då behöva spara tal från 0 till 127, och för det räcker 7 bitar. Minnesbehovet avgörs alltså framför allt av parametern k, alltså antalet grupper.
LogLog passar framför allt där vi behöver räkna multimängder med riktigt stor kardinalitet. Som man också såg i det enkla exemplet ovan klarar LogLog inte särskilt bra av multimängder med liten kardinalitet. Det går dock också att avhjälpa: om vi upptäcker att multimängden har låg kardinalitet, använder vi en annan algoritm för uppskattningen, till exempel den tidigare beskrivna Linear Counting. Det kommer vi också att prata om nästa gång.
Källor:
- Loglog Counting of Large Cardinalities [PDF]
- Damn Cool Algorithms: Cardinality Estimation (därifrån är koden till LogLog i stort sett lånad)
Kapitel: Linear counting: så uppskattar du antalet unika värden, Min Value: så uppskattar du antalet unika värden, LogLog: så uppskattar du antalet unika värden, HyperLogLog: så uppskattar du antalet unika värden med hög precision
