Je me souviens d'avoir entendu parler de l'algorithme suivant quelques années de retour, mais je ne trouve aucune référence à celle-ci en ligne. Il identifie les principaux k éléments (ou frappeurs lourds) dans un flux de données de N éléments utilisant uniquement les compteurs m . Ceci est particulièrement utile pour la recherche de termes de recherche, des abuseurs de réseau, etc. tout en utilisant une mémoire minimale.
L'algorithme: pour chaque élément,
J'ai trouvé de nombreux autres algorithmes similaires (dont beaucoup sont répertoriés, bien que non décrits, dans cet article de Wikipedia sur Algorithmes en streaming ), mais pas celui-ci. Je l'aime particulièrement parce que c'est aussi simple à mettre en œuvre tel qu'il est de décrire.
Mais j'aimerais en savoir plus sur ses caractéristiques probabilistes - si je ne suis intéressé que par les 100 premiers éléments, quel effet utilise 1 000 compteurs au lieu de 100 compteurs?
3 Réponses :
Vous recherchez peut-être l'algorithme "fréquent". Il utilise k - 1 compteurs pour trouver tous les éléments qui dépassent 1 / k du total et ont été publiés en 1982 par Maitra et Gries. C'est une généralisation des algorithmes "majoritaires" de Boyer et de Fischer-Salzberg), où k est 2. Ces algorithmes et algorithmes associés sont introduits dans un article utile, " Le problème de la Britney Spears. "
Je donne un Explication détaillée de l'algorithme ailleurs sur Stackoverflow, que je ne répète pas ici. Le point important est que, après un passage, les valeurs de compteur n'indiquent pas précisément la fréquence d'un élément; Ils peuvent sous-compter sur une marge qui dépend de la longueur du flux et d'inversement sur le nombre de compteurs ( n / k ). Tous ces algorithmes (y compris la "spacesaving" de Metwally) nécessitent une seconde passe si vous voulez un compte exact plutôt qu'une estimation de la fréquence.
En fait, je me souviens d'avoir lu cet article quand il a été publié. Mais il y a une différence dans les algorithmes à l'étape 3. L'algorithme de l'article décrirait tous les compteurs, alors que celui que j'ai décrit ne serait que décompter un seul compteur. Je me souviens vaguement qui étant un facteur important. Cela le rend plus efficace, mais je ne sais pas comment cela affecte la précision.
Vous parlez de l'algorithme notable Misra-Gries, et l'algorithme d'économie d'espace est une version plus rapide de l'algorithme Misra-Gries. Veuillez vérifier cette note de conférence pour détail algorithme de streaming dartmouth sec 1.2.
Une chose que je veux souligner est que cet algorithme ne vous donne pas les éléments Top-K si vous utilisez uniquement des compteurs K, il donne à tous les éléments de fréquence> m / k, où m est la longueur totale de le flux de données.
L'analyse détaillée peut être trouvée dans les notes de lecture que j'ai connectées.
qui ressemble à l'algoritme de remplacement de cache de processeur moins fréquemment utilisé (LFU)
L'algorithme: pour chaque élément,
sinon si l'élément n'a pas de compteur et de comptoirs> m, décrémenter un compteur existant. Si C atteint 0, remplacez son élément correspondant, avec l'élément actuel. (c est un indice dans la liste des compteurs existants, où c augmente la mode rond robin pour chaque élément qui atteint cette étape.)
Pas tout à fait sûr, mais cela ressemble à Space-Saving par A. Metwally et al.
@erickson pas mon vote, j'ai peur.