Min Value: Jak odhadnout počet unikátních hodnot

V minulém článku o Linear Countingu jsme si probrali základní algoritmy na výpočet a odhad počtu unikátních hodnot v nějaké sadě dat. Dnes náš čeká další pravděpodobností algoritmus, který umožňuje se slušnou přesností a malými paměťovými nároky odhadnout počet unikátů.

Min Value

V článku budeme pracovat pouze s reálnými čísly z jednotkového intervalu (0; 1). Představme si množinu čísel z tohoto intervalu, která je rovnoměrně rozložena, např. množina čísel {0,25; 0,5; 0,75}. Sousední čísla jsou vždy od sebe (a od nuly a od jedničky) vzdálena právě o 0,25. Jak nám to pomůže spočítat počet unikátních prvků?

Když vám řeknu, že máme takovou rovnoměrně rozloženou množinu čísel z jednotkového intervalu, a tato čísla mají mezi sebou vzdálenost právě 0,2 — vypočítáte, kolik prvků taková množina má? Samozřejmě, jedná se o množinu {0,2; 0,4; 0,6; 0,8}, jejíž kardinalita je rovna čtyřem. Máme-li na vstupu rovnoměrně rozložená čísla z jednotkového intervalu a známe-li vzdálenost sousedních čísel, jsme schopni snadno vypočítat počet prvků.

Přitom vzdálenost mezi sousedními čísly je rovna minimálnímu prvku množiny — vzdálenost sousedních prvků množiny {0,25; 0,5; 0,75} je 0,25 atp. Při vypočítávání počtu prvků rovnoměrně rozložených čísel nám stačí nějak zjistit minimální prvek. Pak můžeme vypočítat počet prvků p jednoduchým vzorcem:

$$\Large p=\frac{1}{m}-1$$

kde m je onen minimální prvek.

A zase budeme hashovat…

No jo, jenže jak toto využít, pokud máme na vstupu nějaké řetězce nebo jiné hodnoty, které zrovna nesplňují podmínku rovnoměrného rozložení do jednotkového intervalu? Pomůže si opět starou dobrou hashovací funkcí, která nám může pro libovolný vstup vrátit racionální číslo z jednotkového intervalu. Sestrojit takovou hashovací funkci bude snadné.

Tím bychom dostali z dat racionální čísla, ale jak zařídit, aby tato čísla byla rovnoměrně rozložená? To už sice nepůjde, ale můžeme si pomoci jinak. Hashovací funkce se totiž z našeho pohledu chová poměrně „náhodně“. Pro velmi podobná slova jako „ahoj“, „ahok“ a „ahol“ nám bude hashovací funkce nejspíš vracet velmi odlišné checksumy. Jinými slovy: pokud zahashujeme tisíc různých hodnot do jednotkového intervalu, je velice nepravděpodobné, aby výrazná většina čísel byla například menší než jedna polovina. Naopak je velmi pravděpodobné, že tato čísla budou rozložena více méně pravidelně. Čím více dat zahashujeme, tím to rozložení bude pravidelnější.

Z této myšlenky dostáváme jednoduchý algoritmus: projdeme vstupní data, každý prvek zahashujeme do jednotkového intervalu a zapamatujeme si minimální prvek. Počet unikátních prvků odhadneme podle předchozího vzorce. Implementace v Pythonu:

from uuid import uuid4

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

def unit_interval_hash(item, n):
    integer_hash = nhash(item, n) + 1
    return integer_hash / float(2 ** n)

def count_unique_using_minimum(values, n):
    numbers_from_unit_interval = (unit_interval_hash(item, n) for item in values)
    minimum = min(numbers_from_unit_interval)
    return int(1 / minimum) - 1

for _ in xrange(10):
    print count_unique_using_minimum((uuid4() for _ in xrange(10000)), 16)

