Linear counting : comment estimer le nombre de valeurs distinctes

Comment pourrions-nous compter le nombre de valeurs distinctes dans un ensemble de données, si ces données sont vraiment très nombreuses ? Nous pouvons par exemple avoir un service qui mesure le nombre d’utilisateurs distincts d’un grand site web, ou même de tout un domaine en .fr/.com/.whatever, ou quelque chose du genre.

Méthode naïve

Bon, il n’y a pas de quoi se casser la tête : on parcourt les données et on range chaque valeur une seule fois dans une structure de données adaptée. En Python, on pourrait l’écrire à peu près ainsi (le code est inutilement bavard, c’est voulu) :

nonunique_values = [1, 2, 3, 2, 2, 4, 1, 1, 3, 5, 2]

def count_unique(values):
    found = set()
    for item in values:
        if item not in found:
            found.add(item)
    return len(found)

print count_unique(nonunique_values) # 5

Ça marche. D’accord, mais que se passe-t-il si ces données sont des identifiants uniques de 36 caractères (UUID v4) et s’il y a, mettons, dix millions de ces identifiants distincts ? Eh bien… le programme calcule toujours la bonne valeur, mais combien de mémoire prend-il ? Essayons de le calculer. Pour simplifier, supposons que nous stockons chaque UUID sous la forme d’une chaîne de 36 caractères. Un UUID occupe donc 36 octets et dix millions d’identifiants occupent 360 Mo.

Ce n’est pas rien, avouons-le. S’il y avait cent millions d’identifiants distincts, nous atteindrions déjà des gigaoctets de mémoire occupée. Et là, nous ne comptons encore que ce qu’occupent les données elles-mêmes. Ajoutez le surcoût en mémoire (overhead) de Python ou de JavaScript, et vous pouvez arriver à des gigaoctets même avec dix millions d’identifiants :

Tu ne veux pas de ça. Comment s’en sortir ?

Nous pouvons essayer de stocker les identifiants de façon plus efficace, nous pouvons utiliser le langage C à la place de Python, ce qui réduit fortement la consommation de mémoire, mais ce ne sera toujours pas ça et un tel programme occuperait encore une place incroyable. Reste à se poser la question : avons-nous vraiment besoin de savoir au poil près si le nombre de valeurs distinctes est exactement 9 563 618 ? Se passerait-il quelque chose si nous travaillions avec 9 547 666 ? Si ta réponse est oui et que tu tiens à la valeur exacte, alors à toi de voir. Sinon, voyons des méthodes pour estimer le nombre de valeurs distinctes dans un ensemble de données le plus précisément et le plus vite possible, avec un minimum de mémoire.

Les fonctions de hachage à la rescousse

Considérons une fonction de hachage qui prend une chaîne en entrée et renvoie en sortie un nombre de n bits. Si tu as plutôt l’habitude de fonctions de hachage qui « renvoient une chaîne », imagine simplement que cette chaîne est ensuite convertie en nombre, il n’y a rien de compliqué. Le nombre de bits indique la taille du nombre. Une fonction de 8 bits renvoie un nombre qui occupe huit bits, et huit bits permettent de stocker 2⁸ valeurs différentes, typiquement les entiers de 0 à 255. Nous allons travailler avec une fonction de hachage de 24 bits. Une telle fonction renvoie 2²⁴ valeurs différentes, soit 16 777 216.

Au lieu de stocker les valeurs elles-mêmes, nous allons stocker leurs empreintes (hash) de 24 bits. Pour stocker dix millions d’empreintes de 24 bits, il faut 30 Mo. C’est un ordre de grandeur de mieux que les 360 Mo de tout à l’heure. Le code pourrait ressembler à ceci :

def nhash(item, n):
    return hash(item) % (2 ** n)

nonunique_values = [1, 2, 3, 2, 2, 4, 1, 1, 3, 5, 2]

def count_unique_using_nhash(values):
    found = set()
    for item in values:
        checksum = nhash(item, 24)
        if checksum not in found:
            found.add(checksum)
    return len(found)

print count_unique_using_nhash(nonunique_values) # 5

La fonction hash est une fonction native de Python qui renvoie un entier ; la fonction nhash montre une implémentation naïve d’une fonction de hachage de n bits. Il n’est pas important de comprendre comment elle fonctionne, puisque de toute façon elle ne fonctionne pas correctement : son résultat n’occupe pas 24 bits, mais peu importe, c’est le principe qui m’intéresse.

Vient ensuite la fonction count_unique_using_nhash, qui compte les valeurs distinctes. Elle parcourt toutes les valeurs, calcule leur empreinte et la range dans la variable found, si cette valeur n’y est pas déjà.

Le problème de cette méthode est que la fonction de hachage peut renvoyer la même somme de contrôle (checksum) pour des chaînes différentes : il peut y avoir une collision. Plus il y a de collisions, plus le résultat est imprécis. La fonction count_unique_using_nhash renvoie presque toujours un nombre de valeurs distinctes plus petit que le nombre réel.

