Retour au cours

Leçon 30 : Filtres de Bloom (Introduction aux Structures Probabilistes)

Algorithmes : De Zéro à Héro (Un Guide pour Débutants)

30. Filtres de Bloom (Introduction aux Structures Probabilistes)

Alors que la plupart des structures de données garantissent l'exactitude, les Filtres de Bloom échangent une précision garantie contre une efficacité spatiale incroyable, en utilisant la probabilité.

Concept

Un Filtre de Bloom est une structure de données probabiliste, efficace en espace, utilisée pour tester si un élément n'est définitivement pas membre d'un ensemble, ou est potentiellement membre d'un ensemble.

Il se compose d'un grand tableau de bits et de plusieurs fonctions de hachage indépendantes.

Fonctionnement

  1. Pour ajouter un élément, exécutez-le à travers les k fonctions de hachage. Définissez les bits aux k indices résultants dans le tableau à 1.
  2. Pour vérifier si un élément existe, exécutez-le à travers les mêmes k fonctions de hachage. Si tous les k bits sont à 1, il pourrait exister. Si un bit est à 0, il ne doit définitivement pas exister.

Erreur et Cas d'Utilisation

  • L'Inconvénient (Faux Positifs) : Les filtres de Bloom peuvent générer des False Positives (indiquer qu'un élément est présent alors qu'il ne l'est pas), mais jamais de Faux Négatifs.
  • Cas d'utilisation : Empêcher les navigateurs web de visiter des URL malveillantes (en vérifiant une liste noire) ou vérifier des requêtes de base de données pour éviter des lectures de disque coûteuses si un élément est clairement manquant.