Si vous êtes un fan de la théorie des ensembles, vous conviendrez peut-être qu'il existe deux groupes de personnes qui écrivent des programmes informatiques : ceux qui savent ce qu'est un filtre Bloom et ceux qui ne le savent pas. Comment pourriez-vous tester efficacement si quelqu’un appartient à un ensemble ou à un autre ? Eh bien, vous pouvez utiliser un filtre Bloom. [SamWho] nous présente tout cela en termes généraux que vous pouvez appliquer dans n'importe quelle situation.
Le filtre Bloom effectue un compromis en termes de vitesse. Il est sujet aux faux positifs mais pas aux faux négatifs. Autrement dit, si un algorithme de filtre Bloom vous indique que X ne fait pas partie d'un ensemble, c'est correct. Mais s’il vous le dit, vous devrez peut-être enquêter davantage pour voir si c’est vrai.
S'il ne peut pas vous dire que quelque chose est définitivement dans une extension, pourquoi s'embêter ? Habituellement, lorsque vous utilisez un filtre Bloom, vous souhaitez réduire la recherche dans une énorme quantité de données. L'exemple de l'article parle d'avoir une base de données de 20 mégaoctets de « mauvaises » URL. Vous souhaitez avertir les utilisateurs s'ils en saisissent un, mais le téléchargement de cette base de données est prohibitif. Mais un filtre Bloom pourrait être aussi petit que 1,8 mégaoctets. Cependant, il y aurait une chance sur 1 000 d’obtenir un faux positif.
Augmentez la taille de la base de données à 3,59 Mo et vous pourrez réduire les faux positifs à un sur un million. Vraisemblablement, si vous obtenez un résultat positif, vous pourriez accepter le risque qu’il soit faux, ou vous pourriez faire plus de travail pour approfondir vos recherches.
Imaginez, par exemple, un périphérique ou un programme de cache Web. De nombreuses pages Web sont chargées une fois et plus jamais. Si vous les mettez tous en cache, vous perdrez beaucoup de temps et vous ferez sortir d'autres éléments du cache. Mais si vous testez l’URL d’une page avec un filtre Bloom, vous pouvez considérablement améliorer les choses. Si l'URL peut exister dans le filtre Bloom, vous l'avez probablement déjà vue, vous souhaiterez donc peut-être la mettre en cache.
S'il indique que ce n'est pas le cas, vous pouvez l'ajouter au filtre. Ainsi, si vous y accédez à nouveau, il sera mis en cache. Bien sûr, parfois une page affichera un faux positif. Et alors? Vous mettrez simplement la page en cache la première fois, ce que vous faisiez de toute façon auparavant. Si cela ne se produit que 0,1 % du temps, vous gagnez quand même.
En termes simples, le filtre Bloom hache chaque élément à l'aide de trois algorithmes différents et définit les bits dans un tableau en fonction du résultat. Pour tester un élément, vous calculez les mêmes hachages et voyez si l'un des bits correspondants est mis à zéro. Si c'est le cas, l'élément ne peut pas être dans l'ensemble. Bien sûr, rien ne garantit que les trois bits définis signifient que l'ensemble contient l'élément. Ces trois bits peuvent être définis pour des éléments totalement différents.
Pourquoi augmenter le nombre de bits est-il utile ? L'article répond à cela et examine d'autres optimisations comme un nombre différent de fonctions de hachage et le comptage.
L'article explique très bien le filtre, mais si vous voulez un exemple plus concret en C, vous voudrez peut-être lire cet article ensuite. Ou recherchez du code dans votre langue préférée. Nous avons déjà parlé de la gestion des chaînes Python avec les filtres Bloom. Nous avons même vu une proposition visant à les ajouter au bus urbain.
