La compression de données

1)      introduction

Vous regardez des films, à partir de votre lecteur DVD, de votre ordinateur ?

Un DVD a un format de 720x576 pixels, donc chaque image est constituée de 720x576= 414720 pixels.

Comme il faut 3 valeurs pour stocker un pixel (une par couleur primaire) et en prenant par exemple 3 octet pour chaque valeur (de cette taille dépend le nombre de couleurs que l'ont peut stocker, 3 octets = 16,6 millions de couleurs), 414720x3x3 = 3 732 480 octets sont nécessaire pour un seule image.

Un film en PAL nécessite 25 images pour une seule seconde, soit 3 732 480 * 25 = 93 313 000 octets, soit un peu plus de 88 Méga-Octets par seconde. Sans compression un film d'une heure trente nécessiterait plus de 475 Go. Colossal, sans parler du matériel nécessaire pour traiter et transférer cette masse de données.

Afin d'optimiser l'espace mais aussi la bande passante sur les réseaux, la compression de données est indispensable !

Deux grandes familles existent : avec pertes et sans pertes. Ici seule la première catégories sera abordée, en particulier les codeurs appelés « codeurs d'entropie ». Ce type de codage est utilisé dans un grand nombre de systèmes de compression. ZIP, TAR, mais aussi en dernière phase des algorithmes de compression « destructeurs » comme le JPG.

2)      un peu de théorie

En informatique toutes les données sont stockées sous forme de bits, c'est à dire de 0 et de 1. Ainsi il nous est possible de les représenter sous la forme de chaînes de caractères, en prenant un octet (une suite de 8 bits) égal un caractère, nous avons 256 caractères possibles. Pour des raisons didactiques évidentes nous représenterons les données sous forme de chaînes de caractères, mais le principe reste valable pour tout type de donnée.

Un outil de compression est constitué de deux fonctions. Une fonction « c » de codage et une « d » de décodage. Bien entendu pour une chaine « Oméga »    d(c(Oméga))= Oméga, c'est à dire que la fonction de décodage appliquée à un texte codé fournira le texte original, sans aucune modification.

Pour des raisons théoriques qui seront omises ici, un compresseur pourra compresser uniquement 0,4 % des chaînes de caractères. Relativement peu. Comment dans ce cas alléger nos chers fichiers ?

Afin d'optimiser la compression, nous ne chercherons pas à compresser toutes les chaînes, mais uniquement certaines, celles qui se répètent et celles qui sont statistiquement plus fréquentes. Ainsi un texte purement aléatoire sera presque impossible à compresser.

3)      la compression statistique

Ici le but est de repérer les lettres qui reviennent souvent. Pour la démonstration nous utiliserons uniquement 32 caractères, codé sur 5 bits, ce qui reste valable pour un nombre plus important.

Ainsi prenons l'alphabet : 

_	00000		h	01000		p	10000		x	11000
a	00001		i	01001		q	10001		y	11001
b	00010		j	01010		r	10010		z	11010
c	00011		k	01011		s	10011		.	11011
d	00100		l	01100		t	10100		,	11100
e	00101		m	01101		u	10101		'	11101
f	00110		n	01110		v	10110		!	11110
g	00111		o	01111		w	10111		?	11111

Imaginons que nous avons le texte suivant à compresser : «mais sissi, cette saucisse ci sait secher sans s'assecher, non ? » soit 64 caractères (le caractère « espace » est codé par « _ »).

Ce texte occupe donc 64*5 = 320 bits.

Dans cet exemple, nous n'utilisons pas tous les caractères disponibles mais seulement 16. Nous pouvons résumer leur fréquence d'apparition dans le tableau suivant.

?	1	e	7
m	1	t	3
a	5	u	1
i	6	h	2
s	14	r	2
_	10	n	3
c	5	'	1
,	2	o	1

Une première solution pourrait être de changer le codage, en effet pour coder les 16 caractères utilisés nous pourrions utiliser un codage sur 4 bits par exemple le codage suivant :

?	0000	e	1000
m	0001	t	1001
a	0010	u	1010
i	0011	h	1011
s	0100	r	1100
_	0101	n	1101
c	0110	'	1110
,	0111	o	1111

Déjà, en utilisant ce codage, nous avons 64*4= 256 bits, soit un gain de 20 %.

