Le Nouveau Paradigme

Le Nouveau Paradigme

Commencer à penser par soi même c'est déjà faire partie de la solution


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

Publié par Le Nouveau Paradigme sur 8 Mai 2016, 18:10pm

Catégories : #Sciences

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.

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 Albert Huffman 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.

LIRE LA SUITE

 

Commenter cet article

Nous sommes sociaux !

Articles récents