« Algorithme de Flajolet et Martin » : différence entre les versions
Créé en traduisant la page « Flajolet–Martin algorithm » |
(Aucune différence)
|
Version du 5 février 2016 à 00:36
L'algorithme de Flajolet–Martin est un algorithme permettant d'approximer le nombre d'éléments distincts dans un flot, en une seule passe et avec une complexité logarithmique en mémoire, proportionnelle au nombre maximum d'élements distincts. Cet algorithme a été inventé en 1984 par Philippe Flajolet and G. Nigel Martin[1], puis amélioré par Marianne Durand et Philippe Flajolet.[2][3]
En 2010,[4] Daniel M. Kane, Jelani Nelson et David P. Woodruff ont proposé un algorithme avec une complexité spatiale presque optimale et un coût de modification en O(1).
L'algorithme
L'algorithme nécessite une fonction de hashage , associant à une entrée un entier dans , dont les images sont uniformément réparties. L'ensemble des entiers de 0 à correspond en fait à l'ensemble des chaînes binaires de longueur .
On définit ensuite un fonction qui associe à y la position du bit de poids faible dans sa représentation binaire :
avec . Par exemple, car le bit de poids faible est 1, alors que avec le bit de poids faible en troisième position. Étant donné que les images de la fonction de hashage sont uniformément réparties, la probabilité d'observer une valeur terminant par (un suivi de zéros) est et correspond à obtenir piles suivi d'un face en lancant une pièce de monnaie équilibrée.
L'algorithme de Flajolet–Martin estime la cardinalité d'un multiensemble de la manière suivante :
- Initialiser un vecteur BITMAP contenant zéros.
- Pour chaque élement dans , effectuer :
- index = .
- .
- On note le plus petit indice tel que .
- La cardinalité de est approchée par avec .
Avec le nombre d'éléments distincts de , alors est accédé environ fois, accédé fois, etc.. Ainsi, si , vaut certainement 0, de même que si , vaut certainement 1. Si alors vaut soit 1 soit 0.
Les calculs pour obtenir le facteur de correction sont détaillés dans l'article de Flajolet et Martin.
Voir aussi
Références
- Philippe Flajolet et G. Nigel Martin, « Probabilistic counting algorithms for data base applications », Journal of Computer and System Sciences, vol. 31, no 2, , p. 182–209 (DOI 10.1016/0022-0000(85)90041-8, lire en ligne)
- (en) Marianne Durand et Philippe Flajolet, Algorithms - ESA 2003, vol. 2832, coll. « Lecture Notes in Computer Science », , 605 p. (ISBN 978-3-540-20064-2, DOI 10.1007/978-3-540-39658-1_55), « Loglog Counting of Large Cardinalities »
- Philippe Flajolet, Éric Fusy, Olivier Gandouet et Frédéric Meunier, « Hyperloglog: The analysis of a near-optimal cardinality estimation algorithm », Discrete Mathematics and Theoretical Computer Science, , p. 127–146 (lire en ligne)
- (en) D. M. Kane, J. Nelson et D. P. Woodruff, Proceedings of the twenty-ninth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems of data - PODS '10, (ISBN 978-1-4503-0033-9, DOI 10.1145/1807085.1807094), « An optimal algorithm for the distinct elements problem », p. 41
Liens externes
- (en) Anand Rajaraman et Jeffrey David Ullman, Mining of Massive Datasets, Cambridge University Press, , 119– (ISBN 9781139505345, lire en ligne)Mining of Massive Datasets. Cambridge University Press. pp. 119–. ISBN 9781139505345. Retrieved 9 November 2014.