Video: Curious Beginnings | Critical Role | Campaign 2, Episode 1 2024
Selv om et Bloom-filter kan spore objekter, der kommer fra en strøm, kan det ikke fortælle, hvor mange objekter der er. En smule vektor fyldt af dem kan (afhængigt af antallet af hash og sandsynligheden for kollision) skjule det sande antal genstande, der er hashed på samme adresse.
At kende det forskellige antal objekter er nyttigt i forskellige situationer, f.eks. Når du vil vide, hvor mange forskellige brugere der har set en bestemt hjemmeside eller antallet af forskellige søgemaskiner. Lagring af alle elementer og finde duplikaterne blandt dem kan ikke fungere med millioner af elementer, især fra en strøm. Når du vil vide antallet af forskellige objekter i en strøm, skal du stadig stole på en hash-funktion, men tilgangen indebærer at tage en numerisk skitse.
Skitsering betyder at der er en tilnærmelse, der er en inexakt, men ikke fuldstændig forkert værdi som et svar. Tilnærmelse er acceptabel, fordi den reelle værdi ikke er for langt fra den. I denne smarte algoritme, HyperLogLog,, som er baseret på sandsynlighed og tilnærmelse, observerer du egenskaberne ved tal, der genereres fra strømmen. HyperLogLog stammer fra studierne af computerforskere Nigel Martin og Philippe Flajolet. Flajolet forbedrede deres første algoritme, Flajolet-Martin (eller LogLog-algoritmen) til den mere robuste HyperLogLog-version, som virker som denne:
- En hash konverterer hvert element modtaget fra strømmen til et tal.
- Algoritmen konverterer antallet til binære, den basale 2-standard, som computere bruger.
- Algoritmen tæller antallet af indledende nuller i det binære nummer og spor af det maksimale antal, det ser, hvilket er n.
- Algoritmen estimerer antallet af forskellige elementer, der er bestået i strømmen ved hjælp af n. Antallet af forskellige elementer er 2 ^ n.
For eksempel er det første element i strengen ordet hund. Algoritmen pakker den ind i en heltalværdi og konverterer den til binær, med et resultat af 01101010. Der vises kun en nul i begyndelsen af nummeret, så algoritmen registrerer det som det maksimale antal nulstillende nuler set. Algoritmen ser så ordene papegøje og ulv,, hvis binære ækvivalenter er 11101011 og 01101110, hvilket efterlader n uændret. Når ordet cat passerer, er output imidlertid 00101110, så n bliver 2. For at estimere antallet af forskellige elementer beregner algoritmen 2 ^ n, det vil sige 2 ^ 2 = 4. Figuren viser denne proces.
Algoritmens trick er, at hvis din hash producerer tilfældige resultater, lige fordelt (som i et Bloom filter) ved at se på den binære repræsentation, kan du beregne sandsynligheden for, at en sekvens af nuller dukker op. Fordi sandsynligheden for at et enkelt binært tal skal være 0 er en ud af to, for at beregne sandsynligheden for sekvenser af nuller, multiplicerer du blot den 1/2 sandsynlighed så mange gange som længden af sekvensen af nuller:
- 50 procent (1/2) sandsynlighed for tal begyndende med 0
- 25 procent (1/2 * 1/2) sandsynlighed for tal begyndende med 00
- 12. 5 procent (1/2 * 1/2 * 1/2) sandsynlighed for tal startende med 000
- (1/2) ^ k sandsynlighed for tal, der starter med k nuller (du bruger beføjelser til hurtigere beregninger af mange multiplikationer af samme tal)
Jo færre tal, som HyperLogLog ser, jo større er upræcisionen. Nøjagtigheden øges, når du bruger HyperLogLog-beregningen mange gange ved hjælp af forskellige hashfunktioner og gennemsnitligt sammen svarene fra hver beregning, men hashing mange gange tager tid, og strømme er hurtige. Som et alternativ kan du bruge den samme hash, men dele strømmen i grupper (f.eks. Ved at adskille elementerne i grupper efterhånden som de ankommer ud fra deres ankomstordre), og for hver gruppe holder du styr på det maksimale antal nulstillende nuller. I sidste ende beregner du det skelne element estimat for hver gruppe og beregner det aritmetiske gennemsnit af alle estimaterne. Denne fremgangsmåde er stokastisk middelværdi og giver mere præcise estimater end at anvende algoritmen til hele strømmen.
