✖

LogLog: Jak oszacować liczbę unikalnych wartości

Kapitoly: Liczenie liniowe: jak oszacować liczbę unikalnych wartości, Min Value: Jak oszacować liczbę unikalnych wartości, LogLog: Jak oszacować liczbę unikalnych wartości, HyperLogLog: Jak oszacować liczbę unikalnych wartości

Po poprzednich artykułach na temat liczenia liniowego i wartości minim alnej, w końcu dochodzimy do prawie najlepszego algorytmu probabilistycznego do szacowania liczby unikalnych wartości w zbiorze danych, LogLog. Jedyną lepszą rzeczą jest jego mniejszy brat HyperLogLog, który bazuje na LogLog, ale o tym następnym razem.

Powtórzmy opis problemu. Na wejściu mamy jakiś zbiór danych, na przykład tablicę/generator identyfikatorów. W tym polu znajduje się kilka wartości i chcemy policzyć liczbę unikalnych wartości w tym polu. Liczbę tę nazwiemy kardynalnością. Oczekujemy, że ta kardynalność będzie naprawdę duża, w przeciwnym razie możemy użyć konwencjonalnych algorytmów.

Idea stojąca za algorytmem LogLog

Wyobraźmy sobie, że mamy zbiór wektorów binarnych. Nie przejmuj się, na przykład ten 0001011001001100 jest wektorem binarnym o długości 16. Załóżmy, że mamy wektory binarne o długości 32 i że mamy ich w sumie milion, wszystkie całkowicie losowo wygenerowane. Ile wektorów zakończy się zerem?

Oczywiście nie wiemy tego dokładnie, ale jeśli naprawdę wygenerowaliśmy wektory losowo, to około połowa z nich powinna kończyć się zerem, czyli 500 000. Ile wektorów zakończy się liczbą 00? Jedna czwarta. 000? Osiem. I tak dalej. Możemy to przedstawić mniej więcej w ten sposób:

proporcja wzorca wektorowego wśród wszystkich wektorów ...xxxxxx0 50% ...xxxxx00 25% ...xxxx000 12,5% ...xxx0000 6,25% ... ....

Jeśli poprosimy o sufiks (sufiks to ciąg kończący inny ciąg - przeciwieństwo prefiksu) o długości d, spodziewamy się znaleźć wektory kończące się tym sufiksem. Obliczamy wartość v jako:

$$\Large v=\frac{1}{2^d}\cdot N$$

gdzie N jest liczbą wszystkich wektorów w zbiorze. Sufiks o długości 3 (np. ...010) powinien wystąpić w 1/2^3 N = 1/8 N wektorów, tj. 12,5% wszystkich wektorów.

Teraz zróbmy mały mindfuck. Miejmy multizbiór 1024 unikalnych wektorów. Ile wektorów powinno kończyć się sufiksem 0000000000?

$$v=\frac{1}{2^{10}}\cdot1024=\frac{1}{1024}\cdot1024=1$$

Huh, jeden! W tysiącu losowo wygenerowanych wektorów binarnych powinien być dokładnie jeden wektor zakończony dziesięcioma zerami. A jak wykorzystać tę informację do oszacowania liczby unikalnych elementów? Ponieważ możemy zrobić odwrotnie. Co jeśli przejdziemy przez wszystkie wektory binarne, które mamy na wejściu i stwierdzimy, że w zestawie jest jeden wektor, który kończy się dziesięcioma zerami? Wtedy możemy oszacować, że w zbiorze było 1024 wektorów!

Uogólniamy i konstruujemy algorytm

Celem powinno być znalezienie sufiksu, który jest zawarty tylko w jednym wektorze, a ten sufiks jest tak krótki, jak to możliwe. Jest to jednak bardzo trudne, ponieważ aby faktycznie znaleźć taki wektor, musielibyśmy przechowywać wszystkie sufiksy, czego nie chcemy robić, ponieważ zajęłoby to zbyt dużo pamięci. Zamiast tego zadowalamy się szukaniem najdłuższej sekwencji zer na końcu wektora.

Przejdziemy więc przez wszystkie wektory, policzymy dla każdego z nich ile zer zawiera na końcu i zapiszemy maksymalną z tych wartości w jednej zmiennej. Gdy przejdziemy przez wszystkie wektory, poznamy długość najdłuższego sufiksu, który składa się wyłącznie z zer. Oznaczamy tę długość przez d. Zmodyfikujemy teraz poprzedni wzór, aby odizolować zmienną N, tj. uczynić ją wyjściem algorytmu, a nie danymi wejściowymi. Czyniąc to, możemy zastąpić jeden zamiast v, ponieważ spodziewamy się znaleźć tylko jeden taki wektor, tj. spodziewamy się, że v=1.

$$\begin{eqnarray} v&=&\frac{N}{2^d}\\ v\cdot2^d&=&N\\ 2^d&=&N \end{eqnarray}$$

