Hvordan å finne antall elementer i en datastrøm - dummier

Selv om et Bloom-filter kan spore objekter som kommer fra en strøm, kan det ikke fortelle hvor mange objekter det er. En bit vektor fylt av de kan (avhengig av antall hashes og sannsynligheten for kollisjon) gjemme det sanne antall objekter som har hashed på samme adresse.

Å vite det forskjellige antall objekter er nyttig i ulike situasjoner, for eksempel når du vil vite hvor mange forskjellige brukere har sett en bestemt nettside eller antall forskjellige søkemotorforespørsler. Lagring av alle elementene og å finne duplikatene blant dem kan ikke fungere med millioner av elementer, spesielt fra en strøm. Når du vil vite antall forskjellige objekter i en strøm, må du fortsatt stole på en hashfunksjon, men tilnærmingen innebærer å ta en numerisk skisse.

Sketching betyr å ta en tilnærming, som er en inexakt, men ikke helt feil verdi som et svar. Tilnærming er akseptabelt fordi den virkelige verdien ikke er for langt fra den. I denne smarte algoritmen, HyperLogLog, som er basert på sannsynlighet og tilnærming, observerer du egenskapene til tall som genereres fra strømmen. HyperLogLog kommer fra studier av datavitenskapsmenn Nigel Martin og Philippe Flajolet. Flajolet forbedret sin første algoritme, Flajolet-Martin (eller LogLog-algoritmen), til den mer robuste HyperLogLog-versjonen, som virker slik:

1. En hash konverterer hvert element mottatt fra strømmen til et tall.
2. Algoritmen konverterer nummeret til binær, basen 2-numerisk standard som datamaskiner bruker.
3. Algoritmen teller antall innledende nuller i binærnummeret og sporene til det maksimale antallet det ser, som er n.
4. Algoritmen anslår antall forskjellige elementer som er passert i strømmen ved hjelp av n. Antall forskjellige elementer er 2 ^ n.

For eksempel er det første elementet i strengen ordet hund. Algoritmen pakker den inn i en heltallverd og konverterer den til binær, med et resultat av 01101010. Bare ett null vises i begynnelsen av nummeret, slik at algoritmen registrerer det som det maksimale antall nulpunktet sett. Algoritmen ser da ordene papegøye og ulv, hvis binære ekvivalenter er 11101011 og 01101110, og etterlater n uendret. Når ordet cat passerer, er utgangen imidlertid 00101110, slik at n blir 2. For å beregne antall forskjellige elementer beregner algoritmen 2 ^ n, det vil si 2 ^ 2 = 4. Figuren viser denne prosessen.

Teller bare ledende nuller.

Algoritmenes knep er at hvis din hash produserer tilfeldige resultater, like fordelt (som i et Bloom filter), ved å se på binærrepresentasjonen, kan du beregne sannsynligheten for at en sekvens nuller dukket opp. Fordi sannsynligheten for et enkelt binært tall til å være 0 er en i to, for å beregne sannsynligheten for sekvenser av nuller, multipliserer du bare den 1/2-sannsynligheten så mange ganger som lengden på sekvensen av nuller:

• 50 prosent (1/2) sannsynlighet for tall som begynner med 0
• 25 prosent (1/2 * 1/2) sannsynlighet for tall som begynner med 00
• 12. 5 prosent (1/2 * 1/2 * 1/2) sannsynlighet for tall som starter med 000
• (1/2) ^ k sannsynlighet for tall som starter med k nuller (du bruker krefter for raskere beregninger av mange multiplikasjoner av samme tall)

Jo færre tallene som HyperLogLog ser, desto større er upresisjonen. Nøyaktighet øker når du bruker HyperLogLog-beregningen mange ganger ved hjelp av forskjellige hashfunksjoner og gjennomsnittlig sammen svarene fra hver beregning, men hashing mange ganger tar tid og strømmer er raske. Som et alternativ kan du bruke samme hash, men dele strømmen i grupper (for eksempel ved å skille elementene inn i grupper etter hvert som de kommer etter deres ankomstordre), og for hver gruppe holder du oversikt over det maksimale antall nulpunkter. Til slutt beregner du det distinkte elementestimatet for hver gruppe og beregner det aritmetiske gjennomsnittet av alle estimatene. Denne tilnærmingen er stokastisk gjennomsnittlig og gir mer presise estimater enn å anvende algoritmen til hele strømmen.