Filtre de Bloom

Un filtre de Bloom stocke m bits, initialement à zéro. Insérer une chaîne met à un ses k positions de hachage. Une interrogation vérifie les mêmes positions : tout bit à zéro signifie certainement absente ; tous à un signifie seulement peut-être présente. Avec des paramètres fixes et sans suppression, les chaînes insérées ne peuvent pas devenir des faux négatifs. La référence pédagogique séparée stocke les chaînes exactes uniquement pour identifier l’appartenance vraie et les faux positifs ; son stockage supplémentaire n’est pas inclus dans les m bits du filtre.

Choisissez un entier m de 8 à 1024 et k de 1 à 12, puis créez le filtre. Modifier l’un ou l’autre paramètre écarte le filtre actif jusqu’à ce qu’il soit recréé. Réinitialiser efface le filtre et conserve les champs. Les chaînes ont 1–256 unités de code UTF-16 ; au plus 1024 chaînes différentes sont conservées. La comparaison est exacte et sensible à la casse : il n’y a ni trim ni normalisation Unicode. Les espaces comptent, beaucoup d’émojis occupent deux unités de code, et les accents composés et décomposés sont des chaînes distinctes. La dernière chaîne est affichée avec des guillemets et échappements JSON pour rendre identifiables les espaces et caractères de contrôle. Une insertion en double laisse le tableau de bits, le compte d’entrées distinctes et les compteurs de requêtes inchangés.

L’implémentation conserve sa variante de hachage 32 bits de type FNV-1a sur les unités de code UTF-16 JavaScript, plutôt que les octets du FNV-1a standard. Chaque unité est combinée par XOR dans le hachage et multipliée par 16777619 modulo 2³². Les deux valeurs initiales sont 2166136261 et 0xdeadbeef ; le second résultat est rendu impair. Les positions réelles sont (h₁ + i h₂) mod m pour i = 0…k−1. L’arithmétique est réduite modulo m sans enroulement 32 bits intermédiaire. Les positions répétées sont autorisées : un pas impair ne garantit pas un cycle complet pour un m arbitraire. Le tableau d’opération montre chaque position dans l’ordre, y compris les répétitions. Une insertion dans un bit déjà à un le laisse simplement à un. Les deux hachages de base sont disponibles dans Détails. C’est une implémentation pédagogique déterministe, non cryptographique, et non une affirmation que les hachages sont indépendants et uniformes.

Le taux de faux positifs observé est le nombre de faux positifs divisé par les requêtes pour des chaînes réellement absentes de l’ensemble de référence. Les requêtes de chaînes insérées n’entrent dans aucun compteur. Une nouvelle insertion distincte réinitialise les compteurs parce que l’ensemble de référence et éventuellement les bits ont changé. Sans aucune requête négative, le taux est indéfini. Les requêtes répétées comptent comme des demandes répétées ; des requêtes choisies à la main ne sont pas un échantillon aléatoire indépendant et le taux affiché n’est pas une garantie pour de futures chaînes.

Détails montrent l’approximation classique f ≈ (1 − exp(−kn/m))ᵏ pour n entrées distinctes et des hachages idéaux indépendants uniformes. Ce n’est pas le taux exact de ce filtre déterministe fini. L’exemple a…h insère ces huit chaînes ASCII dans le filtre courant. Avec m = 8 et k = 1 elles remplissent chaque bit, donc toute nouvelle chaîne est un faux positif. Pour un exemple plus petit, insérez seulement a, puis interrogez i, a et b : i est un faux positif, a vraiment présent et b absent ; le taux observé est 1/2, parce que seulement deux requêtes sont négatives.

Les paramètres et brouillons bruts, entrées, compteurs de requêtes, dernière opération et détails ouverts sont enregistrés localement jusqu’à 100000 caractères sérialisés. Au-delà, la copie précédente est conservée avec un avertissement ; exportez toute la session avant de recharger ou de quitter la page. La navigation interne conserve la session courante. Session exporte du JSON et importe une session validée jusqu’à 2 MiB avec toutes les entrées de référence. Un import invalide conserve le filtre actuel. Les anciens états enregistrés restent lisibles. Réinitialiser efface le filtre et conserve les brouillons. Aucune suppression, variante à compteurs, protection cryptographique ou mesure de performance n’est fournie.

Sources : Bloom (1970), Method 2 and Eq. 1, original-paper mirror ; Kirsch and Mitzenmacher (2008), §§2 and 5.2 ; RFC 9923, FNV basics.

La dernière requête ou insertion apparaît en premier. Les bits marqués montrent les positions utilisées. Ouvrez Positions de hachage pour les valeurs avant/après dans leur ordre, et Modèle et hachages pour l’estimation idéale et les hachages de base. Le taux observé ne compte que les requêtes de chaînes absentes ; les requêtes manuelles ne sont pas un échantillon aléatoire.

Les bits conservent une taille de cellule fixe et lisible. La grille s’adapte à la largeur disponible, jusqu’à 64 colonnes ; les petits filtres gardent leur largeur naturelle. Les grilles hautes défilent localement. Les contours orange marquent les positions de la dernière opération.