Tak więc, jeśli znajdziemy długość d najdłuższego sufiksu zerowego, oszacujemy kardynalność za pomocą wzoru N=2d.

Jak uzyskać losowe wektory binarne?

Algorytm działa już z losowymi wektorami binarnymi, ale jak zastosować go do rzeczywistych danych? Jak zwykle używamy odpowiedniej funkcji skrótu. Jeśli na wejściu mamy zestaw danych, na przykład identyfikatory (ciągi znaków), najpierw je haszujemy. Wyjściem n-bitowej funkcji haszującej jest n bitów, które z praktycznego punktu widzenia wyglądają jak losowo wygenerowane wektory binarne.

W tym momencie możemy 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(zeros_length, max_zero_suffix_length) return 2 ** max_zero_suffix_length.

Funkcja trailing_zeroes zwraca liczbę zer na końcu liczby. W jaki sposób to robi? Jeśli nie dowiedziałeś się tego z kodu, nawet nie pytaj. A jaki jest współczynnik sukcesu tej funkcji? Dla zbioru, który zawierał 100 000 unikalnych elementów, funkcja zwróciła szacunkową liczbę 524 288.

Cóż...

To nie do końca dobrze, prawda? Ale nie szkodzi! Spróbujmy ulepszyć algorytm w taki sam sposób, jak poprzednio Min Value. Podzielimy dane wejściowe na kilka rozłącznych grup i obliczymy maksymalny sufiks zerowy dla każdej grupy, a na koniec obliczymy średnią długość sufiksu zerowego i wykorzystamy ją do oszacowania liczby unikatów.

Na przykład możemy powiedzieć, że ostatnie dwa bity każdego wektora określą numer grupy, do której należy wektor. Sześć wektorów

1101110111111011 1110110010100101 1011001111110010 1111101100000011 1010101000100000 0110010110011000

można podzielić na cztery grupy na podstawie ich końcówek:

00011010101000100000 1110110010100101011001011001100010111011001111110010 1101110111111011 1111101100000011

Następnie obliczamy długość najdłuższego zerowego sufiksu w każdym wektorze, ale pomijamy bity, których użyliśmy jako numeru grupy. Zerowe "sufiksy" zaznaczamy na zielono:

00 011010101000100000 1110110010100101 011001011001100010111011001111110010 1101110111111011111110110000001100:3 01: 0 10: 2 11: 6

Na końcu znajdują się najdłuższe sufiksy zerowe z tej grupy. Na podstawie tych sufiksów możemy obliczyć średnią arytmetyczną, która wynosi 2,75. Wstawiamy tę wartość do wzoru i otrzymujemy

$$2^{2{,}75}\approx6{,}727$$

Otrzymujemy średnią liczbę unikalnych elementów w każdej grupie. Co oczywiście w ogóle nie pasuje, ale nie przejmujmy się tym, dla małych zbiorów algorytm LogLog daje fatalne wyniki.

Aby oszacować kardynalność całego zbioru, musimy jeszcze pomnożyć tę wartość przez liczbę grup: 6,727 · 4 = 26,908. Algorytm oblicza, że w zbiorze jest około 27 unikalnych wartości. W rzeczywistości było ich sześć, więc wynik jest całkowicie błędny, ale nie ma to teraz większego znaczenia.

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 jest branych jako indeks grupy. Parametr ten określa dokładność algorytmu - im wyższe k, tym wyższa dokładność. Zmienna bucket_index przechowuje numer grupy. Jak działa magia po prawej stronie równania?

Zmienna num_buckets przechowuje liczbę grup, która zawsze jest potęgą dwójki. Jeśli na przykład k = 3, to num_buckets = 8. Liczba 8 ma postać 1000 w systemie binarnym. Jeśli odejmiemy jeden, otrzymamy liczbę 7, która ma postać 0111. Odejmowanie jedynki od num_buckets zawsze daje liczbę, która ma k jedynek na końcu i wszystkie zera przed nią. Następnie wykonujemy iloczyn logiczny (czyli operator &). W przypadku wektora 1110110010100101 operacja ta wyglądałaby następująco:

 1110110010100101 & 0000000000000111 ------------------ 0000000000000101

Celem całej tej magii jest uzyskanie liczby, która zawiera wszystkie zera na początku i ma ostatnie k bitów takich samych jak podany hash h.

Następnie obliczamy bucket_hash, który jest oryginalnym hashem, z którego usuwamy ostatnie k bitów, przesuwając cały hash o k bitów w prawo. Przesunięcie polega po prostu na przesunięciu wszystkich bitów w liczbie k bitów w prawo i wypełnieniu liczby zerami od lewej strony (przesunięcie bitu w prawo o jeden zachowuje się tak samo, jak podzielenie liczby przez dwa i odrzucenie reszty). Z wektora 1110110010100101 otrzymalibyśmy 0001110110010100 po przesunięciu o trzy. Wektor ten zostanie zapisany w zmiennej bucket_hash.