Funkce unit_interval_hash nám vrací desetinné číslo z intervalu (0, 1>. Funkce count_unique_using_minimum nejprve převede všechny vstupní hodnoty právě na toto číslo, nalezne minimum a vrací 1 / minimum - 1. Všimněte si, že vůbec nezáleží na tom, kolik je v sadě dat stejných hodnot — pro dvě stejné hodnoty nám hashovací funkce vrátí stejné racionální číslo, což nám nijak neovlivní výsledné minimum. Proto tímto algoritmem spočítáme počet unikátních prvků.

Jaké jsou výsledky? (Na každém řádku je odhadnutá kardinalita, správná kardinalita je přitom 10 000.)

5957
16384
13107
9362
65536
8192
21845
13107
21845
8192

No, nic moc, že? Algoritmus projel deset různých sad idéček, ve kterých bylo vždy deset tisíc unikátních hodnot. Vypočtené odhady jsou tak většinou dost mimo. Pokud bychom je zprůměrovali, dostali bychom se k hodnotě 18 352. Pořád je dost mimo, na druhou stranu si vemte paměťové nároky — jsou konstantní! Na to, abyste nalezli minimum, vám stačí si v paměti vždy uchovávat jednu proměnnou, do které uložíte aktuální minimum a to je vše. Takže jo, odhad na prd, ale zase skoro nic nestojí.

Vylepšujeme

Vidíme, že algoritmus je především nestabilní — jednou nám vrátí celkem dobrý odhad (9362), podruhé nám vrátí odhad, který je úplně mimo (65536). Jak z toho ven? Můžeme si pomoci tím, že rozdělíme vstupní data do několika částí a spočítáme počet unikátních prvků pro každou část a nakonec všechno hezky zprůměrujeme. Mohli bychom se rozhodnout podle prvního znaku v našem idéčku. Takže spočítáme zvlášť počet unikátů pro idéčka, která začínají na písmena „a“, pak pro ty, které začínají na písmeno „b“ atp. Kód:

from uuid import uuid4

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

def unit_interval_hash(item, n):
    integer_hash = nhash(item, n) + 1
    return integer_hash / float(2 ** n)

def count_unique_using_minimum(values, n):
    min_values = {}
    for item in values:
        first_char = str(item)[0]
        hashed_value = unit_interval_hash(item, n)
        min_values[first_char] = min(min_values.get(first_char, 1), hashed_value)
    average_minimum = sum(min_values.values()) / len(min_values)
    return (int(1 / average_minimum) - 1) * len(min_values)

for _ in xrange(10):
    print count_unique_using_minimum((uuid4() for _ in xrange(10000)), 16)

Změny jsou ve funkci count_unique_using_minimum. V proměnné min_values si uchováváme minima pro každou skupinu. Na konci sečteme všechna minima a vydělíme je počtem všech uložených hodnot — získáme průměrné minimum. Výrazem 1/average_minimum zjistíme, jaký je průměrný počet unikátních hodnot v každé skupině — tuto hodnotu tak ještě vynásobíme počtem skupin a získáme odhadnutý počet unikátních hodnot v předané sadě dat. A jak tento upravený postup funguje?

11312
7504
10560
8160
9344
12688
10976
11616
16240
6832

No, pořád to není dobré, ale je to určitě lepší. Algoritmus je stabilnější. Můžeme zkusit upravit funkci tak, aby se skupiny netvořily podle prvního znaku, ale například podle dvou prvních znaků idéčka, tj. takto:

first_char = str(item)[0:2] # ToDo: choose better name for variable

Výsledky by potom byly takovéto:

9728
9728
9984
10240
8960
10752
9728
9472
11264
9472

Nooo to už není úplně špatné, ne? Pokud ještě zkusíme sto tisíc unikátních hodnot, první dva znaky a n = 24, dostaneme tyto výsledky:

103936
110080
102656
101120
101376
108288
97536
97024
107776
92416

Docela to ujde. Ale stále existují lepší algoritmy, nebojte.

A jaká je paměťová náročnost? Musíme si uchovávat minimum pro každou skupinu, nic víc. Pokud máme idéčka v hex formátu, tak to znamená, že si musíme pamatovat maximálně 16^x minim, kde x je počet znaků, ze kterých tvoříme klíč skupiny. Jedno minimum je jedno racionální číslo, tj. nějaký typ double nebo float.

Poznámka na konec: rozdělení vstupu do několika skupin jsme si mohli dovolit proto, že jsme na vstupu měli idéčka, která se chovala jako náhodný řetězec. Pokud bychom neměli na vstupu náhodný řetězec, ale nějaká data v určitém formátu, museli bychom rozdělení udělat jinak. Pokud by například každé idéčko začínalo prefixem userid-, tak by asi rozdělení do skupin podle prvního znaku moc nefungovalo, žeano.