Filtre de Bloom : absence certaine, présence probable

Chaque mot met à 1 k bits parmi les m bits du filtre. Pour rechercher un mot, on vérifie ses k bits : un seul 0 suffit à prouver son absence ; s'ils valent tous 1, sa présence reste seulement probable. Insérez les mots pas à pas, puis saisissez un mot de votre choix.

Exemple résolu — Filtre de Bloom : absence certaine, présence probable

Bits à 1	20 sur 64 (31,3 %)
Bits par mot	8,00
k optimal selon l'estimation classique	5,55
Estimation classique du taux de faux positifs	3,06 %
Estimation à partir des bits réellement à 1	3,05 %
Mesure sur 10 000 chaînes jamais insérées	335 sur 10 000 (3,35 %)
Mots insérés déclarés « absents à coup sûr »	0 sur 8

Ce sont les valeurs affichées par le calculateur à l’ouverture de la page. Modifiez une entrée ci-dessus pour les recalculer.

Chargement de la simulation interactive...

Leçon

Un filtre de Bloom indique si un élément appartient à un ensemble, à l'aide d'un tableau de m bits et de k fonctions de hachage. Insérer un élément met à 1 les k bits désignés par ses valeurs de hachage. Une recherche vérifie ces mêmes k bits : si l'un d'eux vaut 0, l'élément est absent à coup sûr ; s'ils valent tous 1, il est probablement présent. Une réponse « probablement présent » erronée est un faux positif. Après l'insertion de n éléments, l'estimation classique du taux de faux positifs est (1 − e^−kn/m)^k. Cette approximation exponentielle de la formule donnée par Bloom en 1970 atteint son minimum pour k = (m/n) ln 2.

Ce que signifie chaque symbole

m: le nombre de bits du filtre
k: le nombre de fonctions de hachage, donc de bits mis à 1 par chaque mot et vérifiés à chaque recherche
n: le nombre de mots insérés
X: le nombre de bits à 1 une fois les n mots insérés

Suppose: Les k positions d'un mot sont obtenues par double hachage, à partir de deux valeurs : la position i vaut (h₁ + i·h₂) mod m. Ici, h₁ est la valeur de hachage FNV-1a du mot ; h₂ est une valeur issue du hachage djb2, mélangée puis rendue impaire. Comme m est une puissance de deux, les k positions d'un mot sont toujours distinctes. L'estimation classique suppose que chacune des kn positions est choisie au hasard, indépendamment des autres. Le double hachage et une petite valeur de m peuvent donc créer un écart entre l'estimation et le comportement réel du filtre. Le taux de faux positifs est mesuré sur les 10 000 chaînes de 0 à 9999 : il est exact pour ces chaînes, mais ne décrit pas tous les mots possibles.

Seize fonctions de hachage font moins bien qu'une seule 🖖

Cliquez sur Cinq fonctions et lisez le tableau sous les résultats. Avec 128 bits et 16 mots, une fonction de hachage laisse passer 12,82 % des chaînes jamais insérées ; cinq en laissent passer 2,50 %, le minimum de la colonne ; seize, 32,01 %, soit davantage qu'une seule. Chaque fonction supplémentaire ajoute un bit à vérifier lors d'une recherche, ce qui réduit le risque de faux positif. Mais elle ajoute aussi un bit à mettre à 1 à chaque insertion, ce qui augmente ce risque. D'une à cinq fonctions, le taux baisse à chaque étape. Ensuite, il remonte, avec un léger creux à quinze. Bloom avait repéré le point de bascule en 1970 : il se situe lorsque la moitié environ des bits valent 1. Avec cinq fonctions de hachage, c'est le cas de 60 bits sur ces 128, et l'estimation classique donne pour k optimal (m/n) ln 2 = 8 × 0,693 = 5,55.

Compter les bits à 1 donne une meilleure estimation 🖖

Cliquez sur Seize fonctions. L'estimation classique annonce 9,76 % ; le filtre laisse passer 32,01 % des chaînes jamais insérées. Cette estimation suppose que 128 × (1 − e⁻²) = 110,7 bits sont à 1. Or ces seize mots en mettent 119 à 1. Élevez la proportion réelle à la puissance seize, (119/128)¹⁶ : vous obtenez 31,15 %, une valeur proche du taux mesuré. Lorsque k est aussi grand, quelques bits à 1 supplémentaires pèsent lourd, car chacun des seize bits vérifiés doit valoir 1. Parmi tous les réglages de cette page qui produisent au moins un faux positif, l'estimation fondée sur les bits réellement à 1 est la plus proche du taux mesuré, en termes de rapport à ce taux, dans 5 356 cas sur 6 051. Un filtre réel peut compter ses propres bits à 1 et ainsi mieux estimer son taux qu'avec la formule classique. Ces seize noms d'animaux constituent aussi un tirage défavorable : sur 150 autres ensembles de seize mots, un filtre de cette taille donne un taux moyen de 14,4 %, encore supérieur à l'estimation.

Supprimer un mot en fait disparaître un autre 🖖

