3.4 Modélisations par des structures arborescentes
109
leur arrivée et non stockées, et il est impossible de les relire. De plus, nous voulons
un algorithme qui ne dépende pas de la distribution de probabilité sur l’ensemble
des clés, i.e., de la structure des répétitions. Par contre, nous acceptons une certaine
incertitude sur le nombre de clés, le but étant d’avoir une estimation rapide de l’ordre
de grandeur plutôt qu’un résultat précis mais trop long (voire impossible) à obtenir.
De part son importance pratique, ce problème a connu différentes approches ; cf.
par exemple les travaux autour du comptage probabiliste de Flajolet et Martin [87],
puis Durand et Flajolet [73] pour des algorithmes de plus en plus efficaces avec
leur analyse, jusqu’à Flajolet et al. [104] pour l’algorithme HyperLogLog en 2007.
Nous renvoyons à l’article de synthèse de Flajolet [82] pour une vue globale sur ce
problème, et nous intéressons ci-dessous à l’échantillonnage adaptatif, dont l’idée
initiale serait due à Wegman 25 et qui a été analysé lui aussi par Flajolet dans [81].
Cette méthode n’est sans doute pas la plus performante en pratique, mais son intérêt
dans le cadre de ce livre vient du fait que sa modélisation fait intervenir un trie. Une
variante est le comptage approché, dont l’algorithme initial, qui date de 1978, est dû
à Morris [189] et a été analysé quelques années plus tard par Flajolet [80].
Voyons donc l’algorithme de Wegman. Si ce n’est déjà le cas, un prétraitement
transforme les clés en une suite de bits grâce à une fonction de hachage σ , qui
associe à une clé x une valeur σ (x) ∈ {0, 1} ∞ . 26 En négligeant les collisions
dues au hachage, i.e., le fait que la fonction σ n’est en général pas injective, nous
introduisons une erreur de quelques pour cent, alors que l’erreur due à l’algorithme
est bien supérieure (l’analyse fine, cf. Flajolet [81], montre qu’elle est de l’ordre de
5 à 20 pour cent, et qu’elle diminue avec la taille de la mémoire de travail). Dans
l’exposé qui suit, nous identifions les clés x et les valeurs σ (x), et nous supposons
une distribution uniforme sur {0, 1} ∞ (si la distribution de départ n’est pas uniforme,
il existe des techniques permettant de rectifier ce biais lors du hachage).
L’algorithme travaille avec une suite de N clés que nous supposons être des
éléments de {0, 1} ∞ , un espace de travail en mémoire centrale pouvant contenir
m clés, et une variable entière δ, initialisée à 0, qui représente la « profondeur »
de l’échantillonnage. En pratique, N est « grand » et m est « petit ». L’algorithme
procède à une lecture séquentielle des clés, en gardant les clés distinctes ; il n’y a
donc aucune répétition parmi les clés présentes en mémoire. Les comparaisons et
recherches de clés se font en mémoire centrale, et sont supposées ici avoir un coût
négligeable par rapport à la lecture des N éléments. À chaque fois que les m places
sont allouées, l’algorithme ne garde, parmi les clés présentes en mémoire centrale à
ce moment, que celles commençant par 0, et augmente δ de 1. À tout instant, il y a
au plus m clés présentes en mémoire centrale ; ce sont celles commençant par 0 δ .
Lorsque la lecture des clés est finie, l’algorithme calcule une estimation
N de N
en fonction de la profondeur δ et du nombre ν de clés présentes alors en mémoire
centrale :
N = 2 δ ν.
25 Il ne semble pas y avoir eu d’article publié, et l’article [81] mentionne seulement une
« communication privée » de Wegman.
26 Une présentation des fonctions de hachage se trouve par exemple dans le livre de Knuth [156].
109
leur arrivée et non stockées, et il est impossible de les relire. De plus, nous voulons
un algorithme qui ne dépende pas de la distribution de probabilité sur l’ensemble
des clés, i.e., de la structure des répétitions. Par contre, nous acceptons une certaine
incertitude sur le nombre de clés, le but étant d’avoir une estimation rapide de l’ordre
de grandeur plutôt qu’un résultat précis mais trop long (voire impossible) à obtenir.
De part son importance pratique, ce problème a connu différentes approches ; cf.
par exemple les travaux autour du comptage probabiliste de Flajolet et Martin [87],
puis Durand et Flajolet [73] pour des algorithmes de plus en plus efficaces avec
leur analyse, jusqu’à Flajolet et al. [104] pour l’algorithme HyperLogLog en 2007.
Nous renvoyons à l’article de synthèse de Flajolet [82] pour une vue globale sur ce
problème, et nous intéressons ci-dessous à l’échantillonnage adaptatif, dont l’idée
initiale serait due à Wegman 25 et qui a été analysé lui aussi par Flajolet dans [81].
Cette méthode n’est sans doute pas la plus performante en pratique, mais son intérêt
dans le cadre de ce livre vient du fait que sa modélisation fait intervenir un trie. Une
variante est le comptage approché, dont l’algorithme initial, qui date de 1978, est dû
à Morris [189] et a été analysé quelques années plus tard par Flajolet [80].
Voyons donc l’algorithme de Wegman. Si ce n’est déjà le cas, un prétraitement
transforme les clés en une suite de bits grâce à une fonction de hachage σ , qui
associe à une clé x une valeur σ (x) ∈ {0, 1} ∞ . 26 En négligeant les collisions
dues au hachage, i.e., le fait que la fonction σ n’est en général pas injective, nous
introduisons une erreur de quelques pour cent, alors que l’erreur due à l’algorithme
est bien supérieure (l’analyse fine, cf. Flajolet [81], montre qu’elle est de l’ordre de
5 à 20 pour cent, et qu’elle diminue avec la taille de la mémoire de travail). Dans
l’exposé qui suit, nous identifions les clés x et les valeurs σ (x), et nous supposons
une distribution uniforme sur {0, 1} ∞ (si la distribution de départ n’est pas uniforme,
il existe des techniques permettant de rectifier ce biais lors du hachage).
L’algorithme travaille avec une suite de N clés que nous supposons être des
éléments de {0, 1} ∞ , un espace de travail en mémoire centrale pouvant contenir
m clés, et une variable entière δ, initialisée à 0, qui représente la « profondeur »
de l’échantillonnage. En pratique, N est « grand » et m est « petit ». L’algorithme
procède à une lecture séquentielle des clés, en gardant les clés distinctes ; il n’y a
donc aucune répétition parmi les clés présentes en mémoire. Les comparaisons et
recherches de clés se font en mémoire centrale, et sont supposées ici avoir un coût
négligeable par rapport à la lecture des N éléments. À chaque fois que les m places
sont allouées, l’algorithme ne garde, parmi les clés présentes en mémoire centrale à
ce moment, que celles commençant par 0, et augmente δ de 1. À tout instant, il y a
au plus m clés présentes en mémoire centrale ; ce sont celles commençant par 0 δ .
Lorsque la lecture des clés est finie, l’algorithme calcule une estimation
N de N
en fonction de la profondeur δ et du nombre ν de clés présentes alors en mémoire
centrale :
N = 2 δ ν.
25 Il ne semble pas y avoir eu d’article publié, et l’article [81] mentionne seulement une
« communication privée » de Wegman.
26 Une présentation des fonctions de hachage se trouve par exemple dans le livre de Knuth [156].