Hur man hittar antalet element i en dataström - dummies

Även om ett Bloom-filter kan spåra objekt som kommer från en ström, kan det inte berätta hur många objekt som finns. En liten vektor fylld av en kan (beroende på antalet haschar och sannolikheten för kollision) gömma det sanna antalet objekt som har hashed på samma adress.

Att veta det distinkta antalet objekt är användbart i olika situationer, till exempel när du vill veta hur många distinkta användare som har sett en viss webbsida eller antalet olika sökmotorfrågor. Att lagra alla element och hitta dubbletter bland dem kan inte fungera med miljontals element, särskilt från en ström. När du vill veta antalet separata objekt i en ström måste du fortfarande förlita dig på en hashfunktion, men det innebär att du tar en numerisk skiss.

Sketching betyder att en approximation, som är ett inexakt men inte helt fel värde som ett svar. Approximation är acceptabelt eftersom det verkliga värdet inte är för långt från det. I denna smarta algoritmen, HyperLogLog, som är baserad på sannolikhet och approximation, observerar du egenskaperna hos tal som genereras från strömmen. HyperLogLog härrör från studierna av datavetenskapare Nigel Martin och Philippe Flajolet. Flajolet förbättrade sin initiala algoritm, Flajolet-Martin (eller LogLog-algoritmen) till den mer robusta HyperLogLog-versionen, som fungerar så här:

1. En hasj konverterar varje element som tas emot från strömmen till ett tal.
2. Algoritmen omvandlar numret till binärt, bas 2-standarden som datorer använder.
3. Algoritmen räknar antalet initiala nollor i det binära numret och spåren i det maximala antalet som det ser, vilket är n.
4. Algoritmen uppskattar antalet separata element som passerade i strömmen med hjälp av n. Antalet separata element är 2 ^ n.

Till exempel är det första elementet i strängen ordet hund. Algoritmen har det till ett heltal och omvandlar det till binärt, med ett resultat av 01101010. Endast en noll visas i början av numret, så algoritmen registrerar det som det maximala antalet efterföljande nollor. Algoritmen ser då orden papegoja och varg, vars binära ekvivalenter är 11101011 och 01101110, vilket lämnar n oförändrad. När ordet katt passerar är emellertid utgången 00101110, så n blir 2. För att uppskatta antalet separata element beräknar algoritmen 2 ^ n, det vill säga 2 ^ 2 = 4. Figuren visar denna process.

Räkna endast ledande nollor.

Algoritmens knep är att om din hash producerar slumpmässiga resultat, lika fördelade (som i ett Bloom-filter), genom att titta på binär representation, kan du beräkna sannolikheten för att en sekvens av nollor uppstod. Eftersom sannolikheten för ett enda binärt tal att vara 0 är en i två, för att beräkna sannolikheten för sekvenser av nollor multiplicerar du bara den 1/2 sannolikheten så många gånger som längden av sekvensen av nollor:

• 50 procent (1/2) sannolikhet för siffror som börjar med 0
• 25 procent (1/2 * 1/2) sannolikhet för siffror som börjar med 00
• 12. 5% (1/2 * 1/2 * 1/2) sannolikhet för tal som börjar med 000
• (1/2) ^ k sannolikhet för tal som börjar med k zeros (du använder befogenheter för snabbare beräkningar av många multiplikationer av samma antal)

Ju färre siffrorna som HyperLogLog ser desto större är precisionen. Noggrannhet ökar när du använder HyperLogLog-beräkningen många gånger med olika hashfunktioner och i genomsnitt sammanfattar svaren från varje beräkning, men hashing många gånger tar tid och strömmar är snabba. Som ett alternativ kan du använda samma hash men dela strömmen till grupper (t.ex. genom att separera elementen i grupper när de kommer utifrån deras ankomstorder) och för varje grupp håller du reda på det maximala antalet efterföljande nollor. I slutändan beräknar du den skilda grundberäkningen för varje grupp och beräknar det aritmetiska medelvärdet av alla uppskattningar. Detta tillvägagångssätt är stokastiskt medelvärde och ger mer exakta uppskattningar än att tillämpa algoritmen på hela strömmen.