Następnie zliczamy liczbę zer na końcu tego wektora i jeśli wartość ta jest większa niż bieżąca maksymalna wartość przechowywana w polu max_zeroes w bucket_index, nadpisujemy tę wartość.

Na koniec po prostu liczymy średnią liczbę zer we wszystkich grupach i obliczamy średnią liczbę unikalnych elementów w każdej grupie(2 ** średnia_max_zeros). Ponieważ mamy w sumie num_buckets grup, mnożymy tę wartość przez liczbę grup, aby uzyskać ostateczne oszacowanie liczby unikalnych elementów. Ugh, i to też nie zaszkodziło. Wyniki dla kilku zestawów danych zawierających 250 000 unikatów i k=10:

331774.56203 323349.39265 307343.444439 309430.914045 294512.379123

Nieee, wciąż źle :-(. Ale jesteśmy całkiem blisko, nie martw się. Zauważ, że wszystkie wyniki są większe niż prawidłowy wynik. Wynika to z faktu, że podczas algorytmu kumulują się różne błędy, przez co oszacowanie jest zauważalnie większe niż prawidłowy wynik. Błędy te są jednak dość stałe i możliwe jest oszacowanie, jak duży był błąd. Kiedy pomnożymy oszacowanie przez hausnumer 0.79402, otrzymamy wyniki, które są znacznie lepsze:

263435.63774306054 256745.88475195298 244036.84175345476 245694.33437001088 233848.71927124445

Wypróbowałem inny multiset, który ma kardynalność miliona, wyniki:

Wynik Błąd 1017297.17411 1.01729717411 1022820.99717 1.02282099717 984108.725487 0.984108725487 1018675.32683 1.01867532683 1007020.2853 1.0070202853

Ładnie i ładnie! Błąd wynosi poniżej 2%, co jest przyzwoitym wynikiem. I to, panie i panowie, jest algorytm LogLog. Ostateczna implementacja z hausnumber wygląda następująco:

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 zmodyfikować ten algorytm, aby uzyskać ten mityczny i najlepszy HyperLogLog, powiemy następnym razem. Na razie przyjrzyjmy się, jak bardzo pamięciożerny jest ten algorytm.

Zapotrzebowanie na pamięć

Algorytm jest bardzo wydajny pamięciowo. Jedyną rzeczą, o której musimy pamiętać, jest tablica przechowująca maksima. Długość tej tablicy zależy od wartości k, czyli liczby bitów z wektora, które przyjmujemy jako indeks grupy. Dla danego k mamy w sumie 2k różnych grup, a zatem tablica maksimów ma długość 2k. W implementacji nazwaliśmy tę wartość num_buckets.

Jak duża musi być jedna komórka tablicy? Będziemy w niej przechowywać długości sufiksów null. Z góry mogę powiedzieć, że 64-bitowy hash jest prawdopodobnie wystarczający dla każdego możliwego multizbioru na świecie, więc musimy być w stanie przechowywać w tej tablicy liczby od 0 (wektor wszystkich jedynek) do 64 (wektor wszystkich zer). Co więcej, jeśli założymy, że k zawsze będzie większe od zera, to wystarczy przechowywać liczby od 0 do 63. Do tego potrzebujemy tylko 6 bitów, ponieważ 26 = 64.

Tak, potrzebujemy tylko "tablicy", w której jedna komórka ma rozmiar 6 bitów. Mogę również powiedzieć, że k = 10 wystarczy, aby dać nam całkiem dobre oszacowanie kardynalności rzędu setek milionów. Algorytm skonfigurowany w ten sposób wygenerowałby tablicę o rozmiarze 210 = 1024, w której każda komórka zajmuje 6 bitów. W sumie tablica ta zajmowałaby 6144 bity, czyli 768 bajtów. Nawet nie kilobajt.

I to by było na tyle.

Nie musimy przechowywać niczego więcej, możemy od razu odrzucić obliczone hashe, musimy tylko znać liczbę zer na końcu wektora.

Zauważ, że gdybyś użył większej funkcji haszującej, która zwróciłaby na przykład 128 bitów, ślad pamięci nie zmieniłby się zbytnio. W rzeczywistości musielibyśmy przechowywać liczby od 0 do 127, dla których potrzebujemy tylko 7 bitów. Tak więc zapotrzebowanie na pamięć zależy głównie od parametru k, czyli liczby grup.

LogLog jest szczególnie przydatny, gdy musimy obliczyć multizbiory o naprawdę dużej kardynalności. Jak widać na powyższym prostym przykładzie, LogLog nie radzi sobie idealnie z multizbiorami o małej liczności. Można jednak temu zaradzić, na przykład używając innego algorytmu do oszacowania, jeśli okaże się, że multizbiór ma niską liczność, takiego jak opisany wcześniej algorytm liczenia liniowego. Zostanie to również omówione następnym razem.

Zasoby: