Vous disposez d'un milliard d'URL collectées et vous souhaitez savoir si une nouvelle URL a déjà été rencontrée. Les stocker toutes dans un tableau de hachage prendrait des dizaines de Go. Un filtre de Bloom permet d'y parvenir avec seulement quelques centaines de Mo.
Fonctionnement
Un bloc de bits, initialement composé uniquement de zéros, ainsi que k fonctions de hachage différentes.
- Ajouter un élément : le hacher à l'aide des k fonctions, et mettre à 1 la k-ième position correspondante
- Vérification : après le hachage, examinez les k positions. Si l'une d'entre elles est égale à 0, l'élément n'a certainement jamais été ajouté. Si les k positions sont toutes égales à 1, il est possible que
Le deuxième cas est celui où il peut y avoir une erreur : ces bits ont peut-être été activés par d'autres éléments. C'est ce qu'on appelle un faux positif.
La caractéristique la plus importante
Il n'y a jamais de faux négatifs. Si le filtre de Bloom indique « non », c'est une réponse certaine. C'est ce qui détermine son utilisation : il permet d'éviter une grande partie des recherches inutiles en effectuant au préalable une recherche coûteuse.
Exemples d'utilisation
- La base de données vérifie si la clé se trouve dans le fichier sur le disque avant de lire réellement le disque
- Le cache distribué évite les appels réseau pour des clés qui n’existent certainement pas
- Le robot d'indexation filtre les URL déjà rencontrées
Ce qu'il faut accepter
Impossible de supprimer un élément — la désactivation d'un bit peut perturber le fonctionnement d'un autre élément partageant ce même bit. Il faut également estimer le nombre d'éléments à l'avance : si l'on en ajoute trop, le taux de faux positifs grimpe en flèche, au point que presque toutes les réponses deviennent « peut-être » et que la structure perd toute utilité.
Thảo luận