Loading AI tools
Structure de données probabiliste, utilisant des fonctions de hachage pour enregistrer un ensemble d’éléments dans un espace mémoire limité, et permettant de vérifier si un élément donné appartient à l’ensemble. De Wikipédia, l'encyclopédie libre
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, un test d'appartenance renvoie soit « peut-être dans l'ensemble » ou « assurément pas dans l'ensemble ». Dit autrement, il n'y a jamais de faux négatif mais il peut y avoir des faux positifs.
La taille occupée en mémoire 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é 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[1]. 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 qui peuvent potentiellement être ajoutés au filtre de Bloom. Par exemple, U est l'ensemble des entiers sur 32 bits, ou un ensemble de mots. Le filtre a deux composantes[2] :
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 filtres de Bloom par comptage (en)).
Le filtre de Bloom utilise un espace constant. En effet, l'espace mémoire est occupé par le tableau de bits de taille k, et k est une constante par rapport au nombre n d'éléments présents dans la structure. C'est son principal intérêt.
On rappelle qu'un faux-positif est un élément déclaré « peut-être dans l'ensemble » alors qu'il n'y est pas. Évaluons la proportion de faux-positifs en fonction de divers paramètres. On suppose qu'une fonction de hachage sélectionne chaque case du tableau de manière équiprobable, et que m représente le nombre de bits dans le tableau, alors la probabilité qu'un bit donné soit laissé à 0 par une fonction de hachage donnée lors de l'insertion d'un élément vaut .
Généralisons ceci à k fonctions de hachage qui n'ont pas de corrélation entre elles. La probabilité qu'un bit donné soit laissé à 0 par ces k fonctions de hachage lors de l'insertion d'un élément est .
Si l'on considère à présent que l'on insère n éléments, la probabilité qu'un bit donné vaille 0 vaut . On en déduit que la probabilité que ce bit vaille 1 est
Ainsi, si l'on teste la probabilité de présence d'un élément qui n'est pas dans l'ensemble, chacune des m positions possède la probabilité ci-dessus de valoir 1. Si l'on suppose (et cette supposition est fausse) que ces événements sont indépendants, la probabilité que tous les k vaillent 1 (déclenchant un faux-positif) découle des calculs précédents :
La formule ci-dessus suppose que la probabilité que chaque bit vaille 1 est indépendante des autres bits, ce qui est faux, et peut mener à des résultats significativement différents quand est élevé[3]. Au contraire, quand le rapport est faible, le taux d'erreur tend effectivement vers la valeur ci-dessus.
La formule exacte est plus complexe, et vaut :
Cette valeur peut être calculée récursivement. Cependant, il est simple d'utiliser l'encadrement suivant, donné par Bose et al. [4] :
Un filtre de Bloom permet d'éviter des appels inutiles à une très grande base de données en vérifiant tout de suite l'absence d'une ligne recherchée. Le filtre n'étant pas parfait, la recherche inutile aura toutefois lieu dans certains cas, mais une grande partie sera néanmoins évitée, multipliant ainsi le nombre de requêtes utiles possibles à matériel donné. Cette méthode est utilisée par Google dans leur base de données distribuées, BigTable[5].
Les filtres de Bloom sont utilisés en bio-informatique pour la recherche rapide de motifs dans des larges jeux de données génomiques[6].
Ce type de filtre est également utilisé pour réaliser de l'inspection de paquets en profondeur[7][Quoi ?], en vertu des raisons citées plus haut. Leur implémentation au niveau matériel a permis de réaliser de l'inspection de paquets en profondeur à la vitesse du réseau.
Elle permet aussi d'optimiser les flux entre pairs[Quoi ?] dans un réseau informatiques pair à pair (comme Gnutella, BitTorrent, Freenet, le réseau Tor, les nœuds Bitcoin, et bien d'autres)[8].
Cela permet de réduire le nombre de recherches à transmettre à un sous-ensemble suffisant de pairs voisins pour trouver par quels chemins un objet identifiable est accessible, sans avoir à les interroger tous simultanément avant d'établir de nouveaux chemins supplémentaires vers d'autres pairs, si aucun de ceux interrogés ne donnent de réponse en un temps raisonnable. En effet, la surconsommation sur le réseau global par les diverses recherches identiques effectuées en parallèle par les pairs déjà atteints, s'ils ne possèdent pas directement eux-mêmes une copie de l'objet demandé croit rapidement de façon exponentielle avec la longueur maximale des chemins de recherche (en fonction du degré moyen d'interconnexion de chacun des pairs et de la profondeur atteinte, même si chacun des nœuds traversés dispose d'un cache local lui évitant de répéter en aval la même recherche provenant de plusieurs pairs en amont).
La même problématique survient sur des topologies de réseau pair à pair pour les systèmes de réplication et d'annonce, notamment au sein des protocoles d'annonce de routage entre réseaux IP (avec des pairs, les routeurs, fortement hétérogènes selon leurs capacité de traitement ou de mise en cache, leur degré local d'interconnexion et les débits utilisables sur chacune de leurs liaison d'interconnexion), ou encore pour la réplication et la mise en cache des requêtes de résolution DNS (et la vérification de leur authenticité). Sur Internet, il existe généralement un noyau relativement stable d'interconnexions au sein du réseau, entre des nœuds à forte capacité de traitement et de mise en cache local (disposant entre eux de liaisons très rapides et avec un degré d'interconnexion plus élevé que le reste du réseau), mais cette optimisation avec des filtres de Bloom évite là encore la saturation de ces nœuds fortement sollicités et de leurs liaisons, qui malgré tout peuvent connaitre des variations, du fait de pannes intermittentes sur les nœuds ou leurs liaisons, ou des besoins réguliers de maintenance locale de ces systèmes.
Ce filtre est utilisé dans les moteurs de rendu HTML pour augmenter les performances des sélecteurs CSS[9].
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.