Exclusif : ce Français qui révolutionne la compression de données

Les techniques de compression de données sont partout : elles permettent de réduire la taille des fichiers musicaux et d'images mais aussi d'effectuer du calcul à haute performance. Le Français Olivier Thomine, un jeune numéricien, vient d'élaborer un nouvel algorithme de compression prometteur qui devrait impacter tous ces domaines. Rencontre.

Le 23/03/2016 à 17:30 - Laurent Sacco, Futura-Sciences

Le centre de calcul du Cern, un haut lieu du HPC (High-Performance Computing), c'est-à-dire du « calcul à haute performance » avec des superordinateurs. Sans lui, la découverte du boson de Brout-Englert-Higgs aurait été impossible. © Sophia Elizabeth Bennett, Cern

Dans ses célèbres Leçons sur l’informatique, le prix Nobel de physique Richard Feynman ne fait pas qu’introduire le lecteur à la théorie des machines de Turing et à celle des ordinateurs quantiques. Il y expose aussi les bases de la théorie de l’information de Claude Shannon ainsi que celles de la théorie du codage. Ces deux dernières théories fascinantes sont liées entre elles et sont essentielles pour la conception de systèmes manipulant de l’information de façon de plus en plus efficace.

Qu’il s’agisse de faire de longs calculs sur ordinateur ou encore de transmettre et de stocker de l’information, comme des images ou du son, on a tout intérêt à minimiser la longueur des données que l’on manipule et qui contiennent cette information. Se pose alors le problème du codage.

L’un des exemples les plus anciens est peut-être celui de l’utilisation des chiffres indiens à la place des chiffres romains. Ils ont permis d’effectuer des calculs de façon plus efficace. Un autre exemple, plus récent, est la mise au point du code Morse en 1838 : l'une des idées de base était de coder les caractères les plus fréquents dans des messages avec le moins de signaux possible, sous forme d’assemblages de points et de tirets. Inversement, on utilise les assemblages les plus longs pour les caractères qui reviennent le plus rarement. Ainsi, le « e », qui apparaît fréquemment est codé par un simple point alors que le « x » est codé avec quatre symboles. Cela permet donc de compresser la longueur des messages.

Claude Shannon (1916-2001) est un ingénieur en génie électrique et mathématicien américain. Il est l'un des pères fondateurs de la théorie de l'information qu’il développa largement du fait de ses travaux en cryptographie pendant la seconde guerre mondiale. Il était chargé de localiser de manière automatique dans le code ennemi les parties signifiantes cachées au milieu du brouillage. Il rencontra à ce moment Alan Turing, qui travaillait lui aussi sur la cryptographie. Ses découvertes furent exposées durant la période d'après-guerre dans un célèbre article, A Mathematical Theory of Communications (1948). On doit à Shannon la mise en évidence d’un lien très profond entre la notion d’entropie et celle d’information, ce qui a conduit aux méthodes dites « d'entropie maximale » utilisées notamment pour faire de la reconnaissance automatique des caractères, de l'apprentissage automatique et qui sont aussi employées dans le cadre de l’imagerie médicale. © MIT museum

La compression des données, une nécessité pour l'informatique

L’avènement des télécommunications au XXe siècle, ainsi que la montée en puissance des tâches demandées aux ordinateurs, a conduit les ingénieurs et les mathématiciens à étudier de près des techniques similaires de plus en plus élaborées pour compresser les données. On comprend facilement, par exemple, qu’au temps où les ordinateurs ne disposaient pas de beaucoup de mémoire vive ou morte, on avait tout intérêt à pouvoir écrire des programmes ou à stocker des données sous la forme la plus courte possible. Il en est de même lorsque l’on veut effectuer des calculs ou transmettre des informations. Il n’est évidemment pas question que le temps pris pour le faire dépasse plusieurs mois ou encore plusieurs années, voire des siècles.

Un des plus célèbres codes de compression de données a été découvert par David AlbertHuffman alors qu’il était en thèse au MIT (Massachusetts Institute of Technology) au début des années 1950. Le principe de ce code est simple à comprendre. Donnons-nous 100 caractères possibles qui peuvent être des lettres de l’alphabet, des chiffres, d’autres symboles comme des points-virgules, des parenthèses, etc.

Avec eux, on pourrait former 10010 expressions longues de 10 symboles. Cependant, en réalité, on utilise en général un nombre bien moins important de combinaisons pour coder un texte ou un programme (tghyul !@_} ne correspond à rien, par exemple). L’idée de Huffman est que, pour tout texte source donné, il faut d’abord analyser les fréquences d’apparition des mots ou des assemblages de caractères. On peut ensuite associer à ces assemblages des nombres en binaire qui sont d’autant moins longs qu'ils sont les plus fréquents.

Il est possible d'effectuer ainsi une compression sans pertes de fichiers contenant des textes ou des programmes. Pour des images et des sons, on peut utiliser d’autres algorithmes qui, au prix d’une certaine perte d’information acceptable pour un œil ou une oreille, permettent de compresser l’information.

Ingénieur, David Albert Huffman (1925 - 1999) fut un pionnier de la compression de données dans le domaine de l'informatique. On lui doit le codage de Huffman, utilisé par exemple avec des fichiers en MP3 et en JPeg. © Don Harris

De nos jours, on peut compresser de 50 % des fichiers textes, de 80 % des images fixes et de 95 % des films selon la qualité voulue. Le MP3 et le JPeg sont utilisés pour la compression avec perte, respectivement, des fichiers musicaux et d’images. Il n’est pas exagéré de dire que les techniques de compression des données sont désormais omniprésentes et vitales, aussi bien dans la vie quotidienne, avec les DVD, nos téléphones et ordinateurs portables, que pour l’imagerie en médecine et en astronomie (elles rendent par exemple possible l’obtention des images de la surface de Pluton ou la recherche de nouvelles particules dans les détecteurs du LHC).

