Comment trouver le nombre d'éléments dans un flux de données - mannequins

Même si un filtre Bloom peut suivre les objets arrivant d'un flux, il ne peut pas dire combien il y a d'objets. Un vecteur bit rempli par un peut (en fonction du nombre de hashs et de la probabilité de collision) cacher le vrai nombre d'objets hachés à la même adresse.

La connaissance du nombre d'objets est utile dans diverses situations, par exemple lorsque vous souhaitez connaître le nombre d'utilisateurs distincts ayant consulté une page de site Web ou le nombre de requêtes de moteur de recherche distinctes. Stocker tous les éléments et trouver les doublons parmi eux ne peut pas fonctionner avec des millions d'éléments, en particulier venant d'un flux. Lorsque vous voulez connaître le nombre d'objets distincts dans un flux, vous devez toujours utiliser une fonction de hachage, mais l'approche consiste à prendre une esquisse numérique.

Esquisse signifie prendre une approximation, c'est une valeur inexacte mais pas complètement fausse comme réponse. L'approximation est acceptable car la valeur réelle n'est pas trop éloignée. Dans cet algorithme intelligent, HyperLogLog, basé sur la probabilité et l'approximation, vous observez les caractéristiques des nombres générés à partir du flux. HyperLogLog est issu des études des informaticiens Nigel Martin et Philippe Flajolet. Flajolet a amélioré son algorithme initial, Flajolet-Martin (ou l'algorithme LogLog), dans la version plus robuste de HyperLogLog, qui fonctionne comme ceci:

1. Un hachage convertit chaque élément reçu du flux en un nombre.
2. L'algorithme convertit le nombre en binaire, la norme numérique de base 2 que les ordinateurs utilisent.
3. L'algorithme compte le nombre de zéros initiaux dans le nombre binaire et les traces du nombre maximum qu'il voit, qui est n.
4. L'algorithme estime le nombre d'éléments distincts passés dans le flux en utilisant n. Le nombre d'éléments distincts est 2 ^ n.

Par exemple, le premier élément de la chaîne est le mot chien. L'algorithme le transforme en entier et le convertit en binaire, avec un résultat de 01101010. Seul un zéro apparaît au début du nombre, l'algorithme l'enregistre comme le nombre maximal de zéros finaux vus. L'algorithme voit alors les mots perroquet et loup, dont les équivalents binaires sont 11101011 et 01101110, laissant n inchangé. Cependant, lorsque le mot cat passe, la sortie est 00101110, donc n devient 2. Pour estimer le nombre d'éléments distincts, l'algorithme calcule 2 ^ n, c'est-à-dire 2 ^ 2 = 4. La figure montre ce processus.

Compter uniquement les zéros en tête.

L'astuce de l'algorithme est que si votre hash produit des résultats aléatoires, équitablement répartis (comme dans un filtre Bloom), en regardant la représentation binaire, vous pouvez calculer la probabilité qu'une séquence de zéros apparaisse. Parce que la probabilité qu'un nombre binaire unique soit 0 est une sur deux, pour calculer la probabilité de séquences de zéros, il suffit de multiplier cette probabilité 1/2 autant de fois que la longueur de la séquence de zéros:

• 50% (1/2) probabilité pour les nombres commençant à 0
• 25% (1/2 * 1/2) probabilité pour les nombres commençant par 00
• 12. 5% (1/2 * 1/2 * 1/2) probabilité pour les nombres commençant à 000
• (1/2) ^ k probabilité pour les nombres commençant par k zéros (vous utilisez les puissances pour les calculs plus rapides de nombreuses multiplications de la même nombre)

Moins il y a de chiffres visibles par HyperLogLog, plus grande est l'imprécision. La précision augmente lorsque vous utilisez le calcul HyperLogLog plusieurs fois en utilisant différentes fonctions de hachage et que vous calculez la moyenne des réponses de chaque calcul, mais le hachage de nombreuses fois prend du temps et les flux sont rapides. Vous pouvez également utiliser le même hachage, mais diviser le flux en groupes (par exemple, en séparant les éléments en groupes à leur arrivée en fonction de leur ordre d'arrivée) et, pour chaque groupe, suivre le nombre maximal de zéros de fin. En fin de compte, vous calculez l'estimation de l'élément distinct pour chaque groupe et calculez la moyenne arithmétique de toutes les estimations. Cette approche est un moyennage stochastique et fournit des estimations plus précises que l'application de l'algorithme à l'ensemble du flux.