Video: Räkna med x i omkrets av objekt! 2024
Att lära dig att räkna objekt i en ström kan hjälpa dig att hitta de vanligaste föremålen eller rangordna vanliga och ovanliga händelser. Denna algoritm utnyttjar hashfunktioner och approximativa skisser. Det gör det efter att ha filtrerat duplicerade objekt och räknat med separata element som har dykt upp i dataströmmen.
Du använder den här tekniken för att lösa problem som att hitta de vanligaste frågorna i en sökmotor, de bästsäljande föremålen från en online-återförsäljare, de populäraste sidorna på en webbplats eller de mest flyktiga bestånden (genom att räkna hur många gånger en aktie är såld och köpt).
Du tillämpar lösningen på detta problem, Count-Min Sketch, till en dataström. Det kräver bara ett datapass och lagrar så lite information som möjligt. Denna algoritm tillämpas i många verkliga situationer (t.ex. analys av nätverkstrafik eller hantering av distribuerade dataflöden). Receptet kräver att man använder en massa hashfunktioner, var och en i samband med en bitvektor, på ett sätt som liknar ett Bloom-filter, som visas i figuren:
- Initiera alla bitvektorer till nollor i alla positioner.
- Använd hashfunktionen för varje bitvektor när du tar emot ett objekt från en ström. Använd den resulterande numeriska adressen för att öka värdet vid den positionen.
- Applicera hash-funktionen på ett objekt och hämta värdet i tillhörande position när du uppmanas att uppskatta frekvensen för ett objekt. Av alla värden som tas emot från bitvektorerna tar du det minsta som frekvensen av strömmen.
Eftersom kollisioner alltid är möjliga när en hashfunktion används, speciellt om den associerade bitvektorn har få slitsar, så har flera bitvektorer till hands dig att minst en av dem håller rätt värde. Valet av valet ska vara det minsta eftersom det inte blandas med falska positiva räkningar på grund av kollisioner.
