Jak działa algorytm HyperLogLog?

W wolnym czasie poznałem różne algorytmy, a jeden z nich, który wydaje mi się bardzo interesujący, nazywa się algorytmem HyperLogLog - który szacuje, ile unikalnych elementów znajduje się na liście.

Było to dla mnie szczególnie interesujące, ponieważ wróciłem do czasów MySQL, kiedy zobaczyłem wartość „Kardynalności” (którą zawsze zakładałem do niedawna, że ​​jest obliczana, a nie szacowana).

Więc wiem, jak napisać algorytm w O ( n ), który obliczy, ile unikalnych elementów znajduje się w tablicy. Napisałem to w JavaScript:

function countUniqueAlgo1(arr) {
    var Table = {};
    var numUnique = 0;
    var numDataPoints = arr.length;
    for (var j = 0; j < numDataPoints; j++) {
        var val = arr[j];
        if (Table[val] != null) {
            continue;
        }
        Table[val] = 1;
        numUnique++;
    }
    return numUnique;
}

Ale problem polega na tym, że mój algorytm, podczas gdy O ( n ), zużywa dużo pamięci (przechowuje wartości Table).

Czytałem ten artykuł o tym, jak liczyć duplikaty na liście w czasie O ( n ) i używając minimalnej pamięci.

Wyjaśnia, że ​​przez haszowanie i liczenie bitów lub coś, co można oszacować z pewnym prawdopodobieństwem (zakładając, że lista jest równomiernie rozłożona), liczbę unikalnych pozycji na liście.

Przeczytałem gazetę, ale nie mogę jej zrozumieć. Czy ktoś może wyjaśnić bardziej laika? Wiem, co to są skróty, ale nie rozumiem, jak są używane w tym algorytmie HyperLogLog.

Główną sztuczką tego algorytmu jest to, że jeśli obserwując strumień losowych liczb całkowitych, zobaczysz liczbę całkowitą, której reprezentacja binarna zaczyna się od jakiegoś znanego przedrostka, istnieje większa szansa, że ​​liczność strumienia wynosi 2 ^ (rozmiar przedrostka) .

Oznacza to, że w losowym strumieniu liczb całkowitych ~ 50% liczb (binarnie) zaczyna się od „1”, 25% zaczyna się od „01”, 12,5% zaczyna się od „001”. Oznacza to, że jeśli zaobserwujesz losowy strumień i zobaczysz „001”, istnieje większe prawdopodobieństwo, że ten strumień ma liczność 8.

(Przedrostek „00..1” nie ma specjalnego znaczenia. Występuje tylko dlatego, że w większości procesorów łatwo jest znaleźć najbardziej znaczący bit w liczbie binarnej)

Oczywiście, jeśli zaobserwujesz tylko jedną liczbę całkowitą, prawdopodobieństwo, że ta wartość jest błędna, jest duże. Dlatego algorytm dzieli strumień na niezależne podstrumienie „m” i zachowuje maksymalną długość widzianego przedrostka „00 ... 1” każdego podstrumienia. Następnie szacuje wartość końcową, biorąc średnią wartość każdego podstrumienia.

To główna idea tego algorytmu. Brakuje pewnych szczegółów (na przykład korekta na niskie wartości szacunkowe), ale wszystko jest dobrze napisane w artykule. Przepraszam za okropny angielski.

HyperLogLog to probabilistyczna struktura danych . Zlicza liczbę różnych elementów na liście. Ale w porównaniu z prostym sposobem robienia tego (posiadanie zestawu i dodawanie elementów do zestawu) robi to w przybliżony sposób.

Zanim przyjrzymy się, jak robi to algorytm HyperLogLog, należy zrozumieć, dlaczego jest to potrzebne. Problem z prostym sposobem polega na tym, że zajmuje O(distinct elements)miejsce. Dlaczego występuje tutaj duża notacja O zamiast tylko odrębnych elementów? Dzieje się tak, ponieważ elementy mogą mieć różne rozmiary. Jeden element może być 1innym elementem "is this big string". Więc jeśli masz ogromną listę (lub ogromny strumień elementów), zajmie to dużo pamięci.

Liczenie probabilistyczne