Cliquez sur Supprimer owl et avancez jusqu'à la fin. owl a mis à 1 les bits 37, 58 et 15. Inséré juste après, fox utilisait les positions 14, 15 et 16 ; le bit 15 valait donc déjà 1. Remettre à 0 les bits de owl remet aussi à 0 le bit 15 de fox. La recherche de fox donne alors « absent à coup sûr », alors que le mot est bien dans le filtre. C'est un faux négatif, l'erreur qu'un filtre de Bloom garantit de ne jamais commettre. Un bit indique seulement qu'un mot l'a mis à 1, sans garder trace duquel. On ne peut donc remettre aucun bit à 0 en toute sécurité. Dans ce filtre de 64 bits, six des huit mots entraîneraient la perte d'un autre mot si on les supprimait. La solution habituelle consiste à remplacer chaque bit par un petit compteur : on ajoute une unité lors d'une insertion et on en retire une lors d'une suppression. Cela demande davantage de mémoire.

Combien de bits pour le filtre de césure de Bloom en 1970 ? 4 étapes
En 1970, Burton Bloom prenait l'exemple d'un programme de coupure des mots en fin de ligne, portant sur 500 000 mots. Quelques règles simples suffisent pour 450 000 d'entre eux ; les 50 000 autres doivent être recherchés dans un dictionnaire sur disque. Il proposait de conserver en mémoire centrale un filtre contenant ces 50 000 mots, en acceptant qu'un mot facile sur 16 provoque un accès inutile au disque. Combien faut-il de bits et de fonctions de hachage ? Combien de lectures sur disque reste-t-il ? Réglez ensuite cette page sur le même nombre de bits par mot et mesurez le résultat.

Ouvrez ce problème dans l'outil
1. Pour k optimal, l'estimation classique demande log₂(1/p) / ln 2 bits par mot. Avec p = 1/16, cela donne 4 / 0,6931 = 5,77 bits. Le filtre occupe donc 50 000 × 5,77 = 288 539 bits. Bloom annonçait lui-même « moins de 300 000 bits ». La valeur optimale de k est 5,77 × ln 2 = 4. Avec quatre fonctions de hachage, on s'attend à ce que la moitié des bits valent 1.
  
  $\frac{lo g _{2} 16}{ln 2} = \frac{4}{0.6931} = 5.77 bits per word, 50000 \times 5.77 = 288539 bits, k = 5.77 \times ln 2 = 4$
2. Chacun des 50 000 mots difficiles exige toujours une lecture sur disque, ainsi que 1 mot facile sur 16, soit 450 000 / 16 = 28 125 lectures supplémentaires. Cela fait 78 125 lectures sur disque pour 500 000 mots, soit 15,6 %. Bloom arrondissait ce nombre à 78 000, ce qui représente une économie de 84 % par rapport à une lecture sur disque pour chaque mot.
  
  $50000 + \frac{450 000}{16} = 78125 disk reads of 500000 (15.6%)$
3. La longueur du mot n'intervient nulle part. Le filtre occupe 5,77 bits par mot, qu'il s'agisse de « cat » ou de « incomprehensibilities ». Bloom estimait qu'une table de hachage classique exigeait au moins 19 bits en moyenne pour représenter chaque mot. Chaque division de p par deux ajoute 1 / ln 2 = 1,44 bits par mot : pour 1 sur 64, il faudrait 6 / 0,6931 = 8,66 bits.
  
  $\frac{1}{l n 2} = 1.44 bits per halving of p, \frac{6}{0.6931} = 8.66 for p = \frac{1}{64}$
4. Cette page accepte au plus 64 mots, mais l'estimation dépend seulement de m/n et de k. Réglez m = 256, n = 44 (5,82 bits par mot) et k = 4. Sur les 256 bits, 122 valent 1, soit 47,7 %. Parmi les 10 000 chaînes jamais insérées, 535 donnent la réponse « probablement présent » : le taux mesuré est de 5,35 %, inférieur à l'objectif de 1/16 = 6,25 % retenu pour dimensionner le filtre. L'estimation classique pour ce filtre est de 6,11 %.
  
  $\frac{256}{44} = 5.82 : \frac{535}{10 000} = 5.35% < \frac{1}{16} = 6.25%$
Réponse

288 539 bits et 4 fonctions de hachage, avec 78 125 lectures sur disque pour 500 000 mots. Les 44 mots de cette page, dans 256 bits, donnent un taux mesuré de 5,35 %, conforme à l'objectif. Cette mesure porte sur un seul filtre de 44 mots. La page ne permet pas de vérifier si 50 000 mots dans 288 539 bits donneraient un taux aussi proche de 1/16 : elle est limitée à 64 mots.

$288539 bits, k = 4, 78125 disk reads$

Parcours

Références (1)

The method itself, the turning point at half the bits set in the first insight, and the hyphenation example the worked problem recomputes: Burton H. Bloom, "Space/time trade-offs in hash coding with allowable errors," Communications of the ACM 13(7), July 1970, pp. 422–426.

Par l’équipe 42Math · Vérifié sur des sources publiées. Corrections bienvenues.

Filtre de Bloom : absence certaine, présence probable

La théorie — Filtre de Bloom : absence certaine, présence probable

Ce que signifie chaque symbole

Seize fonctions de hachage font moins bien qu'une seule 🖖

Compter les bits à 1 donne une meilleure estimation 🖖

Supprimer un mot en fait disparaître un autre 🖖

Problème entièrement résolu

Ce qu’une structure de données rend peu coûteux