Linear counting: så uppskattar du antalet unika värden

Hur kan vi räkna antalet unika värden i någon datamängd om det finns riktigt mycket data? Vi kan till exempel ha en tjänst som mäter antalet unika användare på en stor webbplats, eller på hela .se/.com/.whatever-domänen eller något liknande.

Det naiva sättet

Okej, det är ju ingen match: vi går igenom data och sparar varje värde exakt en gång i någon lämplig datastruktur. I Python kunde vi skriva det ungefär så här (koden är onödigt mångordig, det är med flit):

nonunique_values = [1, 2, 3, 2, 2, 4, 1, 1, 3, 5, 2]

def count_unique(values):
    found = set()
    for item in values:
        if item not in found:
            found.add(item)
    return len(found)

print count_unique(nonunique_values) # 5

Det fungerar. Men tänk om data består av unika v4-identifierare på 36 tecken och det finns kanske tio miljoner unika id:n? Programmet räknar fortfarande ut rätt värde, men hur mycket minne tar det? Vi kan räkna ut det. För enkelhetens skull antar vi att vi sparar uuid som en sträng på 36 tecken. Ett uuid tar då 36 byte, och tio miljoner id:n tar 360 MB.

Det är inte direkt lite, erkänn det. Om det fanns hundra miljoner unika id:n skulle vi redan hamna på flera gigabyte minne. Och då räknar vi bara det som själva datan tar. Lägg till overhead från Python eller JavaScript, så kan du hamna på gigabyte redan med tio miljoner id:n:

Det vill du inte. Hur kommer vi runt det?

Vi kan försöka spara själva id:na mer effektivt, vi kan använda C i stället för Python och därmed sänka minnesbehovet rejält, men det blir ändå inte bra, och ett sådant program skulle fortfarande ta oerhört mycket plats. Då återstår frågan: behöver vi verkligen veta på pricken om det finns exakt 9 563 618 unika värden? Skulle det spela någon roll om vi arbetade med talet 9 547 666? Om ditt svar är att det skulle det, och att du vill ha det exakt, så varsågod. Annars ska vi titta på metoder för att uppskatta antalet unika värden i en datamängd så exakt och snabbt som möjligt och med minimalt minnesbehov.

Hashfunktioner räddar oss

Vi tänker oss en hashfunktion som tar en sträng som indata och ger ett n-bitars tal som utdata. Om du är van vid hashfunktioner som ”returnerar en sträng” kan du tänka dig att strängen i sin tur omvandlas till ett tal, det är inget konstigt med det. Antalet bitar anger hur stort talet är. En 8-bitarsfunktion returnerar ett tal som tar åtta bitar, och i åtta bitar ryms 2⁸ olika värden, typiskt heltalen från 0 till 255. Vi kommer att arbeta med en 24-bitars hashfunktion. En sådan funktion returnerar 2²⁴ olika värden, vilket är 16 777 216.

I stället för att spara själva värdena sparar vi deras 24-bitars hashvärden. För att spara tio miljoner 24-bitars hashvärden behöver vi 30 MB. Det är en tiopotens bättre än de tidigare 360 MB. Koden kunde se ut så här:

def nhash(item, n):
    return hash(item) % (2 ** n)

nonunique_values = [1, 2, 3, 2, 2, 4, 1, 1, 3, 5, 2]

def count_unique_using_nhash(values):
    found = set()
    for item in values:
        checksum = nhash(item, 24)
        if checksum not in found:
            found.add(checksum)
    return len(found)

print count_unique_using_nhash(nonunique_values) # 5

Funktionen hash är Pythons inbyggda funktion och returnerar ett heltal. Funktionen nhash visar en naiv implementation av en n-bitars hashfunktion. Det är inte viktigt att förstå hur den fungerar, eftersom den ändå inte fungerar riktigt rätt (resultatet av funktionen tar inte 24 bitar), men det spelar ingen roll här, det är principen som räknas.

Sedan kommer funktionen count_unique_using_nhash, som räknar unika värden. Den går igenom alla värden, beräknar deras hashvärde och sparar det i variabeln found om det inte redan finns där.

Problemet med den här metoden är att hashfunktionen kan ge samma checksumma för olika strängar, alltså att en kollision kan uppstå. Ju fler kollisioner, desto mer felaktigt resultat. Funktionen count_unique_using_nhash returnerar nästan alltid ett lägre antal unika värden än det verkliga.

Vilken hashfunktion ska man då välja? Det spelar inte så stor roll, men generellt rekommenderas någon variant av MurmurHash.

