LogLog: jak oszacować liczbę unikalnych wartości
Kapitoly: Linear Counting, Min Value, LogLog, HyperLogLog
Po poprzednich częściach o Linear Counting i Min Value dochodzimy wreszcie do prawie najbardziej najlepszego probabilistycznego algorytmu do szacowania liczby unikalnych wartości w zbiorze danych, LogLogu. Lepszy jest już tylko jego braciszek HyperLogLog, który wywodzi się z LogLogu, ale o nim następnym razem.
Powtórzmy sobie, na czym polega problem. Na wejściu mamy jakiś zbiór danych/multizbiór, na przykład jakąś tablicę/generator identyfikatorów. W tej tablicy niektóre wartości występują wielokrotnie, a my chcemy policzyć, ile unikalnych wartości jest w tej tablicy. Tę liczbę będziemy nazywać licznością (kardynalnością). Spodziewamy się, że ta liczność będzie naprawdę duża, w przeciwnym razie możemy użyć konwencjonalnych algorytmów.
Idea algorytmu LogLog
Wyobraźmy sobie, że mamy zestaw wektorów binarnych. Nie przestrasz się, na przykład 0001011001001100 to wektor binarny o długości 16. Powiedzmy, że mamy wektory binarne o długości 32 i że mamy ich w sumie milion, wszystkie całkowicie losowo wygenerowane. Ile wektorów będzie się kończyć cyfrą zero?
Tego oczywiście nie możemy wiedzieć dokładnie, ale jeśli te wektory naprawdę generowaliśmy losowo, zerem powinna się ich kończyć mniej więcej połowa, tzn. 500 tysięcy. Ile wektorów będzie się kończyć na 00? Ćwierć. Na 000? Jedna ósma. I tak dalej. Możemy to przedstawić mniej więcej tak:
wzór wektora udział wśród wszystkich wektorów
...xxxxxx0 50%
...xxxxx00 25%
...xxxx000 12,5%
...xxx0000 6,25%
... ...
Jeśli zapytamy o sufiks (sufiks to napis, którym kończy się inny napis — przeciwieństwo prefiksu) o długości d, spodziewamy się, że znajdziemy v wektorów, które kończą się tym sufiksem. Wartość v obliczymy jako:
$$\Large v=\frac{1}{2^d}\cdot N$$
gdzie N jest liczbą wszystkich wektorów w zestawie. Sufiks o długości 3 (na przykład …010) powinien występować w 1/2^3 N = 1/8 N wektorów, tzn. w 12,5% wszystkich wektorów.
Teraz zrobimy taki mały mindfuck. Weźmy multizbiór 1024 unikalnych wektorów. Ile wektorów powinno się kończyć sufiksem 0000000000? (dziesięć zer) Podstawimy do wzoru i wyjdzie nam
$$v=\frac{1}{2^{10}}\cdot1024=\frac{1}{1024}\cdot1024=1$$
Hm, jeden! Wśród tysiąca losowo wygenerowanych wektorów binarnych powinien być dokładnie jeden wektor, który kończy się dziesięcioma zerami. A jak tę informację wykorzystać do oszacowania liczby unikalnych elementów? Możemy przecież postępować odwrotnie. Co jeśli przejdziemy przez wszystkie wektory binarne, które mamy na wejściu, i stwierdzimy, że w zestawie jest jedyny wektor, który kończy się dziesięcioma zerami? Wtedy przecież możemy oszacować, że w zestawie były 1024 wektory!
Uogólniamy i układamy algorytm
Celem powinno być znalezienie takiego sufiksu, który występuje tylko w jednym wektorze, przy czym ten sufiks jest możliwie najkrótszy. To jednak bardzo trudne, bo żeby naprawdę znaleźć taki wektor, musielibyśmy zapisywać wszystkie sufiksy, a tego nie chcemy, bo zajęłoby to zbyt dużo pamięci. Zamiast tego zadowolimy się tym, że będziemy szukać najdłuższego ciągu zer na końcu wektora.
Przejdziemy więc przez wszystkie wektory, dla każdego wektora policzymy, ile zer ma na końcu, i w jednej zmiennej będziemy przechowywać maksimum z tych wartości. Kiedy przejdziemy przez wszystkie wektory, będziemy znać długość najdłuższego sufiksu złożonego z samych zer. Tę długość oznaczamy literą d. Teraz przekształcimy poprzedni wzór tak, żeby wyznaczyć zmienną N, tzn. żeby była wyjściem algorytmu, a nie wejściem. Przy tym zamiast v możemy podstawić jeden, bo spodziewamy się, że znajdziemy dokładnie jeden taki wektor, tzn. spodziewamy się, że będzie zachodzić v=1.
$$\begin{eqnarray} v&=&\frac{N}{2^d}\\ v\cdot2^d&=&N\\ 2^d&=&N \end{eqnarray}$$
Jeśli więc znajdziemy długość d najdłuższego zerowego sufiksu, oszacujemy liczność za pomocą wzoru N=2d.
Jak zdobyć losowe wektory binarne?
Z losowymi wektorami binarnymi algorytm już nam działa, ale jak to podejście zastosować do prawdziwych danych? Jak zwykle i tu użyjemy jakiejś odpowiedniej funkcji haszującej. Jeśli na wejściu mamy zbiór danych, na przykład identyfikatory (stringi), to najpierw je zahaszujemy. Wynikiem n-bitowej funkcji haszującej jest n bitów, które z praktycznego punktu widzenia wyglądają jak losowo wygenerowane wektory binarne.
W tej chwili możemy już napisać nasz algorytm:
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
Funkcja trailing_zeroes zwraca liczbę zer na końcu liczby. Jak to robi? Jeśli nie zrozumiałeś tego z kodu, to lepiej nawet nie pytaj. A jaką skuteczność ma ta funkcja? Dla zbioru, który zawierał sto tysięcy unikalnych elementów, funkcja zwróciła oszacowanie 524 288.
No…
No, nie jest to całkiem dobre, prawda? Ale nic nie szkodzi! Spróbujemy ulepszyć algorytm dokładnie tak samo jak poprzedni Min Value. Podzielimy dane wejściowe na kilka rozłącznych grup, dla każdej grupy policzymy maksymalny zerowy sufiks, a na koniec policzymy średnią długość zerowego sufiksu i użyjemy jej do oszacowania liczby unikalnych wartości.
Możemy na przykład ustalić, że ostatnie dwa bity każdego wektora będą wyznaczać numer grupy, do której wektor należy. Tych sześć wektorów
1101110111111011 1110110010100101
1011001111110010 1111101100000011
1010101000100000 0110010110011000
możemy podzielić na cztery grupy według tego, jaką mają końcówkę:
00 01 1010101000100000 1110110010100101 0110010110011000 10 11 1011001111110010 1101110111111011 1111101100000011
Dalej policzymy długość najdłuższego zerowego sufiksu w każdym wektorze, przy czym pominiemy te bity, których użyliśmy jako numeru grupy. Zerowe „sufiksy” zaznaczymy na zielono:
00 01 1010101000100000 1110110010100101 0110010110011000 10 11 1011001111110010 1101110111111011 1111101100000011 00: 3 01: 0 10: 2 11: 6
Na końcu są długości najdłuższych zerowych sufiksów z danej grupy. Z tych długości możemy obliczyć średnią arytmetyczną, która wyjdzie nam 2,75. Wartość podstawimy do wzoru i wyjdzie nam
$$2^{2{,}75}\approx6{,}727$$
Otrzymujemy średnią liczbę unikalnych elementów w każdej grupie. Co oczywiście zupełnie się nie zgadza, ale nie przejmujmy się tym, dla małych zbiorów algorytm LogLog daje okropne wyniki.
Żeby oszacować liczność całego zbioru, musimy jeszcze tę wartość pomnożyć przez liczbę grup: 6,727 · 4 = 26,908. Algorytm obliczył, że w zestawie jest około 27 unikalnych wartości. Było ich tam sześć, więc to zupełnie chybione, ale to teraz naprawdę nie szkodzi.
Implementacja algorytmu
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
Parametr k określa, ile bitów będzie brane jako indeks grupy. Ten parametr wyznacza dokładność algorytmu — im wyższe k, tym większa dokładność. W zmiennej bucket_index jest przechowywany numer grupy. Jak działa ta magia po prawej stronie znaku równości?
W zmiennej num_buckets jest liczba grup, która jest zawsze potęgą liczby dwa. Jeśli na przykład k = 3, to num_buckets=8. Liczba 8 ma w systemie dwójkowym postać 1000. Jeśli odejmiemy jedynkę, dostaniemy liczbę 7, która ma postać 0111. Po odjęciu jedynki od num_buckets zawsze dostaniemy liczbę, która ma na końcu k jedynek, a przed nimi same zera. Dalej wykonamy iloczyn bitowy (bitowe AND, operator &). Dla wektora 1110110010100101 ta operacja wyglądałaby tak:
1110110010100101
& 0000000000000111
------------------
0000000000000101
Celem całej tej magii jest to, żebyśmy dostali liczbę, która na początku ma same zera, a ostatnie k bitów ma takie same jak dany hasz h.
Dalej obliczymy bucket_hash, czyli pierwotny hasz, z którego usuniemy ostatnie k bitów w ten sposób, że cały hasz przesuniemy o k bitów w prawo. Przesunięcie działa tak, że po prostu wszystkie bity w liczbie przesuwa o k bitów w prawo, a z lewej liczbę uzupełnia zerami. (Przesunięcie bitowe w prawo o jeden działa tak samo, jakbyś liczbę podzielił przez dwa i odrzucił resztę.) Z wektora 1110110010100101 po przesunięciu o trzy dostalibyśmy 0001110110010100. Ten wektor zostałby zapisany w zmiennej bucket_hash.
Dalej policzymy liczbę zer na końcu tego wektora i jeśli ta wartość jest większa niż obecna maksymalna wartość zapisana w tablicy max_zeroes pod indeksem bucket_index, nadpiszemy ją.
Na końcu już tylko obliczymy średnią liczbę zer we wszystkich grupach i obliczymy, jaka jest średnia liczba unikalnych elementów w każdej grupie (2 ** average_max_zeros). Ponieważ mamy w sumie num_buckets grup, pomnożymy tę wartość właśnie przez liczbę grup i w ten sposób otrzymamy końcowe oszacowanie liczby unikalnych elementów. Uff, i nawet nie bolało. Wyniki dla kilku zbiorów danych, które zawierają 250 000 unikalnych wartości, i k=10:
331774.56203
323349.39265
307343.444439
309430.914045
294512.379123
Nieeee, wciąż źle :-(. Ale jesteśmy już całkiem blisko, bez obaw. Zauważ, że wszystkie wyniki są większe niż prawidłowy wynik. W trakcie działania algorytmu nagromadzą się bowiem różne błędy i oszacowanie jest dlatego wyraźnie większe niż prawidłowy wynik. Te błędy są jednak dość stałe i można oszacować, jak duży błąd powstał. Kiedy oszacowanie pomnożymy przez magiczną stałą 0.79402, otrzymamy wyniki, które są zasadniczo lepsze:
263435.63774306054
256745.88475195298
244036.84175345476
245694.33437001088
233848.71927124445
Spróbowałem jeszcze multizbioru, który ma liczność milion, wyniki:
Wynik Błąd
1017297.17411 1.01729717411
1022820.99717 1.02282099717
984108.725487 0.984108725487
1018675.32683 1.01867532683
1007020.2853 1.0070202853
Pięknie! Błąd nie przekracza 2,5%, co jest przyzwoitym wynikiem. I to jest, panie i panowie, algorytm LogLog. Końcowa implementacja razem z magiczną stałą wygląda tak:
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
Jak zmienić ten algorytm, żeby otrzymać ów legendarny i najbardziej najlepszy HyperLogLog, powiemy sobie następnym razem. Na razie przyjrzymy się temu, ile algorytm zużywa pamięci.
Zużycie pamięci
Algorytm jest bardzo oszczędny, jeśli chodzi o zajętą pamięć. Jedyne, co musimy pamiętać, to tablica przechowująca maksima. Długość tej tablicy zależy od wartości k, tzn. od liczby bitów wektora, które bierzemy jako indeks grupy. Dla danego k mamy w sumie 2k różnych grup i tablica maksimów ma dlatego długość 2k. Tę wartość nazywaliśmy w implementacji num_buckets.
Jak duża musi być jedna komórka tablicy? Będziemy w niej zapisywać długości zerowych sufiksów. Mogę ci z góry zdradzić, że 64-bitowy hasz wystarczy najpewniej dla wszystkich wyobrażalnych multizbiorów świata, więc w tej tablicy musimy móc zapisać liczby od 0 (wektor złożony z samych jedynek) do 64 (wektor złożony z samych zer). Dalej, jeśli założymy, że k będzie zawsze większe od zera, to wystarczy nam zapisywać liczby od 0 do 63. Do tego, proszę uprzejmie, wystarczy nam 6 bitów, bo 26 = 64.
Tak, wystarczy nam „tablica”, w której jedna komórka ma rozmiar 6 bitów. Dalej mogę ci zdradzić, że wartość k=10 wystarczy, żebyśmy całkiem przyzwoicie oszacowali liczność do rzędu setek milionów. Tak ustawiony algorytm utworzyłby tablicę o rozmiarze 210 = 1024, w której każda komórka zajmuje 6 bitów. W sumie ta tablica zajmowałaby 6144 bity, czyli 768 bajtów. Nawet nie kilobajt.
I to wszystko.
Niczego innego zapisywać nie potrzebujemy, obliczone hasze możemy od razu wyrzucać, wystarczy nam znać liczbę zer na końcu wektora.
Zauważ, że gdybyś użył większej funkcji haszującej, która zwracałaby na przykład 128 bitów, zużycie pamięci zmieniłoby się niewiele. Potrzebowalibyśmy bowiem zapisać liczby od 0 do 127, do czego wystarczy nam 7 bitów. Zużycie pamięci wyznacza więc przede wszystkim parametr k, tzn. liczba grup.
LogLog nadaje się przede wszystkim tam, gdzie potrzebujemy liczyć multizbiory o naprawdę dużej liczności. Jak było widać nawet na prostym przykładzie powyżej, LogLog nie radzi sobie najlepiej z multizbiorami, które mają małą liczność. Można temu jednak zaradzić na przykład tak, że jeśli stwierdzimy, że multizbiór ma niską liczność, użyjemy do oszacowania innego algorytmu, na przykład opisanego już wcześniej Linear Counting. O tym też będzie mowa następnym razem.
Źródła:
- Loglog Counting of Large Cardinalities [PDF]
- Damn Cool Algorithms: Cardinality Estimation (stąd jest mniej więcej ściągnięty kod LogLogu)