Les filtres de Bloom : un peu de bruit pour beaucoup [1] !

Magazine
Marque
GNU/Linux Magazine
Numéro
231
Mois de parution
novembre 2019
Domaines


Résumé

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,...

Cet article est réservé aux abonnés. Il vous reste 97% à découvrir.
à partir de 21,65€ HT/mois/lecteur pour un accès 5 lecteurs à toute la plateforme
J'en profite


Articles qui pourraient vous intéresser...

Le point sur le débogage en Python

Magazine
Marque
GNU/Linux Magazine
HS n°
Numéro
111
Mois de parution
novembre 2020
Domaines
Résumé

Il n'existe pas une unique façon de déboguer du code en Python. Dans cet article, nous allons faire un rapide tour des différentes techniques qui s'offrent à vous pour traquer les bugs.

Les bases de LaTeX sous GNU/Linux et Windows

Magazine
Marque
GNU/Linux Magazine
Numéro
242
Mois de parution
novembre 2020
Domaines
Résumé

Et si nous retournions aux sources ? Des articles sont régulièrement consacrés à LaTeX dans ce magazine, mais comment les utiliser si l'on part de zéro ? Dans cet article, je vous propose de voir ou revoir comment installer LaTeX, configurer un éditeur et gérer les extensions/paquets pour une utilisation sous GNU/Linux ou Windows. Une sorte de guide de survie pour prof de maths, en cas d'obligation d'enseignement à distance...

Débugage facile avec Sentry

Magazine
Marque
GNU/Linux Magazine
HS n°
Numéro
111
Mois de parution
novembre 2020
Domaines
Résumé

Nous le savons tous, aucun code n’est exempt de bugs. Nous avons beau écrire tous les tests unitaires du monde, tous les tests fonctionnels, avoir une couverture du code par nos tests de 200 %, il y a toujours des bugs qui passent à travers les mailles du filet. Sentry est là pour vous aider à les trouver et à les corriger grâce à vos utilisateurs, et ce, sans qu’ils ne s’en rendent compte.

Résolution azimutale d’un RADAR à bruit : analyse et réalisation d’un RADAR à synthèse d’ouverture (SAR) par radio logicielle

Magazine
Marque
GNU/Linux Magazine
Numéro
242
Mois de parution
novembre 2020
Domaines
Résumé

Nous complétons la mesure de distance des cibles RADAR par la mesure d’azimut rendue possible par la synthèse d’ouverture d’antenne, afin de localiser leur position et ainsi d’identifier précisément leur nature par superposition sur une photographie aérienne. La souplesse de la radio logicielle est illustrée par la montée en fréquence (2,4 GHz), sans modifier aucun élément matériel autre que les antennes.

Débogage JavaScript côté client

Magazine
Marque
GNU/Linux Magazine
HS n°
Numéro
111
Mois de parution
novembre 2020
Domaines
Résumé

Si JavaScript a longtemps évoqué l’idée de petit script dans un site internet, il est aujourd’hui souvent utilisé comme fondation d’application web complexe (notamment via des frameworks comme ReactJS ou VueJS). Dans ce contexte d’usage avancé, il est nécessaire d’avoir en main les bons outils et techniques de débogage.