Filtre de Bloom
Un filtre Bloom est une structure de données qui permet aux ordinateurs de voir si un élément donné se trouve dans un ensemble. Les filtres Bloom utilisent pour cela des fonctions de hachage. Pour chaque élément qui est ajouté, une valeur de hachage est calculée. Lorsqu'un nouvel élément est ajouté, sa valeur de hachage est comparée à celle des autres éléments de l'ensemble. Un filtre Bloom est une structure de données probabiliste. Il est possible d'obtenir un faux positif, mais pas un faux négatif. En d'autres termes, une requête renvoie soit "peut-être dans l'ensemble", soit "certainement pas dans l'ensemble". Des éléments peuvent être ajoutés à l'ensemble, mais pas supprimés. Pour chaque élément ajouté, la probabilité d'obtenir un faux positif augmente.
Edward Bloom a proposé le filtre Bloom en 1970. Dans l'article, Bloom suppose qu'il existe un algorithme pour mettre un trait d'union entre les mots en fin de ligne. Selon l'exemple, la plupart des mots ont un schéma de césure simple. Mais environ 10 % des mots nécessitent de longues recherches pour trouver la bonne règle. Son cas est celui de la césure d'environ 500 000 mots. Il a vu que l'utilisation des techniques de hachage "normales" sans erreur, le stockage des modèles de césure, nécessiterait beaucoup de mémoire. Il a découvert qu'en utilisant sa technique, il pouvait éliminer la plupart des recherches. Par exemple, une zone de hachage de seulement 15 % de la taille requise par un hachage idéal sans erreur élimine encore 85 % des accès au disque.
Plus généralement, moins de 10 bits par élément sont nécessaires pour une probabilité de faux positif de 1 %, indépendamment de la taille ou du nombre d'éléments dans l'ensemble.
Questions et réponses
Q : Qu'est-ce qu'un filtre de Bloom ?
R : Un filtre de Bloom est une structure de données qui permet aux ordinateurs de voir si un élément donné apparaît dans un ensemble. Pour ce faire, il utilise des fonctions de hachage en calculant la valeur de hachage de chaque élément ajouté et en la comparant aux autres éléments de l'ensemble.
Q : Quel type de structure de données est un filtre de Bloom ?
R : Un filtre de Bloom est une structure de données probabiliste, ce qui signifie qu'il y a une possibilité d'obtenir des faux positifs mais pas de faux négatifs.
Q : Qui a proposé le filtre de Bloom ?
R : Edward Bloom a proposé le filtre de Bloom en 1970.
Q : Quel était l'exemple donné par Edward pour utiliser sa technique ?
R : L'exemple d'Edward était la césure d'environ 500 000 mots ; il a constaté qu'en utilisant sa technique, il pouvait éliminer la plupart des recherches et réduire les accès au disque de 15 %.
Q : Combien de bits par élément sont nécessaires pour une probabilité de faux positifs de 1 % ?
R : Moins de 10 bits par élément sont nécessaires pour une probabilité de faux positifs de 1 %, indépendamment de la taille ou du nombre d'éléments de l'ensemble.
Q : Est-il possible de supprimer des éléments d'un filtre bloom une fois qu'ils ont été ajoutés ?
R : Non, les éléments peuvent uniquement être ajoutés à l'ensemble mais pas supprimés.
Q : L'ajout de plus d'éléments augmente-t-il ou diminue-t-il la probabilité d'obtenir un résultat faussement positif ?
R : L'ajout de plus d'éléments augmente la probabilité d'obtenir un résultat faussement positif.
