Yahoo Actualités CHRONIQUE. Un algorithme magique
La mathématicienne Claire Mathieu évoque un "algorithme un peu magique proposé en 2005".
Cet article est extrait du mensuel Sciences et Avenir - La Recherche n°915, daté mai 2023.
Comment surveiller les passages de paquets dans un réseau et détecter des distributions suspectes ? Il existe une méthode simple et efficace pour mémoriser les éléments qui surviennent fréquemment dans une suite d'éléments. Il s'agit d'un algorithme un peu magique proposé en 2005. Il a l'avantage de n'utiliser que peu de mémoire.
Un algorithme largement utilisé pour les flux massifs de données
Dans une suite de N éléments, on cherche à repérer un élément présent plus de N /2 fois. Il suffit alors de mémoriser deux compteurs pour deux éléments e et f, qu'on met à jour à mesure qu'on voit la suite défiler : si l'élément suivant de la suite est e, on ajoute 1 au compteur de e ; si c'est f, on ajoute 1 au compteur de f ; si c'est un autre élément, g, on regarde lequel de e et f a le plus petit compteur, par exemple f, et on remplace f par g et on ajoute 1 au compteur de g (qui était précédemment le compteur de f ). Si la suite contient un élément présent plus de N /2 fois, alors cet élément est garanti d'être un des deux éléments mémorisés à la fin !
Lire aussiAlgorithmes : qui était Ada Lovelace, à l'origine du tout premier programme informatique ?
Par exemple, prenons la suite abbccaaadeaacaa (N = 15), où a est présent 8 fois (donc plus de N /2 fois). À la fin du processus, on aura mémorisé les éléments c (compteur 6) et a (compteur 9) : l'élément a fait bien partie des deux éléments mémorisés. De même, si on mémorisait 3 éléments au lieu de 2 avec cette méthode, on serait sûr d'avoir tout élément présent plus de N /3 fois dans la suite. Cet algorithme baptisé SpaceSaving est aujourd'hui largement utilisé pour les flux massifs de données.
Par Claire Mathieu, directrice de recherche au CNRS, Institut de recherche en informatique fondamentale (CNRS/université Paris Cité).
Retrouvez cet article sur sciencesetavenir.fr
