Video: Biblical Series I: Introduction to the Idea of God 2024
Chiar dacă un filtru Bloom poate urmări obiectele care sosesc dintr-un flux, nu poate spune câte obiecte există. Un vector de biți umplut de unul poate (în funcție de numărul de hash-uri și de probabilitatea de coliziune) să ascundă adevăratul număr de obiecte care au fost rulate la aceeași adresă.
Cunoașterea numărului distinct de obiecte este utilă în diferite situații, cum ar fi când doriți să știți cât de mulți utilizatori distinși au văzut o anumită pagină de site sau numărul de interogări distincte ale motorului de căutare. Stocarea tuturor elementelor și găsirea duplicatelor dintre ele nu pot funcționa cu milioane de elemente, în special provenind dintr-un flux. Când doriți să cunoașteți numărul obiectelor distincte dintr-un flux, trebuie să mai utilizați o funcție hash, dar abordarea presupune luarea unei schițe numerice.
Schițarea înseamnă a face o aproximare, adică o valoare inexactă, dar nu complet greșită, ca răspuns. Aproximarea este acceptabilă deoarece valoarea reală nu este prea departe de ea. În acest algoritm inteligent, HyperLogLog, care se bazează pe probabilitate și aproximație, observați caracteristicile numerelor generate de flux. HyperLogLog derivă din studiile cercetătorilor de calculatoare Nigel Martin și Philippe Flajolet. Flajolet și-a îmbunătățit algoritmul inițial, Flajolet-Martin (sau algoritmul LogLog), în versiunea HyperLogLog mai robustă, care funcționează astfel:
- Un hash transformă fiecare element primit din flux într-un număr.
- Algoritmul convertește numărul în binar, standardul numeric de bază 2 folosit de calculatoare.
- Algoritmul numără numărul de zerouri inițiale din numărul binar și piese ale numărului maxim pe care îl vede, adică n.
- Algoritmul estimează numărul de elemente distincte transferate în flux folosind n. Numărul elementelor distincte este de 2 ^ n.
De exemplu, primul element din șir este cuvântul câine. Algoritmul îl cochetează într-o valoare întregă și îl convertește în binar, cu un rezultat de 01101010. La începutul numărului apare doar un zero, astfel încât algoritmul îl înregistrează ca numărul maxim de zerouri care au urmat. Algoritmul vede apoi cuvintele papagal și lup, ale căror echivalente binare sunt 11101011 și 01101110, lăsând n neschimbate. Cu toate acestea, atunci când cuvântul cat trece, ieșirea este 00101110, deci n devine 2. Pentru a estima numărul de elemente distincte, algoritmul calculează 2 ^ n, adică 2 ^ 2 = 4. Figura arată acest proces.
Trunchiul algoritmului este că dacă hash produce rezultate aleatoare, distribuite în mod egal (ca într-un filtru Bloom), prin analizarea reprezentării binare, puteți calcula probabilitatea ca o succesiune de zerouri să apară. Deoarece probabilitatea ca un singur număr binar să fie 0 este unul din două, pentru a calcula probabilitatea secvențelor de zerouri, trebuie să multiplicați probabilitatea de 1/2 de câte ori lungimea secvenței de zerouri:
- 50% (1/2) probabilitate pentru numere începând cu 0
- 25% (1/2 * 1/2) probabilitate pentru numere începând cu 00
- 12. 5% (1/2 * 1/2 * 1/2) probabilitate pentru numere începând cu 000
- (1/2) ^ k probabilitate pentru numere care încep cu k zerouri (utilizați puteri pentru calcule mai rapide a mai multor multiplicări ale același număr)
Cu cât sunt mai puține numere pe care le vede HyperLogLog, cu atât mai mare este imprecizia. Acuratețea crește atunci când utilizați calculul HyperLogLog de mai multe ori utilizând diferite funcții de tip hash și media împreună răspunsurile de la fiecare calcul, dar hashing-ul de multe ori durează timp și fluxurile sunt rapide. Ca o alternativă, puteți utiliza același hash, dar împărțiți fluxul în grupuri (cum ar fi separarea elementelor în grupuri în momentul în care acestea sosesc pe baza comenzii lor de sosire), iar pentru fiecare grup, țineți evidența numărului maxim de zerouri care urmează. În cele din urmă, calculați estimarea elementului distinct pentru fiecare grup și calculați media aritmetică a tuturor estimărilor. Această abordare este o mediere stocastică și oferă estimări mai precise decât aplicarea algoritmului la întreg fluxul.