Bitkartor

Följde du med på kursen i grundläggande C-programmering? I så fall känner du till bitkartor. Hur kan vi använda dem?

Vi skissar idén med en array. Vi behöver nämligen inte spara de beräknade checksummorna, vi kan skapa en array med längden 2²⁴ och initiera alla element till noll. När vi sedan stöter på en checksumma (som ju är ett tal!) skriver vi en etta i arrayen på index checksum och markerar därmed att vi redan har hittat den checksumman. Antalet unika element är då ungefär lika med antalet ettor i arrayen. Koden kunde se ut så här:

def count_unique_using_array(values):
    # lista med längden 2^24 initierad med enbart nollor
    array = [0] * (2 ** 24) 
    for item in values:
        array[nhash(item, 24)] = 1
    return sum(array)

print count_unique_using_array(nonunique_values)

Att använda en array är dock mycket minneskrävande i det här fallet, eftersom vi i varje cell måste spara antingen en etta eller en nolla. I stället kan vi använda ett bitfält. För att du ska förstå: ett heltal (integer) kan till exempel sparas i 32 bitar. Om vi skriver talet 354 i det binära systemet får vi 101100010. Talet 354 skulle alltså lagras i datorn som ett 32-bitars heltal så här (vi skiter i detaljerna, okej?):

00000000 00000000 00000001 01100010

Det är ett ganska trevligt format som vi kan utnyttja, eller hur? Vi vill ju i vår funktion bara spara ettor och nollor, och nu har vi just upptäckt att ett vanligt tal egentligen inte är något annat än en hög med nollor och ettor (ungefär som allt annat i en dator …). Med hjälp av bitoperatorer kan vi alltså spara en etta så att den verkligen bara tar en bit.

Vi återvänder till vår funktion med arrayen. Om vi skrev om den med bitfält skulle det för en 24-bitars hashfunktion räcka med ett bitfält på 2²⁴ bitar, vilket är 2 MiB. Det är en rejäl förbättring!

Med en 32-bitars hashfunktion, som har 2³² olika utdatavärden, vilket är 4 294 967 296, skulle vi behöva ett bitfält på en halv gigabyte. Det är inte så illa med tanke på att vi då kan räkna unika värden upp till miljarder.

Linear counting

Jag har redan nämnt att vi med en hashfunktion bara får en uppskattning av antalet unika värden. Uppskattningen blir mer felaktig ju närmare antalet unika värden kommer antalet olika utdatavärden hos hashfunktionen. Det är logiskt att om vi har en datamängd med fem miljarder unika värden kan vi helt enkelt inte räkna dem med en 24-bitars hashfunktion.

Uppskattningen som vi beräknar med hashfunktioner kan dock göras mer exakt. Det bygger på en enkel tanke: ju fler unika värden det finns i datamängden, desto sannolikare är det att kollisioner uppstår med tiden. (Kollision = två olika indata har samma utdata från hashfunktionen, samma checksumma.) Nu ska vi räkna lite, så vi inför några variabler:

• Vi arbetar med en n-bitars hashfunktion h.
• Antalet möjliga utdata från funktionen h är då 2n. Det antalet betecknar vi med bokstaven m, alltså m=2n.
• Bitfältet där vi sparar vilka checksummor vi har hittat betecknar vi med den stora bokstaven A. Fältet A har längden m.
• När vi har gått igenom hela datamängden med vår algoritm är en del värden i bitfältet lika med noll och en del lika med ett. Det som främst intresserar oss är kvoten ”antal nollor delat med fältets längd”, som anger andelen nollor i bitfältet. I början är den kvoten lika med 1, eftersom fältet är initierat med enbart nollor. Om det vore fifty-fifty skulle kvoten vara en halv osv. Det värdet betecknar vi Z och beräknar som Z = antal nollor / m.

Nu gäller att ju högre värde Z har, desto säkrare kan vi vara på att vår uppskattning av antalet unika värden är exakt. Om vi till exempel går igenom en tom datamängd förblir bitfältet fullt av nollor och Z blir lika med ett. Då är vi helt säkra på att datamängden innehåller lika många unika element som det finns ettor i bitfältet, alltså noll.

Om Z är lika med 0,99 betyder det att en hundradel av bitfältet är fylld med ettor. 99 % av fältet innehåller nollor. Det är fortfarande bra, det är sannolikt att det inte uppstod för många kollisioner under beräkningen och att det bara behövs en minimal korrigering eller ingen alls. Men om Z är lika med 0,05 är det bara 5 % av fältet som förblev noll, och vi har sannolikt stött på väldigt många kollisioner under beräkningen, så det behövs en stor korrigering.

