Second épisode consacré à la compression de l'information et publié le 12 octobre 2012 sur le site Alliance Géostratégique
http://alliancegeostrategique.org/

Compresser pour Régner – Acte II/III

« tournez tournez bons chevaux de bois,

tournez cent tours tournez mille tours,
tournez souvent et tournez toujours,
tournez tournez au son des hautbois. »
Chevaux de bois, « Bruxelles », Romances sans paroles, Paul Verlaine.

Compressons Verlaine !

Compresser une information consiste à la transformer afin de lui donner une forme plus courte.
Ceci implique immédiatement deux types de méthodes de natures très différentes:

La compression sans perte qui va conserver l'intégralité de l'information tout en lui donnant une forme plus courte.

La compression avec perte, qui va volontairement dégrader l'information initiale afin d'en donner une forme réduite.

Observons un exemple simple de compression sans perte en partant de l'extrait du poème de Verlaine figurant en préambule :

Ce texte contient 23 mots, occupant une position numérotée de 1 à 23 et 125 lettres hors ponctuation.
Je peux réécrire l'extrait en précisant la position de chaque mot dans la phrase :
« tournez 1, 2, 7,10,13,16,18,19 bons chevaux de bois,
cent 8 tours 9,12 mille 11 souvent et toujours, au son des hautbois. »
celle-ci contient maintenant 91 lettres, soit un gain de 34 lettres par rapport au message initial.
Je n'ai perdu aucune quantité d'information puisque lorsque je décompresse cette phrase, je retrouve intégralement le texte d'origine !
On peut faire mieux via un nouvel algorithme de compression appliqué à ma précédente compression puis réitèrer le procédé jusqu'à une forme compactée de l'information non dégradée par rapport au texte initial.

La compression sans perte

Sans entrer dans le détail technique, il faut évoquer les algorithmes classiques de compression sans perte utilisés notamment pour coder les images :

Le codage de Huffman qui repose sur un codage statistique d'un fichier, octet par octet, sachant que plus les octets apparaissent souvent dans le mot initial et plus les codes qui les remplacent doivent être courts.

L'algorithme parcourt les données d'un fichier octet par octet ainsi que le nombre de fois où cet octet apparaît, il construit ensuite un arbre (graphe) en débutant par les feuilles jusqu'aux racines ;
les octets sont alors classés par ordre décroissant de fréquence d'apparition.
Cette technique est utilisée en partie dans les formats MP3 pour le son, et PNG.

Le RLE (Run-Lenght encoding) qui parcourt les données et recherche les octets identiques qui se suivent, l'algorithme trouve un octet répété successivement n fois, il crée une paire de données composée du nombre de répétitions n suivi de l'octet à répéter.

Ainsi, « A, A, A, la queue leu leu » se code par « 3A 1la 1queue 2leu »
cet algorithme est d'autant plus efficace que le mot initial à coder contient de nombreuses répétitions, ce n'est pas toujours le cas, mais pour des fichiers images, il est fréquent et fortement probable de trouver des pixels contigus identiques.Cette technique est utilisée dans le format PCX et BMP.

La classe des algorithmes Lempel Ziv : LZ77, LZ78, LZW
Il s'agit d'une famille de méthodes utilisant un dictionnaire et où les codes utilisent les indices des séquences d'octets placées dans le dictionnaire.
Ceci donne les formats d'images PNG , ZIP et GIF.

la compression avec perte

Arrêtons-nous maintenant sur quelques techniques classiques de compression avec perte :
On rappelle que l'information initiale y est volontairement et définitivement dégradée.

La transformée en cosinus discrète DCT

C'est une variante de la transformée de Fourier discrète qui est utilisée dans les formats MP3, JPEG, MPEG. Grosso-modo, cet algorithme transforme les pixels de l'image ou les séquences audio en fréquences puis élimine les fréquences qui ne sont pas pertinentes pour l'oeil ou l'oreille humaine.

Le DWT pour Discrete Wavelet Transform

Elle utilise une transformation classique de théorie du signal par ondelettes; celles-ci sont quantifiées pour être enfin tamisées afin de ne garder que la partie principale de l'information.
Le DWT est la base du format JPEG2000.

La compression fractale pour les images
Elle utilise la théorie du « rugueux » initiée par Benoit Mandelbrot.
Basée sur l'idée classique de similarité d'échelle, elle exploite le fait que toute image peut être vue comme un ensemble fini de transformations géométriques (rotations , translations, homothéties...) appliqué aux sous-motifs de taille variable qui composent l'image initiale.
Cette méthode exploite les propriétés géométriques de l'information initiale; elle s'applique en général assez bien aux paysages mais est particulièrement lente lors de la phase de compression (parfois 50 fois plus longue qu'un algo JPEG classique...).

 

Image initiale : 192ko

 

 

 

 

 

 

 

 

 

Image compressée par DWT , ondelettes de Haar : 15.6 ko

soit un taux de compression deux fois meilleur qu'avec jpeg mais une dégradation perceptible de l'image sur le haut...

Après ce tour d'horizon ultra rapide des algorithmes de compression usuels, il nous faut revenir à la question initiale : Tout peut-il se compresser ?
Si l'on compresse en acceptant de dégrader l'information, la réponse est immédiate et triviale :
OUI ! , tout se compresse avec perte ! Il convient simplement de se fixer un seuil d'acceptabilité de la perte d'information; c'est ce que l'on fait lorsque l'on se contente des informations fournies sur twitter.

Considérons maintenant notre question en n'autorisant que la compression sans perte :
la réponse est alors beaucoup moins évidente :
A priori, je peux imaginer un texte de longueur finie pour lequel je serai toujours en mesure de fixer un codage suffisamment astucieux pour en réduire sa représentation codée ! non ?
Et bien NON ! Ici, il ne faut pas se fier à son intuition première car elle est fausse.

Nous démontrerons ce théorème profond dans le dernier épisode consacré à la compression.