Video: Dime cómo eres y te diré que herida emocional tienes por Ana Belén Mena 2024
Imparare a contare gli oggetti in un flusso può aiutarti a trovare gli oggetti più frequenti o classificare eventi usuali e insoliti. Questo algoritmo sfrutta le funzioni hash e gli schizzi approssimativi. Lo fa dopo aver filtrato gli oggetti duplicati e contato gli elementi distinti che sono comparsi nel flusso di dati.
Questa tecnica viene utilizzata per risolvere problemi come trovare le query più frequenti in un motore di ricerca, gli articoli più venduti da un rivenditore online, le pagine molto popolari in un sito Web o gli stock più volatili (contando i tempi di uno stock venduto e comprato).
Si applica la soluzione a questo problema, Count-Min Sketch, a un flusso di dati. Richiede solo un passaggio di dati e archivia meno informazioni possibili. Questo algoritmo viene applicato in molte situazioni del mondo reale (come l'analisi del traffico di rete o la gestione di flussi di dati distribuiti). La ricetta richiede l'utilizzo di una serie di funzioni hash, ognuna associata a un vettore bit, in un modo simile a un filtro Bloom, come mostrato nella figura:
- Inizializza tutti i vettori bit a zero in tutte le posizioni.
- Applicare la funzione di hash per ogni vettore di bit quando si riceve un oggetto da un flusso. Utilizzare l'indirizzo numerico risultante per incrementare il valore in quella posizione.
- Applica la funzione di hash a un oggetto e recupera il valore nella posizione associata quando viene richiesto di stimare la frequenza di un oggetto. Di tutti i valori ricevuti dai vettori bit, si prende il più piccolo come frequenza del flusso.
Poiché le collisioni sono sempre possibili quando si usa una funzione hash, specialmente se il vettore bit associato ha pochi slot, avendo a disposizione più vettori bit, si assicura che almeno uno di essi mantenga il valore corretto. Il valore della scelta dovrebbe essere il più piccolo perché non è mescolato con conteggi falsi positivi dovuti a collisioni.