Hur beräknar vi då den här korrigeringen? Vi tar hjälp av logaritmen, en funktion som har den här formen:

Vi är intresserade av den röda delen på intervallet ]0, 1]. Om vi avsätter värdet Z på x-axeln gäller att ju högre Z, desto närmare noll kommer värdet y. Och tvärtom: ju mindre Z, desto mindre blir y. Den slutliga uppskattningen får vi genom att multiplicera det här talet med -m. Lägg märke till att vi för tillräckligt lågt Z får ett tal som till och med är mindre än -1, och om vi multiplicerar det värdet med -m får vi en uppskattning som är större än m: vi har uppskattat att antalet unika värden är större än antalet möjliga checksummor som hashfunktionen h kan ge.

Hela formeln för att beräkna antalet unika värden p ser ut så här:

$$p=-m\cdot \ln Z$$

En implementation (utan bitfält, bara med vanliga arrayer) kunde se ut så här:

from uuid import uuid4
from math import log

number_of_unique_values = 10000
nonunique_values = [uuid4() for _ in xrange(number_of_unique_values)]
nonunique_values += nonunique_values

def nhash(item, n):
    return hash(item) % (2 ** n)

def count_unique_using_array(values, n):
    array = [0] * (2 ** n)
    for item in values:
        array[nhash(item, n)] = 1
    return sum(array)

def linear_counting(values, n):
    estimate = count_unique_using_array(values, n)
    m = 2 ** n
    number_of_zeros = m - estimate
    Z = float(number_of_zeros) / m
    # log är här den naturliga logaritmen med basen e
    p = (-m) * log(Z)      
    p = int(round(p))
    print "Debug info: estimate=%s, m=%s, number_of_zeros=%s, Z=%s, p=%s" % \
          (estimate, m, number_of_zeros, Z, p)
    return p

print "Cardinality: %s" % linear_counting(nonunique_values, 16)

I funktionen linear_counting beräknar vi först en första uppskattning med den tidigare algoritmen, som använder en n-bitars hashfunktion. Sedan beräknar vi andelen nollor i fältet och gör korrigeringen enligt formeln. Logaritmen i koden är den naturliga logaritmen. Variabeln nonunique_values innehåller number_of_unique_values unika strängar, så i det här exemplet finns det tiotusen unika värden i listan nonunique_values. Den där konstiga koden på sjätte raden ser till att fältet innehåller flera likadana värden: vi lägger helt enkelt till samma lista av värden i slutet av listan, så varje värde finns två gånger. Och sedan räknar vi. Funktionen borde helst returnera att listan innehåller tiotusen unika värden. Utdata:

Debug info: estimate=9289, m=65536, number_of_zeros=56247, 
Z=0.858261108398, p=10017
Cardinality: 10017

Eftersom en ny lista nonunique_values genereras varje gång blir resultaten olika vid varje körning. Vi använde en 16-bitars hashfunktion. Vi ser att den första uppskattningen från funktionen count_unique_using_array var att listan innehåller 9289 unika värden. Med korrigeringen förbättrade vi uppskattningen till 10 017, vilket är ganska bra: vår uppskattning är bara 0,17 % för stor, medan den tidigare var 7,11 % för liten, och det är ganska mycket.

Om vi tar en ”större” hashfunktion, till exempel en 24-bitars, får vi ett mer exakt resultat:

Debug info: estimate=9997, m=16777216, number_of_zeros=16767219, 
Z=0.999404132366, p=10000
Cardinality: 10000

Redan den ursprungliga uppskattningen var OK, och korrigeringen landade på exakt tiotusen. Som demonstration kan vi prova en miljon unika id:n, dvs. number_of_unique_values = 1000000. Med en 24-bitars hashfunktion får vi de här resultaten:

Debug info: estimate=971033, m=16777216, number_of_zeros=15806183, 
Z=0.94212192297, p=1000267
Cardinality: 1000267

Det går an. Om vi dessutom implementerar det som ett bitfält skulle fältet bara äta de två megabyte som nämndes (+ det som språket äter). Rätt bra, tycker jag. But we can do better! Much better. Men det får vänta till nästa gång.

Under tiden kan du läsa artikeln A Linear-Time Probabilistic Counting Algorithm for Database Applications [PDF]. Eller så kan du fortsätta till nästa del i serien: algoritmen min-value.