Un algorithme de comptage probabiliste

Un algorithme de comptage probabiliste, ou comment compter le nombre d’éléments distincts dans un grand ensemble de données en disposant d’un espace mémoire très restreint.

Grace a des propriétés de mots binaires aléatoires comme la fréquence d’un préfixe de zéros de taille $k$, on peut estimer avec une précision de quelques pour cents le nombre d’éléments distincts dans un ensemble de grande taille (des milliers de Go) en utilisant un espace mémoire de 1 kbit.

Je présenterai l’algorithme, et montrerai de nombreux exemples d’applications. J’expliquerai les grandes lignes de l’analyse dans la mesure du temps restant.