Algorithme de Flajolet et Martin

L'algorithme de Flajolet et Martin^[1] est un algorithme donnant une estimation du 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'éléments distincts. Cet algorithme a été inventé en 1984 par Philippe Flajolet and G. Nigel Martin^[2], puis amélioré par Marianne Durand et Philippe Flajolet^[3],[4]. C'est un algorithme de fouille de flots de données (streaming).

En 2010^[5], 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 ${\displaystyle hash(x)}$, associant à une entrée ${\displaystyle x}$ un entier dans ${\displaystyle [0,2^{L}-1]}$, dont les images sont uniformément réparties. L'ensemble des entiers de 0 à ${\displaystyle 2^{L}-1}$ correspond en fait à l'ensemble des chaînes binaires de longueur ${\displaystyle L}$.

Étant donné un entier positif ${\displaystyle y}$, on note ${\displaystyle bit(y,k)}$ le ${\displaystyle k}$-ème bit dans la représentation binaire de ${\displaystyle y}$, de sorte que :

${\displaystyle y=\sum _{k\geq 0}{\text{bit}}(y,k)2^{k}}$

On définit ensuite une fonction ${\displaystyle \rho (y)}$ qui associe à y la position du bit de poids faible dans sa représentation binaire :

${\displaystyle \rho (y)=\min _{{\text{bit}}(y,k)\neq 0;k\geq 0}k}$

avec ${\displaystyle \rho (0)=L}$. Par exemple, ${\displaystyle \rho (13)=\rho (1101)=0}$ car le premier bit est non nul, alors que ${\displaystyle \rho (8)=\rho (0100)=2}$ 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 un nombre finissant par ${\displaystyle 2^{k}}$ (un 1 suivi de ${\displaystyle k}$ zéros) est ${\displaystyle 2^{-(k+1)}}$ et correspond à tirer ${\displaystyle k}$ piles suivi d'un face en lançant une pièce de monnaie équilibrée.

Description de l'algorithme

Algorithme de Flajolet-Martin — L'algorithme de Flajolet–Martin estime la cardinalité d'un multiensemble ${\displaystyle M}$ de la manière suivante :

1. Initialiser un vecteur BITMAP contenant ${\displaystyle L}$ zéros.
2. Pour chaque élément ${\displaystyle x}$ dans ${\displaystyle M}$, effectuer :
   1. ${\displaystyle index=\rho ({\text{hash}}(x))}$,
   2. ${\displaystyle BITMAP[index]=1}$.
3. On note ${\displaystyle R}$ le plus petit indice ${\displaystyle i}$ tel que ${\displaystyle BITMAP[i]=0}$.
4. La cardinalité de ${\displaystyle M}$ est approchée par ${\displaystyle 2^{R}/\phi }$ avec ${\displaystyle \phi \approx 0.77351}$.

Commentaires

Avec ${\displaystyle n}$ le nombre d'éléments distincts de ${\displaystyle M}$, alors ${\displaystyle BITMAP[0]}$ est accédé environ ${\displaystyle n/2}$ fois, ${\displaystyle BITMAP[1]}$ accédé ${\displaystyle n/4}$ fois, etc. Ainsi, si ${\displaystyle i\gg \log _{2}n}$, ${\displaystyle BITMAP[i]}$ vaut certainement 0, de même que si ${\displaystyle i\ll \log _{2}n}$, ${\displaystyle BITMAP[i]}$ vaut certainement 1. Si ${\displaystyle i\approx \log _{2}n}$ alors ${\displaystyle BITMAP[i]}$ vaut soit 1 soit 0.

Les calculs pour obtenir le facteur de correction ${\displaystyle \phi \approx 0.77351}$ sont détaillés dans l'article de Flajolet et Martin.

Voir aussi

• HyperLogLog