Une technique de compression pour le calcul à haute performance

Toute nouvelle méthode de compression des données qui serait plus efficace que les autres, au moins dans certains cas, est donc importante, aussi bien pour la recherche fondamentale que pour l'industrie.

Olivier Thomine, un jeune numéricien, a justement trouvé un nouvel algorithme prometteur de compression alors qu'il était en postdoc au CEA (Commissariat à l'énergie atomique et aux énergies alternatives). Il a notamment travaillé sur la simulation numérique des plasmas tels ceux que l'on rencontrera dans le réacteur d'Iter. Les membres de Futura-Sciences le connaissent bien puisqu'il est un des modérateurs actifs du forum. Nous avons donc demandé à Olivier Thomine de nous expliquer l'enjeu de sa découverte.

Olivier Thomine sur son lieu de travail en 2016. © Olivier Thomine, tous droits réservés

Futura-Sciences : Il existe deux types d’algorithmes de compression : ceux avec perte et ceux sans perte. À quelle famille votre nouvel algorithme appartient-il ?

Olivier Thomine : Cela peut paraître surprenant, puisqu’il s’applique notamment aux sons, aux photos et à la vidéo, mais il s’agit d’un algorithme qui permet de faire de la compression sans perte. En fait, ce n’est pas le premier capable d’une telle performance. Il existe par exemple depuis 1984 l’algorithme LZW, pour Lempel-Ziv-Welch, qui, bien qu’étant un algorithme de compression de données sans perte est utilisé pour les fichiers d’images Gif et Tiff ainsi que les fichiers audio enMOD pour la musique.

Futura-Sciences : Peut-on se faire une idée de l’efficacité de ce nouvel algorithme ?

Olivier Thomine : Oui, il permet de compresser les données environ 10.000 fois plus rapidement que le LZW et, pour des tests que j’ai effectués avec des fichiers de données concernant des capteurs de rayonnement mais aussi des capteurs cardiaques, il est quatre fois plus rapide que les méthodes usuelles.

Une comparaison entre les performances des techniques de compression utilisables pour faire du HPC (High-Performance Computing), c'est-à-dire le « calcul à haute performance » avec des superordinateurs. Au centre, les méthodes standard et, à droite, la nouvelle méthode. © Oliver Thomine

Futura-Sciences : Dans quels domaines est-il susceptible de faire la différence avec les autres méthodes de compression ?

Olivier Thomine : Il est probable que presque tous les domaines scientifiques vont être impactés, du médical au nucléaire en passant par les transmissions satellitaires et avec des sondes spatiales. Mais le domaine où l’algorithme devrait vraiment être très utile, c’est celui du HPC (High-Performance Computing) ou, en français, le « calcul à haute performance » avec des superordinateurs. La raison en est simple, c’est justement parce que j’essayais d’améliorer la vitesse de calcul de simulations numériques impliquées dans la physique des plasmas dans le cadre du projet Tore-Supra, lors de mon postdoc à Cadarache, que j’ai élaboré ce nouvel algorithme de compression.

Le HPC est vraiment partout de nos jours et il est devenu un outil essentiel de la recherche scientifique, technologique et industrielle. Il intervient par exemple lorsque l’on veut modéliser des crashs d’avions ou de voitures, des molécules biologiques d’intérêt pharmaceutique, le climat ou encore la formation et l’évolution des galaxies et des étoiles. Il s’agit à chaque fois de pouvoir exécuter plusieurs milliards d’opérations à la seconde pour modéliser des phénomènes complexes ainsi que pour traiter ou qualifier rapidement de gros volumes de données comme celles obtenues dans les détecteurs du LHC lors des collisions de faisceaux de protons.

Pour vous donner un exemple précis, il y a actuellement un laboratoire en partenariat avec le CEA qui fait des tests de toxicité avec des capteurs sur des matrices de cellules cardiaques. Il y a tellement de données qu’on n'arrive plus à les transférer efficacement à des clusters de calculateurs afin de les éplucher. Avec le nouvel algorithme, ils pourront le faire.

Futura-Sciences : Quelle est l'idée centrale derrière votre nouvel algorithme ?

Olivier Thomine : Déjà, il faut comprendre que je l’ai mis au point alors que j’étais confronté à un problème précis. Lorsqu’un ordinateur effectue des simulations numériques, une partie du temps nécessaire n’est pas consacré à l’exécution de l’algorithme lui-même derrière les calculs de la simulation mais provient du temps de transfert des données entre les composantes où celui-ci est exécuté. Pour le minimiser, on compresse donc les données à envoyer. C’est à ce niveau-là qu’une réduction du temps d’exécution du programme a été obtenue en améliorant le processus de compression des données utilisé. La méthode peut donc intervenir dans un grand nombre de domaines.

Schéma de la technique de compression de données pour les transférer entre les éléments d'un superordinateur lors des calculs (cliquez sur l'image pour l'agrandir). © Olivier Thomine

Pour compresser les données avant de les envoyer aux composants effectuant les calculs, on anticipe les données qui vont venir à partir de celles que l'on a déjà transmises, on trouve les erreurs dans le signal anticipé et on n'envoie uniquement les erreurs. C'est bien là la différence majeure : avant, il fallait envoyer ou stocker la compression avec perte en plus des erreurs. Pour s'en passer, on reboucle au niveau du décompresseur la sortie vers un registre à décalage qui tente de prédire les données suivantes de la même manière que le compresseur, comme l'illustre le schéma ci-dessus (cliquez dessus pour l'agrandir).