Appartenance à un ensemble efficace avec Bloom Filter

Le filtre Bloom est une structure de données conçue pour tester si un élément est membre d'un ensemble. Il est utilisé dans diverses applications telles que la vérification orthographique, l'indexation de bases de données et les routeurs réseau qui nécessitent une méthode rapide et économe en mémoire pour tester l'appartenance à un ensemble. Les filtres Bloom sont des structures de données probabilistes, ce qui signifie qu'ils peuvent générer des faux positifs mais jamais de faux négatifs.

Avant d'expliquer Bloom Filter, comprenons d'abord le hachage. Le hachage est une technique permettant de réduire une grande quantité de données en une valeur de hachage plus petite de taille fixe, avec une faible probabilité que deux valeurs de données génèrent la même valeur de hachage (collision).

Mise en œuvre

Les filtres Bloom sont implémentés sous la forme d'un tableau de bits de N bits, tous mis à 0 au départ. Le tableau de bits représente l'ensemble et chaque élément est haché K fois à l'aide de différentes fonctions de hachage. Les valeurs de hachage K résultantes sont utilisées pour définir les bits correspondants dans le tableau de bits sur 1.

Pour vérifier l'appartenance, l'élément est à nouveau haché K fois et les bits résultants dans le tableau de bits sont vérifiés. Si tous les K bits sont définis sur 1, l'élément est considéré comme un membre de l'ensemble, bien qu'il soit possible que l'élément n'ait pas été réellement inséré dans l'ensemble, ce qui entraîne un faux positif.

La probabilité d'un faux positif est déterminée par la taille du tableau de bits, N, et le nombre de fonctions de hachage, K.

Cas d'utilisation

Supposons que nous ayons besoin de concevoir un système d'enregistrement des utilisateurs permettant aux utilisateurs de s'enregistrer avec un nom d'utilisateur et un mot de passe uniques. Pour vérifier si un nom d'utilisateur choisi est disponible, nous pouvons parcourir toute la base de données et rechercher une correspondance, mais il s'agit d'une méthode lente et gourmande en mémoire. Une meilleure solution consiste à utiliser un filtre Bloom.

Le filtre Bloom est initialisé avec un grand tableau de bits et un ensemble de fonctions de hachage. Le tableau de bits est initialement défini sur tous les zéros et les fonctions de hachage sont sélectionnées pour répartir uniformément les valeurs d'entrée sur le tableau de bits.

Lorsqu'un utilisateur tente de s'enregistrer, le nom d'utilisateur choisi est transmis via les fonctions de hachage, qui génèrent un ensemble d'index dans le tableau de bits. Le système vérifie alors la valeur des bits à ces index. Si tous les bits sont définis sur un, le système suppose que le nom d'utilisateur est déjà utilisé et refuse l'enregistrement. Si l'un des bits est défini sur zéro, le système peut confirmer que le nom d'utilisateur n'est pas utilisé et procède à l'enregistrement.

Une fois l'enregistrement terminé, le système définit les bits des index générés par les fonctions de hachage sur un, indiquant que le nom d'utilisateur est maintenant utilisé.

Ceci est un exemple simple de la façon dont un filtre Bloom peut être utilisé pour vérifier efficacement l'appartenance à un ensemble dans un système d'enregistrement de nom d'utilisateur. Bien qu'il existe une faible probabilité de faux positif, l'utilisation d'un contrôle secondaire peut atténuer efficacement cette limitation et garantir l'exactitude des résultats.

Exemple

Exécutons à sec un exemple d'implémentation d'un filtre Bloom dans un système d'enregistrement de nom d'utilisateur.

Nous considérons un filtre Bloom avec un tableau de bits de longueur 10 et trois fonctions de hachage.
Initialement, tous les bits du tableau de bits sont mis à 0.

Bit Array: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

h1("Rohit") = 8
h2("Rohit") = 2
h3("Rohit") = 7

Une fois l'enregistrement terminé, le système définit les bits des index générés par les fonctions de hachage sur un.

Bit Array: [0, 0, 1, 0, 0, 0, 0, 1, 1, 0]

h1("Mohit") = 2
h2("Mohit") = 8
h3("Mohit") = 5

Une fois l'enregistrement terminé, le système définit les bits des index générés par les fonctions de hachage sur un.

Bit Array: [0, 0, 1, 0, 0, 1, 0, 1, 1, 0]

h1("Rahul") = 2
h2("Rahul") = 5
h3("Rahul") = 7

Ceci est un exemple de faux positifs qui peuvent se produire lors de l'utilisation de filtres Bloom. Pour surmonter cela, le système effectue une vérification secondaire par rapport à la base de données pour confirmer la disponibilité du nom d'utilisateur.

Avantages et inconvénients

L'un des principaux avantages du filtre Bloom est son efficacité spatiale. Il utilise beaucoup moins de mémoire que d'autres structures de données, telles que les tables de hachage ou les arbres de recherche binaires, pour stocker les éléments définis. Un autre avantage est son fonctionnement à temps constant. La complexité temporelle du test d'appartenance est O(K), si K est le nombre de fonctions de hachage, quel que soit le nombre d'éléments dans l'ensemble.

Cependant, la nature probabiliste du filtre Bloom signifie qu'il n'est pas adapté aux applications où les faux positifs ne sont pas acceptables. Dans de tels cas, des structures de données alternatives, telles que des tables de hachage ou des arbres de recherche binaires, doivent être utilisées.

Le taux de faux positifs d'un filtre Bloom peut être réduit en augmentant la taille du tableau de bits ou le nombre de fonctions de hachage. Cependant, l'augmentation de la taille du tableau de bits augmentera également les besoins en mémoire du filtre. D'autre part, augmenter le nombre de fonctions de hachage augmentera la complexité temporelle du test d'appartenance. Trouver le compromis optimal entre la complexité spatiale et temporelle est une considération importante lors de l'utilisation des filtres Bloom.

Utilisations courantes

Les filtres Bloom sont utilisés dans une variété d'applications de conception de haut niveau en raison de leur efficacité et de leur nature probabiliste. Certains des cas d'utilisation courants sont : -
Moteurs de recherche Web : les filtres Bloom peuvent être utilisés pour stocker les URL des pages qui ont déjà été explorées, empêchant les moteurs de recherche de réexplorer les pages qui ont déjà été visitées.
Indexation de la base de données : Utilisation de filtres Bloom pour vérifier si une base de données contient un enregistrement spécifique, évitant ainsi la nécessité d'une analyse complète de la table.
Routage réseau : Filtrage des paquets réseau en vérifiant si leurs adresses de destination appartiennent à un ensemble d'adresses autorisées.
Vérification orthographique : Vérifier si un mot existe dans un grand dictionnaire.