Avec l’explosion des données (un fichier de logs, par exemple), chercher une information particulière déjà connue devient une tâche complexe. Or depuis 1970, il existe une technique particulièrement puissante qui permet de résoudre très efficacement ce problème : les filtres de Bloom. Cet article propose de les explorer et de montrer comment les implémenter.
Dans de nombreux problèmes informatiques, il est nécessaire de déterminer si un ou plusieurs éléments figurent dans un ensemble de données de référence, et ce, de manière rapide (en particulier, en minimisant les accès disques, ce qui devient difficile dans la pratique si l’ensemble de référence est grand). Dans bien des cas, l’usage classique des tables de hachage ne permet pas un tel traitement, en particulier dans des environnements contraints comme celui du calcul embarqué. Dans cet article, nous allons présenter une structure probabiliste, les filtres de Bloom, permettant de traiter efficacement ce type de problème. L’idée maîtresse est d’introduire une dose acceptable d’erreurs pour augmenter les performances, tout en gérant les contraintes (temps et mémoire), mais sans dégrader la solution/décision finale. Après la présentation d’une implémentation classique, nous verrons une implémentation optimisée, développée par l’auteur,...
- Accédez à tous les contenus de Connect en illimité
- Découvrez des listes de lecture et des contenus Premium
- Consultez les nouveaux articles en avant-première