Video: De Voorspelbare Mens 3: Mijn baas is een algoritme 2024
In het hart van veel streaming-algoritmen bevinden zich Bloom-filters. Gecreëerd bijna 50 jaar geleden door Burton H. Bloom, in een tijd dat computerwetenschap nog vrij jong was, was de oorspronkelijke bedoeling van de maker van dit algoritme om ruimte (geheugen) en / of tijd (complexiteit) in te ruilen tegen wat hij noemde toegestane fouten. Zijn originele paper is getiteld Space / Time Trade-offs in Hash-codering met toegestane fouten.
Je kunt je afvragen wat de ruimte en tijd is dat Bloom als motivatie beschouwt voor zijn algoritme. Stel je voor dat je moet bepalen of een element al in een stream is verschenen met behulp van een eerder besproken datastructuur. Het vinden van iets in een stream betekent dat opnemen en zoeken snel gaat, dus een hash-tabel lijkt een ideale keuze. hashtabellen vereisen eenvoudigweg het toevoegen van de elementen die u wilt opnemen en opslaan. Het herstellen van een element uit een hash-tabel is snel omdat de hash-tabel gemakkelijk te manipuleren waarden gebruikt om het element weer te geven, in plaats van het element zelf (wat behoorlijk complex zou kunnen zijn). Toch heeft het opslaan van beide elementen en een index voor die elementen beperkingen. Als een hash-tabel meer elementen bevat dan hij aankan, zoals de elementen in een continue en potentieel oneindige stroom, zult u op een gegeven moment geheugenproblemen oplopen.
Een essentiële overweging voor Bloom-filters is dat valse positieven kunnen voorkomen, maar fout-negatieven kunnen dat niet. Een gegevensstroom kan bijvoorbeeld realtime bewakingsgegevens voor een energiecentrale bevatten. Wanneer een Bloom-filter wordt gebruikt, zou de analyse van de gegevensstroom aantonen dat verwachte metingen waarschijnlijk deel uitmaken van de reeks toegestane waarden, met enkele fouten toegestaan. Wanneer er echter een fout optreedt in het systeem, laat dezelfde analyse zien dat de metingen geen deel uitmaken van de reeks toegestane waarden. Het is onwaarschijnlijk dat de valse positieven problemen veroorzaken, maar de afwezigheid van valse negatieven betekent dat iedereen veilig blijft. Vanwege het potentieel voor valse positieven zijn filters zoals het Bloom-filter probabilistische datastructuren - ze bieden geen bepaald antwoord, maar een waarschijnlijk antwoord.
Hashes, de afzonderlijke items in een hashtabel, zijn snel omdat ze fungeren als de index van een boek. Je gebruikt een hash-functie om de hash te produceren; de invoer is een element dat complexe gegevens bevat en de uitvoer is een eenvoudig getal dat als een index voor dat element fungeert. Een hash-functie is deterministisch omdat het elke keer dat u het een specifieke gegevensinvoer levert hetzelfde aantal produceert.U gebruikt de hash om de complexe informatie te vinden die u nodig hebt. Bloom-filters zijn handig omdat ze een zuinige manier zijn om sporen van veel elementen vast te leggen zonder ze weg te hoeven bewaren zoals een hash-tabel doet. Ze werken op een eenvoudige manier en gebruiken de volgende ingrediënten:
- Een bitvector: Een lijst met bitelementen, waarbij elke bit in het element een waarde van 0 of 1 kan hebben. De lijst is lang aantal bits genaamd m. Hoe groter m is, hoe beter, hoewel er manieren zijn om de omvang ervan optimaal te definiëren.
- Een reeks hash-functies: Elke hashfunctie vertegenwoordigt een andere waarde. Met de hash-functies kunnen snel gegevens worden gecrawld en uniform gedistribueerde resultaten worden geproduceerd, wat resulteert in resultaten die variëren van de minimale tot de maximale uitvoerwaarden van de hash.
