LogLog : comment estimer le nombre de valeurs distinctes
Après les articles précédents sur le Linear Counting et sur Min Value, nous arrivons enfin à l’un des tout meilleurs algorithmes probabilistes pour estimer le nombre de valeurs distinctes dans un jeu de données : LogLog. Seul son petit frère HyperLogLog, qui découle de LogLog, fait encore mieux, mais nous en parlerons la prochaine fois.
Rappelons le problème. En entrée, nous avons un jeu de données, un multi-ensemble, par exemple un tableau (ou un générateur) d’identifiants. Dans ce tableau, certaines valeurs apparaissent plusieurs fois, et nous voulons compter le nombre de valeurs distinctes. Ce nombre s’appelle la cardinalité. Nous nous attendons à ce que cette cardinalité soit vraiment très grande, sinon nous pouvons utiliser des algorithmes classiques.
L’idée de l’algorithme LogLog
Imaginons que nous avons un ensemble de vecteurs binaires. N’aie pas peur : par exemple, 0001011001001100 est un vecteur binaire de longueur 16. Supposons que nous ayons des vecteurs binaires de longueur 32, un million au total, tous générés de façon totalement aléatoire. Combien de vecteurs se terminent par un 0 ?
Nous ne pouvons évidemment pas le savoir exactement, mais si les vecteurs ont vraiment été générés au hasard, environ la moitié devrait se terminer par 0, soit 500 000. Combien de vecteurs se terminent par 00 ? Un quart. Par 000 ? Un huitième. Et ainsi de suite. On peut le représenter à peu près ainsi :
motif du vecteur part parmi tous les vecteurs
...xxxxxx0 50 %
...xxxxx00 25 %
...xxxx000 12,5 %
...xxx0000 6,25 %
... ...
Si l’on s’intéresse à un suffixe (un suffixe est la chaîne par laquelle se termine une autre chaîne, le contraire d’un préfixe) de longueur d, on s’attend à trouver v vecteurs qui se terminent par ce suffixe. On calcule la valeur v ainsi :
où N est le nombre de tous les vecteurs de l’ensemble. Un suffixe de longueur 3 (par exemple …010) devrait apparaître dans 1/2^3 N = 1/8 N des vecteurs, soit 12,5 % de tous les vecteurs.
Maintenant, un petit moment de vertige. Prenons un multi-ensemble de 1 024 vecteurs distincts. Combien de vecteurs devraient se terminer par le suffixe 0000000000 (dix zéros) ? En remplaçant dans la formule, nous obtenons
Eh oui, un seul ! Parmi mille vecteurs binaires générés au hasard, il devrait y avoir exactement un vecteur qui se termine par dix zéros. Et comment utiliser cette information pour estimer le nombre d’éléments distincts ? Nous pouvons raisonner à l’envers. Et si nous parcourions tous les vecteurs binaires d’entrée et constations qu’il n’existe dans l’ensemble qu’un seul vecteur se terminant par dix zéros ? Alors nous pouvons estimer qu’il y avait 1 024 vecteurs dans l’ensemble !
Généralisation et construction de l’algorithme
L’objectif devrait être de trouver un suffixe contenu dans un seul vecteur, et le plus court possible. Mais c’est très difficile, car pour trouver réellement un tel vecteur, il faudrait mémoriser tous les suffixes, ce que nous ne voulons pas : cela prendrait beaucoup trop de mémoire. Nous nous contentons donc de chercher la plus longue suite de zéros à la fin d’un vecteur.
Nous parcourons donc tous les vecteurs, nous comptons pour chacun le nombre de zéros à la fin et nous gardons dans une variable le maximum de ces valeurs. Quand tous les vecteurs ont été parcourus, nous connaissons la longueur du plus long suffixe formé uniquement de zéros. Cette longueur se note d. Modifions maintenant la formule précédente pour isoler la variable N, c’est-à-dire pour que ce soit la sortie de l’algorithme et non l’entrée. À la place de v, nous pouvons mettre un, puisque nous nous attendons à trouver exactement un tel vecteur, c’est-à-dire que v=1.
Si nous trouvons la longueur d du plus long suffixe nul, nous estimons donc la cardinalité grâce à la formule N=2d.
Comment obtenir des vecteurs binaires aléatoires ?
Avec des vecteurs binaires aléatoires, l’algorithme fonctionne déjà, mais comment appliquer cette méthode à des données réelles ? Comme d’habitude, nous utilisons ici une bonne fonction de hachage. Si l’entrée est un jeu de données, par exemple des identifiants (des chaînes de caractères), nous commençons par calculer leur empreinte (hash). La sortie d’une fonction de hachage de n bits est formée de n bits qui, en pratique, ressemblent à des vecteurs binaires générés au hasard.
Nous pouvons maintenant écrire notre algorithme :
def trailing_zeroes(number):
if number == 0:
return 0
zeroes = 0
while (number & 1) == 0:
zeroes += 1
number = number >> 1
return zeroes
def count_unique(values):
max_zero_suffix_length = 0
for value in values:
zeroes_length = trailing_zeroes(hash(value))
max_zero_suffix_length = max(zeroes_length, max_zero_suffix_length)
return 2 ** max_zero_suffix_length
La fonction trailing_zeroes renvoie le nombre de zéros à la fin d’un nombre. Comment fait-elle ? Si tu n’as pas compris en lisant le code, mieux vaut ne pas poser la question. Et quel est son taux de réussite ? Pour un ensemble de cent mille valeurs distinctes, la fonction a renvoyé l’estimation 524 288.
Hmm…
Ce n’est pas terrible, n’est-ce pas ? Mais ce n’est pas grave ! Nous allons améliorer l’algorithme exactement comme pour l’algorithme précédent, Min Value. Nous répartissons les données d’entrée en plusieurs paquets (buckets) disjoints, nous calculons pour chaque paquet le suffixe nul maximal, puis nous calculons la longueur moyenne du suffixe nul et nous l’utilisons pour estimer le nombre de valeurs distinctes.
Nous pouvons par exemple décider que les deux derniers bits de chaque vecteur déterminent le numéro du paquet auquel appartient le vecteur. Ces six vecteurs
1101110111111011 1110110010100101
1011001111110010 1111101100000011
1010101000100000 0110010110011000
peuvent être répartis en quatre paquets selon leur terminaison :
00 01 1010101000100000 1110110010100101 0110010110011000 10 11 1011001111110010 1101110111111011 1111101100000011
Ensuite, nous calculons la longueur du plus long suffixe nul dans chaque vecteur, en sautant les bits utilisés comme numéro de paquet. Les « suffixes » nuls sont marqués en vert :
00 01 1010101000100000 1110110010100101 0110010110011000 10 11 1011001111110010 1101110111111011 1111101100000011 00: 3 01: 0 10: 2 11: 6
À la fin, nous avons les longueurs des plus longs suffixes nuls de chaque paquet. À partir de ces longueurs, nous pouvons calculer la moyenne arithmétique, qui vaut 2,75. Nous reportons cette valeur dans la formule et nous obtenons
Nous obtenons le nombre moyen de valeurs distinctes dans chaque paquet. Ce qui, bien sûr, ne colle pas du tout, mais ne nous en soucions pas : pour de petits ensembles, l’algorithme LogLog donne des résultats épouvantables.
Pour estimer la cardinalité de l’ensemble entier, il faut encore multiplier cette valeur par le nombre de paquets : 6,727 · 4 = 26,908. L’algorithme a calculé qu’il y a environ 27 valeurs distinctes dans l’ensemble. Il y en avait six, donc c’est complètement à côté, mais cela n’a vraiment aucune importance pour l’instant.
Implémentation de l’algorithme
def trailing_zeroes(number):
if number == 0:
return 0
zeroes = 0
while (number & 1) == 0:
zeroes += 1
number = number >> 1
return zeroes
def estimate_cardinality(values, k):
num_buckets = 2 ** k
max_zeroes = [0] * num_buckets
for value in values:
h = hash(value)
bucket_index = h & (num_buckets - 1)
bucket_hash = h >> k
num_zeros = trailing_zeroes(bucket_hash)
max_zeroes[bucket_index] = max(max_zeroes[bucket_index], num_zeros)
average_max_zeros = float(sum(max_zeroes)) / num_buckets
return (2 ** average_max_zeros) * num_buckets
Le paramètre k détermine combien de bits servent d’indice de paquet. Ce paramètre détermine la précision de l’algorithme : plus k est grand, plus la précision est grande. La variable bucket_index contient le numéro du paquet. Comment fonctionne cette magie à droite du signe égal ?
La variable num_buckets contient le nombre de paquets, qui est toujours une puissance de deux. Si par exemple k = 3, alors num_buckets=8. Le nombre 8 s’écrit 1000 en binaire. Si on lui retire un, on obtient le nombre 7, qui s’écrit 0111. En retirant un à num_buckets, on obtient toujours un nombre qui a k uns à la fin et uniquement des zéros avant. Nous effectuons ensuite un ET logique (c’est l’opérateur &). Pour le vecteur 1110110010100101, cette opération ressemble à ceci :
1110110010100101
& 0000000000000111
------------------
0000000000000101
Le but de toute cette magie est d’obtenir un nombre qui ne contient que des zéros au début et dont les k derniers bits sont les mêmes que ceux de l’empreinte h.
Nous calculons ensuite bucket_hash, c’est-à-dire l’empreinte d’origine privée de ses k derniers bits, en décalant toute l’empreinte de k bits vers la droite. Le décalage déplace simplement tous les bits du nombre de k positions vers la droite et complète le nombre à gauche avec des zéros. (Un décalage d’un bit vers la droite revient à diviser le nombre par deux et à jeter le reste.) Pour le vecteur 1110110010100101, après un décalage de trois, on obtiendrait 0001110110010100. Ce vecteur serait stocké dans la variable bucket_hash.
Ensuite, nous calculons le nombre de zéros à la fin de ce vecteur et, si cette valeur est supérieure au maximum actuel stocké dans le tableau max_zeroes à l’indice bucket_index, nous remplaçons la valeur.
À la fin, il ne reste qu’à calculer le nombre moyen de zéros dans tous les paquets, puis le nombre moyen de valeurs distinctes dans chaque paquet (2 ** average_max_zeros). Comme nous avons num_buckets paquets au total, nous multiplions cette valeur par le nombre de paquets, ce qui donne l’estimation finale du nombre de valeurs distinctes. Ouf, et ça n’a même pas fait mal. Voici les résultats pour plusieurs jeux de données qui contiennent 250 000 valeurs distinctes, avec k=10 :
331774.56203
323349.39265
307343.444439
309430.914045
294512.379123
Noooon, c’est encore faux :-(. Mais nous sommes déjà assez près, ne t’inquiète pas. Remarque que tous les résultats sont plus grands que le résultat exact. Pendant l’exécution de l’algorithme, diverses erreurs s’accumulent et l’estimation est donc nettement supérieure au résultat exact. Néanmoins, ces erreurs sont assez stables et on peut estimer leur ampleur. Si nous multiplions l’estimation par la constante de correction 0.79402, nous obtenons des résultats bien meilleurs :
263435.63774306054
256745.88475195298
244036.84175345476
245694.33437001088
233848.71927124445
J’ai aussi essayé un multi-ensemble de cardinalité un million. Résultats :
Résultat Erreur
1017297.17411 1.01729717411
1022820.99717 1.02282099717
984108.725487 0.984108725487
1018675.32683 1.01867532683
1007020.2853 1.0070202853
Très joli ! L’erreur reste sous 2,5 %, ce qui est une performance honorable. Et voilà, mesdames et messieurs, l’algorithme LogLog. L’implémentation finale, avec la constante de correction, ressemble à ceci :
def trailing_zeroes(number):
if number == 0:
return 0
zeroes = 0
while (number & 1) == 0:
zeroes += 1
number = number >> 1
return zeroes
def estimate_cardinality(values, k):
num_buckets = 2 ** k
max_zeroes = [0] * num_buckets
for value in values:
h = hash(value)
bucket_index = h & (num_buckets - 1)
bucket_hash = h >> k
num_zeros = trailing_zeroes(bucket_hash)
max_zeroes[bucket_index] = max(max_zeroes[bucket_index], num_zeros)
average_max_zeros = float(sum(max_zeroes)) / num_buckets
return (2 ** average_max_zeros) * num_buckets * 0.79402
Comment modifier cet algorithme pour obtenir le légendaire HyperLogLog, le meilleur de tous ? Nous le verrons la prochaine fois. Pour l’instant, regardons la consommation de mémoire de l’algorithme.
Consommation de mémoire
L’algorithme est très efficace du point de vue de la mémoire. La seule chose à retenir est le tableau des maxima. Sa longueur dépend de la valeur de k, c’est-à-dire du nombre de bits du vecteur pris comme indice de paquet. Pour un k donné, nous avons 2k paquets différents et le tableau des maxima a donc pour longueur 2k. Dans l’implémentation, nous avons appelé cette valeur num_buckets.
Quelle doit être la taille d’une case du tableau ? Nous y stockerons des longueurs de suffixes nuls. Je peux te dévoiler dès maintenant qu’une empreinte de 64 bits suffit probablement pour tous les multi-ensembles imaginables du monde. Nous devons donc pouvoir stocker dans ce tableau des nombres de 0 (un vecteur formé uniquement de uns) à 64 (un vecteur formé uniquement de zéros). De plus, si nous supposons que k est toujours supérieur à zéro, il nous suffit de stocker des nombres de 0 à 63. Pour cela, 6 bits suffisent, car 26 = 64.
Oui, il nous suffit d’un « tableau » dont chaque case occupe 6 bits. Je peux aussi te dire que la valeur k=10 suffit pour estimer assez bien une cardinalité de l’ordre de plusieurs centaines de millions. Un algorithme réglé ainsi créerait un tableau de taille 210 = 1 024, dont chaque case occupe 6 bits. Au total, ce tableau occuperait 6 144 bits, soit 768 octets. Même pas un kilo-octet.
Et c’est tout.
Nous n’avons besoin de rien stocker d’autre : les empreintes calculées peuvent être jetées aussitôt, il nous suffit de connaître le nombre de zéros à la fin du vecteur.
Remarque que si tu utilisais une fonction de hachage plus grande, qui renverrait par exemple 128 bits, la consommation de mémoire ne changerait presque pas. Il faudrait alors stocker des nombres de 0 à 127, ce qui demande 7 bits. C’est donc surtout le paramètre k, c’est-à-dire le nombre de paquets, qui détermine la consommation de mémoire.
LogLog convient surtout quand nous devons compter des multi-ensembles de très grande cardinalité. Comme on l’a vu dans le petit exemple plus haut, LogLog se débrouille moins bien avec les multi-ensembles de petite cardinalité. On peut néanmoins y remédier, par exemple ainsi : si nous constatons que le multi-ensemble a une faible cardinalité, nous utilisons un autre algorithme pour l’estimation, par exemple le Linear Counting décrit plus tôt. Nous en reparlerons aussi la prochaine fois.
Sources :
- Loglog Counting of Large Cardinalities [PDF]
- Damn Cool Algorithms: Cardinality Estimation (le code de LogLog en est plus ou moins pompé)
Chapitres: Linear counting : comment estimer le nombre de valeurs distinctes, Min Value : comment estimer le nombre de valeurs distinctes, LogLog : comment estimer le nombre de valeurs distinctes, HyperLogLog : comment estimer avec précision le nombre de valeurs distinctes