Il est encore possible d'optimiser ce code. Remarquons que certains caractères apparaissent bien plus souvent que d'autres. Ainsi le « s » qui apparaît 14 fois pourrait être codé avec un nombre de bits moins élevé que le « m » qui n'a qu'un seule occurrence.

Par exemple les lettres de l'exemple ci-dessus pourraient être :

s	0	,	110
_	1	h	111
e	00	r	1000
i	01	?	1001
c	10	m	1010
a	11	'	1011
t	100	o	1100
n	101	u	1101

Ainsi le texte «  mais sisi, cette » précédent peut être codé par : 1010 11 01 0 110 1 10 00 100 100.

Donc l'intégralité du texte occupe maintenant : 14*1+10*1+7*2+6*2+5*2+5*2+3*3+3*3+2*3+2*3+2*4+3*4+4+4+4+4=  136 bits.

A comparer aux 320 bits sans compression, soit un gain de près de 60%.  Seulement le codage utilisé ci-dessus n'est pas utilisable ! Dommage.

Pourquoi ? Tout simplement parce que les bits sont écrits les uns à la suite des autres donc  1010 11 01 0 110 1 10 00 100 100 sera  10101101011011000100100. Par exemple la séquence 1010 peut être :

-         1 0 1 0 soit « _s_s »

-         10 10 soit « cc »

-         1010 soit « m »

on ne peut donc pas retrouver sans perte le texte initial. Ce codage ne convient donc pas !

4)      Codages préfixes

Afin de décoder correctement il est impératif de respecter la règle suivante : Aucun code ne doit commencer comme un autre code.

Pour décoder le message, il suffit de le lire bit à bit, lorsqu'on rencontre un code qui correspond à un caractère, on le décode et on reprend la lecture.

5)      un petit exemple

Reprenons notre texte : «mais sissi, cette saucisse ci sait secher sans s'assecher, non ? »

En utilisant le codage suivant

s	00	,	11100
_	010	h	111010
e	011	?	111100
a	100	r	111011
c	1010	m	111101
i	1011	u	111110
t	1101	'	1111110
n	1100	o	1111111

Nous pouvons observer qu'aucun code n'est le début d'un autre, ainsi en lisant bit a bit, nous pouvons décoder.

Notre texte ainsi codé devient  : 11110110010110001000101100001011 ...etc.

si nous le lisons:

-         premier chiffre : 1 il ne correspond à rien donc on continue

-         deuxième : 11 , ne correspond à rien on continue

-         troisième : 111, ne correspond à rien on continue

-         quatrième : 1111, ne correspond à rien on continue

-         cinquième : 11110, ne correspond à rien on continue

-         Sixième : 111101, ah on a un code qui correspond à la lettre « m », donc on décode et on continue.

Il reste à décoder  (111101 est remplacé par m)    10010110001000101100001011 ...etc.

nous lisons:

-         premier chiffre : 1 il ne correspond à rien donc on continue

-         deuxième : 10, on continue

-         troisième : 100 , on a la lettre « a », on décode et on continue.

Il reste 10110001000101100001011 ...etc.

-         premier chiffre : 1

-         deuxième : 10, on continue

-         troisième 101, on continue

-         quatrième 1011, ah on a la lettre « i », on décode et on continue

il reste 0001000101100001011 ...etc.

et ainsi de suite,

on voit bien que ceci est fastidieux à la main, mais l'algorithme est extrêmement simple et très rapide à exécuter pour unordinateur.

En utilisant ce type de codage notre texte initial prendrait : 228 bits, soit encore mieux que précédemment.

6)      conclusion

En réalité pour un texte bien plus long, les répétitions sont plus nombreuses et plus marquées, la compression n'en est que meilleure.

Ce type de codage n'est presque jamais utilisé sine die mais, en général, des transformations du texte initial permettent d'optimiser les répétitions et la fréquence des caractères.

Comment créer un codage préfixe, me direz-vous ? Il existe deux principaux algorithmes. Celui de Huffman et celui de Shannon-Fano. Les détailler exigerait un article complet (qui sait si la demande m'en était faite ? ).

Vous trouverez plus de précisions ici: http://fr.wikipedia.org/wiki/Codage_de_Huffman

A vos commentaires !