Et quelle fonction de hachage choisir ? Cela n’a pas tant d’importance, mais on recommande en général une variante de MurmurHash.

Tableaux de bits

Tu as été attentif pendant ton cours de programmation en C ? Si oui, tu connais les tableaux de bits. Comment pourrait-on s’en servir ?

Esquissons l’idée avec un tableau. En fait, nous n’avons pas besoin de conserver les sommes de contrôle calculées : nous pouvons créer un tableau de longueur 2²⁴ et initialiser tous ses éléments à zéro. Ensuite, chaque fois que nous rencontrons une somme de contrôle — qui est un nombre ! —, nous écrivons un 1 dans ce tableau à l’indice checksum, pour noter que nous avons déjà trouvé cette somme de contrôle. Le nombre de valeurs distinctes sera alors à peu près égal au nombre de 1 dans ce tableau. Le code pourrait ressembler à ceci :

def count_unique_using_array(values):
    # liste de longueur 2^24 initialisee a zero
    array = [0] * (2 ** 24) 
    for item in values:
        array[nhash(item, 24)] = 1
    return sum(array)

print count_unique_using_array(nonunique_values)

Seulement, utiliser un tableau est ici très gourmand en mémoire, car dans chaque case nous devons stocker soit un 1, soit un 0. À la place, nous pouvons utiliser un tableau de bits. Pour comprendre : un nombre entier (integer) peut être stocké par exemple sur 32 bits. Si nous convertissons le nombre 354 en binaire, nous obtenons 101100010. Le nombre 354 serait donc stocké dans l’ordinateur, comme entier de 32 bits (on ne s’occupe pas des détails, d’accord ?), ainsi :

00000000 00000000 00000001 01100010

C’est un format plutôt sympa, que nous pourrions exploiter, non ? Dans notre fonction, nous ne voulons stocker que des 1 et des 0, et nous venons de constater qu’un simple nombre n’est en fait rien d’autre qu’un tas de 0 et de 1 (comme tout dans un ordinateur, d’ailleurs…). Bref, grâce aux opérations bit à bit, nous pouvons stocker un 1 de façon qu’il occupe vraiment un seul bit.

Revenons à notre fonction avec le tableau. Si nous la réécrivions avec des tableaux de bits, un tableau de bits de taille 2²⁴ bits suffirait pour une fonction de hachage de 24 bits, soit 2 Mio. Voilà une belle amélioration !

Avec une fonction de hachage de 32 bits, qui a 2³² valeurs de sortie différentes, soit 4 294 967 296, il nous faudrait un tableau de bits d’une taille d’un demi-gigaoctet. Ce n’est pas si mal, puisque cela nous permet de compter des valeurs distinctes jusqu’à des milliards.

Linear Counting

J’ai déjà mentionné qu’avec une fonction de hachage, nous n’obtenons qu’une estimation du nombre de valeurs distinctes. Cette estimation est d’autant plus imprécise que le nombre de valeurs distinctes se rapproche du nombre de valeurs de sortie différentes de la fonction de hachage. Il est logique que, si un ensemble de données contient cinq milliards de valeurs distinctes, une fonction de hachage de 24 bits ne permette tout simplement pas de les compter.

Cependant, l’estimation obtenue avec des fonctions de hachage peut être encore affinée. On utilise pour cela une idée simple : plus il y a de valeurs distinctes dans l’ensemble de données, plus il est probable que des collisions finissent par apparaître. (Collision = deux entrées différentes ont la même sortie de la fonction de hachage, la même somme de contrôle.) Nous allons maintenant faire un peu de calcul, alors introduisons quelques variables :

• Nous travaillons avec une fonction de hachage h de n bits.
• Le nombre de toutes les sorties possibles de la fonction h est donc égal à 2n. Nous le notons par la lettre m, c’est-à-dire : m=2n.
• Le tableau de bits, dans lequel nous notons quelles sommes de contrôle nous avons trouvées, est noté par la lettre majuscule A. Le tableau A a pour longueur m.
• Quand notre algorithme a parcouru tout l’ensemble de données, certaines valeurs du tableau de bits sont égales à 0 et d’autres à 1. Ce qui nous intéressera surtout, c’est la proportion « nombre de zéros divisé par la longueur du tableau », qui donne la part relative de zéros dans le tableau de bits. Au début, cette proportion vaut 1, car le tableau est initialisé avec uniquement des zéros. Si c’était moitié-moitié, la proportion vaudrait un demi, etc. Nous notons cette valeur Z et la calculons ainsi : Z = nombre de zéros / m.

À ce stade, plus la valeur de Z est élevée, plus nous pouvons être sûrs que notre estimation du nombre de valeurs distinctes est précise. Si par exemple nous parcourons un ensemble de données vide, il ne reste que des zéros dans le tableau de bits et la valeur de Z est égale à un — nous avons alors une certitude complète que notre ensemble de données contient autant de valeurs distinctes qu’il y a de 1 dans le tableau de bits : zéro.

