Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Filtre de Bloom
Résumé
En informatique, et plus précisément en algorithmique, un filtre de Bloom est une structure de données inventée par Burton Howard Bloom en 1970. C'est une implémentation du type abstrait Ensemble. Cette structure est probabiliste, c'est-à-dire qu'elle utilise des probabilités, et que sa correction est probabiliste. Plus précisément, lors du test de la présence d'un élément dans un ensemble, un filtre de Bloom permet de savoir :
avec certitude l'absence d'un élément (il ne peut pas y avoir de faux négatif) ;
avec une certaine probabilité la présence d'un élément (il peut y avoir des faux positifs).
La taille d'un filtre de Bloom est fixe et indépendante du nombre d'éléments contenus, ce qui en fait une structure très compacte. L'inconvénient est toutefois qu'il y a d'autant plus de faux positifs qu'il y a d'éléments dans la structure. Le principe du filtre est le même que pour le hachage.
Un filtre de Bloom est constituée d'un tableau de bits de taille m, ainsi qu'une collection de k fonctions de hachage . Chaque fonction de hachage associe tout élément à une case du tableau.
En général, k est une constante qui dépend du taux de faux positifs souhaité, tandis que m est proportionnel à k et au nombre d'éléments à ajouter.
Soit U l'univers de tous les éléments que pourrait contenir l'ensemble considéré. Par exemple, U est l'ensemble des entiers sur 32 bits, ou un ensemble de mots. Le filtre a deux composantes :
T : un tableau de bits de taille m dont chaque case est initialisée à 0. (indexé de 1 à m)
k fonctions de hachage de .
Pour ajouter un élément , on met des 1 dans les cases d'indice .
Pour tester si un élément est présent, on vérifie que les cases d'indice contiennent toutes un 1. Il se peut que le test d'appartenance renvoie vrai alors que l'élément est absent, c'est un faux positif.
Les éléments ne peuvent pas être retirés de l'ensemble (bien que cela soit possible avec certaines variantes telles que les ).
Le filtre de Bloom utilise un espace constant. C'est son principal intérêt.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.