Video: Web Apps of the Future with React by Neel Mehta 2024
Hoewel een Bloom-filter objecten van een stream kan volgen, kan het niet zeggen hoeveel objecten er zijn. Een bitvector gevuld door enen kan (afhankelijk van het aantal hashes en de kans op een botsing) het ware aantal hash-objecten op hetzelfde adres verbergen.
Het aantal objecten kennen is handig in verschillende situaties, bijvoorbeeld wanneer u wilt weten hoeveel verschillende gebruikers een bepaalde websitepagina hebben gezien of het aantal verschillende zoekopdrachten voor zoekmachines. Het opslaan van alle elementen en het vinden van de duplicaten onder hen kan niet werken met miljoenen elementen, vooral afkomstig van een stream. Wanneer u het aantal verschillende objecten in een stream wilt weten, moet u nog steeds vertrouwen op een hash-functie, maar de aanpak bestaat uit het nemen van een numerieke schets.
Schetsen betekent een schatting maken, dat is een onnauwkeurige maar niet helemaal verkeerde waarde als antwoord. Benadering is acceptabel omdat de echte waarde er niet te ver van verwijderd is. In dit slimme algoritme, HyperLogLog, dat is gebaseerd op waarschijnlijkheid en benadering, observeert u de kenmerken van getallen die uit de stream zijn gegenereerd. HyperLogLog is afgeleid van de studies van computerwetenschappers Nigel Martin en Philippe Flajolet. Flajolet verbeterde hun oorspronkelijke algoritme, Flajolet-Martin (of het LogLog-algoritme), naar de robuustere HyperLogLog-versie, die zo werkt:
- Een hash converteert elk element dat van de stream is ontvangen naar een getal.
- Het algoritme converteert het getal naar binair, de standaardbasisnorm van 2 die door computers wordt gebruikt.
- Het algoritme telt het aantal initiële nullen in het binaire getal en tracks van het maximale aantal dat het ziet, dat is n.
- Het algoritme schat het aantal afzonderlijke elementen dat in de stroom is gepasseerd met behulp van n. Het aantal afzonderlijke elementen is 2 ^ n.
Het eerste element in de tekenreeks is bijvoorbeeld het woord. Het algoritme hashes het in een geheel getal en converteert het naar binair, met als resultaat 01101010. Er verschijnt slechts één nul aan het begin van het getal, dus het algoritme registreert het als het maximale aantal volgnullen. Het algoritme ziet dan de woorden papegaai en wolf, waarvan de binaire equivalenten 11101011 en 01101110 zijn, waardoor n ongewijzigd blijft. Wanneer het woord cat echter wordt doorgegeven, is de uitvoer 00101110, dus wordt n 2. Om het aantal afzonderlijke elementen te schatten, berekent het algoritme 2 ^ n, dat wil zeggen 2 ^ 2 = 4. De figuur toont dit proces.
De truc van het algoritme is dat als je hash willekeurige resultaten produceert, gelijk verdeeld (zoals in een Bloom-filter), door te kijken naar de binaire representatie, je de kans kunt berekenen dat een reeks nullen verschijnt. Omdat de kans dat een enkelvoudig binair getal 0 is één op twee is, vermenigvuldigt u die kans van 1/2 keer net zo vaak als de lengte van de reeks van nullen:
- 50 procent voor het berekenen van de kans op reeksen nullen. (1/2) kans op getallen die beginnen met 0
- 25 procent (1/2 * 1/2) kans op getallen die beginnen met 00
- 12. 5 procent (1/2 * 1/2 * 1/2) kans voor getallen die beginnen met 000
- (1/2) ^ k waarschijnlijkheid voor getallen die beginnen met k-nullen (je gebruikt krachten voor snellere berekeningen van veel vermenigvuldigingen van de hetzelfde nummer)
Hoe minder getallen die HyperLogLog ziet, hoe groter de onnauwkeurigheid. De nauwkeurigheid neemt toe wanneer u de HyperLogLog-berekening vele malen gebruikt met verschillende hash-functies en de antwoorden van elke berekening tezamen meet, maar hashing vele malen kost tijd en streams zijn snel. Als alternatief kunt u dezelfde hash gebruiken maar de stroom in groepen verdelen (zoals door de elementen in groepen te splitsen wanneer ze arriveren op basis van hun aankomstorder) en voor elke groep het maximale aantal volgnullen bij te houden. Uiteindelijk berekent u de afzonderlijke elementschatting voor elke groep en berekent u het rekenkundig gemiddelde van alle schattingen. Deze benadering is stochastisch middelen en biedt nauwkeuriger schattingen dan het toepassen van het algoritme op de hele stroom.