Si la valeur de Z est égale à 0,99, cela signifie que le tableau de bits est rempli de 1 à un centième. 99 % du tableau contient des zéros. C’est encore bien : il est probable qu’il n’y ait pas eu trop de collisions pendant le calcul et la correction sera peut-être nulle ou minime. Mais si la valeur de Z est égale à 0,05, seuls 5 % du tableau sont restés à zéro et nous avons probablement rencontré énormément de collisions — il faudra une grosse correction.

Mais comment calculer cette correction ? Nous nous aidons du logarithme, une fonction qui a cette allure :

Ce qui nous intéresse, c’est la partie rouge sur l’intervalle ]0 ; 1]. Si nous portons la valeur de Z sur l’axe des x, alors plus Z est grand, plus la valeur de y se rapproche de zéro. Et inversement : plus Z est petit, plus la valeur de y est petite. Nous obtenons l’estimation finale en multipliant ce nombre par -m. Remarque que, pour une valeur de Z suffisamment basse, nous obtenons un nombre qui est même inférieur à -1, et si nous multiplions cette valeur par -m, nous obtenons une estimation supérieure à m : nous avons estimé que le nombre de valeurs distinctes est supérieur au nombre de toutes les sommes de contrôle possibles que la fonction de hachage h peut produire.

La formule complète pour calculer le nombre p de valeurs distinctes s’écrit :

$$p=-m\cdot \ln Z$$

Une implémentation (sans tableaux de bits, avec de simples tableaux) pourrait ressembler à ceci :

from uuid import uuid4
from math import log

number_of_unique_values = 10000
nonunique_values = [uuid4() for _ in xrange(number_of_unique_values)]
nonunique_values += nonunique_values

def nhash(item, n):
    return hash(item) % (2 ** n)

def count_unique_using_array(values, n):
    array = [0] * (2 ** n)
    for item in values:
        array[nhash(item, n)] = 1
    return sum(array)

def linear_counting(values, n):
    estimate = count_unique_using_array(values, n)
    m = 2 ** n
    number_of_zeros = m - estimate
    Z = float(number_of_zeros) / m
    # log est ici le logarithme naturel de base e
    p = (-m) * log(Z)      
    p = int(round(p))
    print "Debug info: estimate=%s, m=%s, number_of_zeros=%s, Z=%s, p=%s" % \
          (estimate, m, number_of_zeros, Z, p)
    return p

print "Cardinality: %s" % linear_counting(nonunique_values, 16)

Dans la fonction linear_counting, nous calculons d’abord une première estimation grâce à l’algorithme précédent, qui utilise une fonction de hachage de n bits. Ensuite, nous calculons la proportion de zéros dans le tableau et nous appliquons la correction selon la formule. Le logarithme dans le code est le logarithme naturel. La variable nonunique_values contient number_of_unique_values chaînes distinctes ; dans cet exemple, la liste nonunique_values contient donc dix mille valeurs distinctes. Le code bizarre de la sixième ligne fait en sorte que le tableau contienne plusieurs fois les mêmes valeurs : on ajoute simplement à la fin de la liste la même liste de valeurs, et chaque valeur y figure donc deux fois. Et ensuite, on calcule. Idéalement, la fonction devrait indiquer que la liste contient dix mille valeurs distinctes. Sortie :

Debug info: estimate=9289, m=65536, number_of_zeros=56247, 
Z=0.858261108398, p=10017
Cardinality: 10017

Comme une liste nonunique_values différente est générée à chaque fois, les résultats varient d’un appel à l’autre. Nous avons utilisé une fonction de hachage de 16 bits. Nous voyons que la première estimation de la fonction count_unique_using_array était que la liste contient 9 289 valeurs distinctes. Avec la correction, nous avons affiné cette estimation à 10 017, ce qui est déjà plutôt honnête : notre estimation n’est supérieure que de 0,17 %, alors qu’avant elle était inférieure de 7,11 % — ce qui est beaucoup.

Si nous prenions une « plus grosse » fonction de hachage, par exemple de 24 bits, nous obtiendrions un résultat plus précis :

Debug info: estimate=9997, m=16777216, number_of_zeros=16767219, 
Z=0.999404132366, p=10000
Cardinality: 10000

L’estimation d’origine était déjà correcte, et l’affinage est arrivé pile à dix mille. Pour la démonstration, essayons avec un million d’identifiants distincts, c’est-à-dire number_of_unique_values = 1000000. Avec une fonction de hachage de 24 bits, nous obtenons ces résultats :

Debug info: estimate=971033, m=16777216, number_of_zeros=15806183, 
Z=0.94212192297, p=1000267
Cardinality: 1000267

Ça passe. Et pourtant, si nous l’implémentons avec un tableau de bits, le tableau ne devrait engloutir que les deux mégaoctets mentionnés (+ ce que consomme le langage). Pour moi, c’est plutôt bien. But we can do better! Much better. Mais ce sera pour la prochaine fois.

En attendant, tu peux lire l’article A Linear-Time Probabilistic Counting Algorithm for Database Applications [PDF]. Ou bien tu peux passer à l’épisode suivant de la série : l’algorithme Min Value.