Compression (assez difficile)
Vous souhaitez communiquer un message manuscrit à un correspondant. Vous le prenez en photo avec votre Smartphone et vous obtenez un fichier. Celui-ci est composé d'octets, eux mêmes composés de 0 et de 1 qu'on appelle "bit". Le nombre de bits est la taille du fichier.
Mais le canal que vous allez utiliser pour véhiculer cette information a une capacité limitée. Et le fichier initial ne passera pas : il est trop gros. Que faire ?
Une solution consiste à compresser votre fichier. Il existe des outils pour cela, par exemple le programme "7-zip" : https://www.7-zip.fr/
Avec un peu de chance, le fichier compressé sera alors assez petit pour être envoyé.
Il faudra toutefois que votre correspondant dispose aussi de 7-zip, qui permet de décompresser les fichiers qu'il a initialement compressé.
Quotidiennement,
et sans le savoir, vous bénéficiez de tels algorithmes qui compressent
votre voix sur un téléphone, la musique que vous écoutez, des images que
vous visionnez...
La compression de données est partout et a optimisé bien des communications. Ainsi, les sondes spatiales Voyager envoyaient initialement vers la Terre leurs images sans compression, et avec un débit très faible. L'utilisation d'algorithmes de compression a permis d'augmenter ce débit et d'échanger plus de données tout en consommant moins d'énergie.
Mais revenons à notre exemple et supposons que votre correspondant n'ait pas 7-zip. Ou que le fichier compressé soit encore trop gros. Votre problème n'est pas résolu.
7-zip est un programme universel qui réduit tout fichier en un fichier plus petit. Mais le plus souvent, le fichier résultat n'est pas le plus petit possible. Vous pouvez espérer faire mieux.
Imaginons alors des programmes plus spécifiques, qui soient entièrement dédiés à votre fichier à compresser. Contrairement à un programme universel qui a besoin d'un fichier externe pour fonctionner, ces programmes spécifiques, une fois lancés, fourniraient directement le fichier initial.
Plus besoin de 7-zip donc pour votre correspondant : lancer le programme restitue le fichier. Un problème résolu.
Parmi tous ces programmes dédiés, retenons le plus petit en taille, bien entendu.
La taille de ce plus petit programme est ce qu'on appelle la complexité de Kolmogorov de l'information. Autrement dit, c'est la taille de l'information.
C'est assez logique : impossible d'envoyer quelque chose de plus petit sans perdre de l'information !
Certains résultats théoriques indiquent que, dans le cas général, on ne peut pas trouver de programme minimal. Mais laissons cela de côté pour le moment, Il nous suffit de savoir qu'il existe.
D'autres résultats indiquent que, quel que soit le langage de programmation considéré, la taille du plus petit programme est relativement constante et cela donne du sens à la définition, bien évidemment.
Revenons maintenant à notre exemple de feuille manuscrite numérisée sous forme de fichier.
Supposons que vous soyez capable de trouver ce plus petit programme compresseur dédié possible. Ce programme est lui aussi un fichier fichier binaire (composé de 0 et de 1).
Et vous vous apercevez alors que le programme est tout juste encore un peu trop gros. Avec un bit de moins, vous pourriez l'envoyer pourtant... Mince !
Vous décidez de retirer le dernier bit du fichier et vous envoyez le programme ainsi réduit.
Votre correspondant va tenter de lancer le programme.
Il verra alors qu'il ne fonctionne pas ou qu'il fournit quelque chose d'inintelligible.
Il verra bien également que vous avez envoyé un fichier juste assez grand pour qu'il puisse le recevoir.
Si votre correspondant est assez malin, il se doutera de votre action réductrice (enlever le dernier bit) et tentera peut-être de rajouter un bit à la fin. Avec un 0 ou un 1 en plus, il obtiendra une image intelligible et lira le message.
Finalement, il aura reconstitué l'image alors qu'il a reçu moins d'information que l'image n'en contenait.
Approfondir cet aspect nous amènerait sur les codes correcteurs d'erreur et sur le contexte d'une information. Mais ce sera une autre histoire.
Je vous laisse méditer là-dessus...
Pour ceux qui veulent aller plus loin :
https://fr.wikipedia.org/wiki/Compression_de_donn%C3%A9es
Commentaires
Enregistrer un commentaire