Accueil▸Informatique distribuée et parallèle▸Filtre de Bloom — Appartenance probabiliste à un ensemble

🌸 Filtre de Bloom — Appartenance probabiliste à un ensemble

Ajoutez des éléments à un tableau de bits via k fonctions de hachage et testez leur appartenance. Les filtres de Bloom ne produisent jamais de faux négatif mais peuvent produire des faux positifs — ajustez la taille du tableau de bits et le nombre de hachages et observez le taux de faux positifs.

Informatique distribuée et parallèle3DModéré60 FPS

À propos du filtre de Bloom

Un filtre de Bloom est une structure de données probabiliste qui répond aux requêtes d'appartenance en temps O(1) et en espace O(m), où m est la taille du tableau de bits — bien plus petit que de stocker les éléments eux-mêmes. Lorsque vous insérez un élément, k fonctions de hachage indépendantes le font correspondre à k positions dans un tableau de m bits et mettent ces bits à 1. Pour tester l'appartenance, les mêmes k positions sont vérifiées : si l'une est à 0, l'élément est définitivement absent ; si toutes sont à 1, il est probablement présent. Les bits ne sont jamais réinitialisés, donc les faux négatifs sont impossibles, mais les collisions de hachage peuvent produire des faux positifs dont la probabilité est approximée par (1 − e^(−kn/m))^k, où n est le nombre d'éléments insérés.

Ce simulateur vous permet de saisir des mots et de les ajouter à une visualisation en direct du tableau de bits, d'interroger l'appartenance pour voir apparaître des faux positifs à mesure que le tableau se remplit, et d'ajuster la taille du tableau m et le nombre de hachages k via des curseurs. Le taux de faux positifs théorique et le taux mesuré sur 2 000 requêtes de test aléatoires se mettent à jour en temps réel, rendant immédiatement visible le compromis entre espace et précision.

Questions fréquentes

Pourquoi un filtre de Bloom ne peut-il jamais produire de faux négatif ?

Lorsqu'un élément est inséré, ses k positions de bits hachées sont toutes mises à 1 et ne sont jamais réinitialisées. Par conséquent, si vous testez un élément réellement inséré, les k bits seront tous à 1 et le filtre indiquera correctement « probablement dans l'ensemble ». Un faux négatif nécessiterait qu'un bit repasse à 0, ce qui n'arrive jamais.

Quelle est la formule de la probabilité de faux positif ?

Après avoir inséré n éléments dans un tableau de m bits avec k fonctions de hachage, la fraction de bits encore à 0 est d'environ e^(-kn/m), donc la probabilité que les k positions d'un non-membre soient toutes à 1 est (1 - e^(-kn/m))^k. Par exemple, avec m = 64, k = 3 et n = 10 éléments, le taux de faux positifs est d'environ 5 %.

Comment choisir le nombre optimal de fonctions de hachage k ?

La valeur k = (m/n) x ln 2 minimise le taux de faux positifs pour un m et un n donnés. Trop peu de hachages laissent de nombreux bits non définis et réduisent la discrimination ; trop de hachages remplissent rapidement le tableau et augmentent les collisions. Pour un taux d'erreur cible de 1 %, la taille optimale du tableau est d'environ 9,6 bits par élément inséré.

Pourquoi ne peut-on pas supprimer des éléments d'un filtre de Bloom standard ?

Supprimer un élément nécessiterait de réinitialiser ses k positions de bits, mais ces bits peuvent aussi avoir été définis par d'autres éléments insérés, donc les réinitialiser introduirait silencieusement des faux négatifs pour ces éléments. Un filtre de Bloom à compteurs remplace chaque bit par un petit compteur, incrémenté à l'insertion et décrémenté à la suppression, pour permettre une suppression sûre au prix d'une mémoire supplémentaire.

⚙ Sous le capot

Un filtre de Bloom teste l'appartenance à un ensemble avec k fonctions de hachage sur un tableau de bits : aucun faux négatif, faux positifs ajustables. Observez les bits s'allumer et le taux d'erreur suivre (1−e^(−kn/m))^k.

Filtre de Bloomhachagefaux positifprobabilisteCanvas 2D

3D · Moteur Three.js / WebGL · Cible 60 FPS · fonctionne entièrement côté client, sans installation