Jak uzyskać rozsądną ocenę liczby unikalnych elementów? Załóżmy, że masz ciąg o długości mskładającej się z {0, 1}z równym prawdopodobieństwem. Jakie jest prawdopodobieństwo, że zacznie się od 0, od 2 zer i k zer? Jest 1/2, 1/4i 1/2^k. Oznacza to, że jeśli napotkałeś łańcuch z kzerami, przejrzałeś w przybliżeniu 2^kelementy. Więc to jest dobry punkt wyjścia. Mając listę elementów, które są równomiernie rozłożone pomiędzy 0i 2^k - 1można policzyć maksymalną liczbę największego prefiksu zer w reprezentacji binarnej i to daje rozsądnego oszacowania.

Problem polega na tym, że założenie o równomiernym rozłożeniu liczb od 0t 2^k-1jest zbyt trudne do osiągnięcia (dane, które napotkaliśmy, w większości nie są liczbami, prawie nigdy nie są równomiernie rozłożone i mogą znajdować się między dowolnymi wartościami. Ale używając dobrej funkcji haszującej można założyć, że bity wyjściowe byłyby równomiernie rozłożone, a większość funkcji haszujących ma wyjścia między 0a 2^k - 1( SHA1 podaje wartości od 0do 2^160). Więc to, co osiągnęliśmy do tej pory, to to, że możemy oszacować liczbę unikalnych elementów z maksymalną licznością kbitów, przechowując tylko jedną liczbę log(k)bitów rozmiaru . Wadą jest to, że w naszych szacunkach występują duże rozbieżności. Fajna rzecz, którą prawie stworzyliśmyProbabilistyczny artykuł liczący z 1984 r. (Szacunek jest trochę mądrzejszy, ale wciąż jesteśmy blisko).

LogLog

Zanim przejdziemy dalej, musimy zrozumieć, dlaczego nasze pierwsze oszacowanie nie jest takie świetne. Powodem tego jest to, że jedno przypadkowe wystąpienie elementu o wysokiej częstotliwości z prefiksem 0 może wszystko zepsuć. Jednym ze sposobów na ulepszenie tego jest użycie wielu funkcji skrótu, zliczenie maksimum dla każdej z funkcji skrótu i ​​na koniec uśrednienie ich. To doskonały pomysł, który poprawi oszacowanie, ale papier LogLog zastosował nieco inne podejście (prawdopodobnie dlatego, że haszowanie jest trochę drogie).

Użyli jednego haszyszu, ale podzielili go na dwie części. Jeden nazywa się wiadrem (całkowita liczba wiader to2^x ), a drugi - jest w zasadzie taki sam jak nasz hash. Ciężko mi było zrozumieć, co się dzieje, więc podam przykład. Zakładam, że masz dwa elementy i swoją funkcję skrótu, który podaje wartości formularza 0do 2^10produkowanych 2 wartości: 344a 387. Zdecydowałeś się mieć 16 wiader. Więc masz:

0101 011000  bucket 5 will store 1
0110 000011  bucket 6 will store 4

Mając więcej koszyków, zmniejszasz wariancję (zużywasz nieco więcej miejsca, ale wciąż jest niewielka). Korzystając z umiejętności matematycznych, byli w stanie obliczyć błąd (który jest 1.3/sqrt(number of buckets)).

HyperLogLog

HyperLogLog nie wprowadza żadnych nowych pomysłów, ale przede wszystkim wykorzystuje dużo matematyki, aby poprawić poprzednie oszacowanie. Naukowcy odkryli, że jeśli usuniesz 30% największych liczb z koszyków, znacznie poprawisz oszacowanie. Użyli również innego algorytmu do uśredniania liczb. Papier jest ciężki od matematyki.

I chcę zakończyć niedawnym artykułem, który pokazuje ulepszoną wersję algorytmu hyperLogLog (do tej pory nie miałem czasu, aby go w pełni zrozumieć, ale może później poprawię tę odpowiedź).

Intuicja jest taka, że ​​jeśli dane wejściowe to duży zestaw liczb losowych (np. Wartości zakodowane), powinny one równomiernie rozłożyć się w zakresie. Powiedzmy, że zakres wynosi do 10 bitów, aby przedstawić wartość do 1024. Następnie zaobserwowano minimalną wartość. Powiedzmy, że wynosi 10. Wtedy liczność zostanie oszacowana na około 100 (10 × 100 ≈ 1024).

Przeczytaj artykuł, aby poznać prawdziwą logikę.

Kolejne dobre wyjaśnienie z przykładowym kodem można znaleźć tutaj: Cholernie fajne algorytmy: szacowanie liczności
- Blog Nicka