Linear counting: Sådan estimerer du antallet af unikke værdier

Hvordan kunne vi tælle antallet af unikke værdier i et datasæt, hvis der var rigtig mange data? Vi kan fx have en tjeneste, der måler antallet af unikke brugere på et stort website eller sagtens på hele .dk/.com/.whatever-domænet eller noget i den stil.

Den naive fremgangsmåde

Okay, der er jo ikke noget at tænke over, vi gennemgår simpelthen data og gemmer hver værdi præcis én gang i en passende datastruktur. I Python kunne vi skrive det nogenlunde sådan her (koden er unødigt snakkesalig, det er med vilje):

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 virker. Men hvad nu, hvis data er 36 tegn lange unikke v4-identifikatorer, og hvad nu, hvis der er ti millioner af dem? Tja… programmet beregner stadig den rigtige værdi, men hvor meget hukommelse fylder det? Vi kan prøve at regne på det. For enkelhedens skyld antager vi, at vi gemmer uuid'et som en streng på 36 tegn. Et uuid fylder dermed 36 byte, og ti millioner ID'er fylder 360 MB.

Det er ikke ligefrem lidt, lad os være ærlige. Hvis der var hundrede millioner unikke ID'er, ville vi allerede komme op i gigabyte af optaget hukommelse. Og det er stadig kun det, som selve data fylder. Læg dertil en overhead, som fx Python/JavaScript optager, og du kan komme op i gigabyte allerede med ti millioner ID'er:

Det vil du ikke. Hvordan kommer vi ud af det?

Vi kan prøve at gemme selve ID'erne mere effektivt, vi kan bruge C i stedet for Python, hvilket vil sænke hukommelsesforbruget markant, men det er stadig ikke helt det rigtige, og sådan et program ville stadig fylde utroligt meget. Tilbage står spørgsmålet: har vi virkelig brug for at vide helt på hår, om der lige nu er 9.563.618 unikke værdier? Ville der ske noget, hvis vi arbejdede med tallet 9.547.666? Hvis dit svar er, at ja, der ville ske noget, og at du vil have det præcist, så værsgo. Ellers lad os se på fremgangsmåder, hvor man så præcist, hurtigt og med så lidt hukommelse som muligt estimerer antallet af unikke værdier i et datasæt.

Hashfunktion — vores redning

Vi betragter en hashfunktion, som tager en streng som input og returnerer et n-bit tal som output. Hvis du er vant til hashfunktioner, der »returnerer en streng«, så forestil dig blot, at strengen efterfølgende konverteres til et tal, det er der ikke noget i. Antallet af bit angiver, hvor stort tallet er. En 8-bit funktion returnerer et tal, der fylder otte bit, og i otte bit kan man gemme 2⁸ forskellige værdier, typisk heltallene fra 0 til 255. Vi vil fremover arbejde med en 24-bit hashfunktion. En sådan funktion returnerer 2²⁴ forskellige værdier, hvilket er 16.777.216.

I stedet for at gemme selve værdierne gemmer vi deres 24-bit hashes. For at gemme ti millioner 24-bit hashes har vi brug for 30 MB. Det er en størrelsesorden bedre end de foregående 360 MB. Koden kunne se sådan her ud:

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 er en indbygget funktion i Python og returnerer et heltal, funktionen nhash viser en naiv implementering af en n-bit hashfunktion; det er ikke vigtigt at forstå, hvordan den virker, for den virker alligevel ikke korrekt — funktionens resultat fylder ikke 24 bit, men det er lige meget nu, for mig handler det om princippet.

Så følger funktionen count_unique_using_nhash, som tæller unikke værdier. Den gennemgår alle værdier, beregner deres hash og gemmer den i variablen found, hvis den værdi ikke allerede er der.

Problemet ved denne fremgangsmåde er, at hashfunktionen kan returnere den samme checksum for forskellige strenge — der kan opstå en kollision. Jo flere sådanne kollisioner der opstår, desto upræcisere bliver resultatet. Funktionen count_unique_using_nhash returnerer næsten altid et mindre antal unikke værdier, end der i virkeligheden er.

Og hvilken hashfunktion skal man vælge? Det betyder ikke så forfærdelig meget, men generelt anbefales en eller anden variant af MurmurHash.

Bitmaps

Gav du agt i Grundlæggende programmering i C? Hvis ja, kender du bitmaps. Hvordan kunne de bruges?

Vi skitserer ideen med et array. Vi behøver nemlig ikke gemme de beregnede checksums, vi kan oprette et array med længden 2²⁴ og initialisere alle elementer til nul. Når vi så støder på en checksum — som er et tal! — skriver vi et ettal i arrayet på indeks checksum, og dermed noterer vi, at vi allerede har fundet denne checksum. Antallet af unikke elementer er så cirka lig med antallet af ettaller i arrayet. Koden kunne se sådan her ud:

def count_unique_using_array(values):
    # liste med laengden 2^24 initialiseret til udelukkende nuller
    array = [0] * (2 ** 24) 
    for item in values:
        array[nhash(item, 24)] = 1
    return sum(array)

print count_unique_using_array(nonunique_values)

Det er dog i dette tilfælde meget hukommelseskrævende at bruge et array, fordi vi i hver celle skal gemme enten et ettal eller et nul. I stedet kan vi bruge et bitfelt. For at du kan følge med: et heltal (integer) kan fx gemmes i 32 bit. Når vi omregner tallet 354 til det binære talsystem, får vi 101100010. Tallet 354 ville derfor i en computer som et 32-bit integer blive gemt (detaljerne er vi ligeglade med, ikke?) sådan her:

00000000 00000000 00000001 01100010

Det er et ret rart format, som vi kunne udnytte, ikke? I vores funktion vil vi nemlig kun gemme ettaller og nuller, og nu har vi lige fundet ud af, at et almindeligt tal i virkeligheden ikke er andet end en bunke nuller og ettaller (ligesom alt andet i en computer…). Kort sagt kan vi ved hjælp af bitoperatorer gemme et ettal, så det virkelig kun fylder én bit.

Vi vender tilbage til vores funktion med arrayet. Hvis vi omskrev den til bitfelter, ville vi til en 24-bit hashfunktion nøjes med et bitfelt på 2²⁴ bit, hvilket er 2 MiB. Det er en ordentlig opgradering!

Ved brug af en 32-bit hashfunktion, som har 2³² forskellige outputværdier, hvilket er 4.294.967.296, ville vi have brug for et bitfelt på en halv gigabyte. Det er ikke helt dårligt, når man tænker på, at vi dermed kan tælle unikke værdier op i størrelsesordenen milliarder.

Linear Counting

Jeg har allerede nævnt, at vi ved brug af en hashfunktion kun får et estimat af antallet af unikke værdier. Dette estimat er desto mere upræcist, jo tættere antallet af unikke værdier kommer på antallet af forskellige outputværdier fra hashfunktionen. Det er logisk, at hvis vi har et datasæt med fem milliarder unikke værdier, kan en 24-bit hashfunktion simpelthen ikke tælle dem.

Det estimat, vi beregner ved hjælp af hashfunktioner, kan dog præciseres yderligere. Dertil bruges en simpel idé — jo flere unikke værdier der er i datasættet, desto mere sandsynligt er det, at der med tiden opstår kollisioner. (Kollision = to forskellige input har det samme output fra hashfunktionen, den samme checksum.) Nu skal vi regne lidt, så vi indfører nogle variabler:

• Vi arbejder med en n-bit hashfunktion h.
• Antallet af alle mulige outputværdier fra funktionen h er dermed lig med 2n. Dette antal betegner vi med bogstavet m, altså: m=2n.
• Det bitfelt, hvor vi gemmer, hvilke checksums vi har fundet, betegner vi med det store bogstav A. Feltet A har længden m.
• Når vi har kørt hele datasættet igennem vores algoritme, vil nogle værdier i bitfeltet være nul og nogle ét. Vi vil især interessere os for forholdet »antal nuller divideret med feltets længde«, som angiver den relative andel af nuller i bitfeltet. I begyndelsen er den andel lig med 1, fordi feltet er initialiseret til udelukkende nuller. Hvis det stod fifty-fifty, ville andelen være lig med en halv osv. Denne værdi betegner vi Z og beregner den som Z = antal nuller / m.

På dette tidspunkt gælder, at jo højere værdien af Z er, desto større sikkerhed har vi for, at vores estimat af antallet af unikke værdier er præcist. Hvis vi fx gennemgår et tomt datasæt, bliver der kun nuller i bitfeltet, og værdien Z bliver lig med et — vi har dermed fuld sikkerhed for, at der i vores datasæt er lige så mange unikke elementer, som der er ettaller i bitfeltet — nul.

Hvis værdien Z er lig med 0,99, betyder det, at en hundrededel af bitfeltet er fyldt med ettaller. 99 % af feltet indeholder nuller. Det er stadig godt, det er sandsynligt, at der under beregningen ikke er opstået alt for mange kollisioner, og der skal måske slet ingen eller kun en minimal korrektion til. Hvis værdien Z derimod er lig med 0,05, er kun 5 % af feltet forblevet nul, og vi er sandsynligvis undervejs stødt på rigtig mange kollisioner — der skal en stor korrektion til.

Men hvordan beregner vi denne korrektion? Vi bruger logaritmen, som er en funktion med denne form:

Vi interesserer os for den røde del på intervallet ]0; 1]. Hvis vi afsætter værdien Z på x-aksen, opnår vi, at jo højere Z, desto tættere kommer værdien y på nul. Og omvendt — jo mindre Z, desto mindre bliver værdien y. Det endelige estimat beregner vi ved at gange dette tal med -m. Læg mærke til, at vi for en tilstrækkelig lav værdi af Z får et tal, der endda er mindre end -1, og når vi ganger denne værdi med -m, får vi et estimat, der er større end m: vi har estimeret, at antallet af unikke værdier er større end antallet af alle de checksums, der overhovedet kan komme ud af hashfunktionen h.

Hele formlen til beregning af antallet p af unikke værdier ville se sådan her ud:

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

Implementeringen (uden bitfelter, kun med almindelige arrays) kunne se sådan her ud:

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 er her den naturlige logaritme med grundtal 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 beregner vi først et første estimat ved hjælp af den foregående algoritme, som bruger en n-bit hashfunktion. Derefter beregner vi andelen af nuller i arrayet og foretager korrektionen efter formlen. Logaritmen i koden er den naturlige logaritme. Variablen nonunique_values indeholder number_of_unique_values unikke strenge, i dette eksempel er der altså ti tusind unikke værdier i listen nonunique_values. Den mærkelige kode på sjette linje sørger for, at der er flere ens værdier i arrayet: vi sætter simpelthen den samme liste af værdier på enden af listen, så hver værdi er der to gange. Og så regner vi. Funktionen skulle helst returnere, at listen indeholder ti tusind unikke værdier. Output:

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

Da der hver gang genereres en ny liste nonunique_values, vil resultaterne variere for hvert kald. Vi brugte en 16-bit hashfunktion. Vi ser, at det første estimat fra funktionen count_unique_using_array var, at listen indeholder 9289 unikke værdier. Dette estimat har vi præciseret med korrektionen til 10.017, hvilket er ret fint: vores estimat er kun 0,17 % for stort, mens det før var 7,11 % for lille — det er ret meget.

Hvis vi tog en »større« hashfunktion, fx en 24-bit, ville vi få et mere præcist resultat:

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

Allerede det oprindelige estimat var OK, og præciseringen nåede op på præcis ti tusind. Som demonstration kan vi prøve en million unikke ID'er, dvs. number_of_unique_values = 1000000. Med en 24-bit hashfunktion når vi frem til disse resultater:

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

Det går. Hvis vi implementerer det som et bitfelt, ville feltet kun æde de nævnte to megabyte (+ hvad sproget æder). For mig er det ret godt. But we can do better! Much better. Men det kommer først næste gang.

I mellemtiden kan du læse artiklen A Linear-Time Probabilistic Counting Algorithm for Database Applications [PDF]. Eller du kan fortsætte med næste del af serien: algoritmen min-value.