La compression de données (Généralités)
Les méthodes de compression sans perte
Un exemple simple.
Étudions d’abord un exemple très simple.
Supposons que nous devions essayer de compresser la série d’octets
suivante :
0001 0100 0011 1111 0101 0101 0101 0101 0101 0101
0101 0101 1110 1111 0000 1111 1111 1111 1111 1111
1111 1111 1111 1111 1111 1111 0110 0111 0111 0000
0111 0000 1010 1111 0000 0000 0001 1111 0001 1111
0001 1111
Elle compte 21 octets. (Vous pouvez l’interpréter comme une suite de caractères ou comme les niveaux de gris d’une suite de pixels, cela n’a pas d’importance pour ce qui nous préoccupe ici).
Nous allons coder cette chaîne en utilisant les répétitions d’octets pour gagner de la place.
Commençons par écrire un octet de signalisation, pour le repérer, nous l’écrirons en gras.
0000 0010
Convenons que le premier bit indique si l’octet de donnée qui suit se répète, si c’est le cas le bit sera mis à 1 (ce n’est pas le cas ici), si ce n’est pas le cas il sera mis à 0. Les 7 bits qui suivent indiqueront le nombre de répétitions dans le premier cas ou le nombre d’octets sans répétition qui suivent (ici on a écrit 0000 0010 car on va faire suivre l’octet de signalisation par deux octets différents qui ne se répètent pas).
Notons qu’avec ces 7 bits, nous pouvons coder 127 répétitions. On voit l’économie réalisée si beaucoup d’octets sont identiques (un masque dans Photoshop…).
Notre chaîne codée commence donc par :
0000 0010 0001 0100 0011 1111
Ça commence mal ! Nous avons utilisé 3 octets pour en coder 2, mais ça va s’améliorer. Continuons. Les 4 octets qui suivent sont identiques, ce que nous indiquons par l’octet de signalisation :
1000 0100
Le premier bit à 1 annonce une répétition, la valeur 0000100 (4 en binaire) indique le nombre de répétitions.
Nous pouvons compléter notre chaîne codée :
0000 0010 0001 0100 0011 1111 1000 0100 0101 0101
Vous vérifierez qu’en continuant nous obtenons la chaîne suivante qui code l’ensemble du message :
0000 0010 0001 0100 0011 1111 1000 0100 0101 0101
0000 0010 1110 1111 0000 1111 1000 0101 1111 1111
0000 0001 0110 0111 1000 0010 0111 0000 0000 0010
1010 1111 0000 0000 1000 0011 0001 1111
Cette chaîne fait 19 octets soit 2 de moins que la chaîne initiale, nous avons un taux de compression de 21/19 = 1,1
Le décodage ne pose aucun problème à condition que le décodeur soit informé de la méthode utilisée, il interprètera dans ce cas le premier octet comme un octet de signalisation et tout ira bien…
Cette méthode est séduisante parce qu’elle est facile à comprendre mais elle est malheureusement peu efficace. Elle n’est plus utilisée seule mais seulement comme méthode complémentaire.
Les méthodes statistiques.
L’idée est la suivante : nous avons l’habitude de coder toutes les valeurs que nous avons à stocker avec le même nombre de bits, généralement un ou plusieurs octets. Nous utilisons un octet par caractère quand nous travaillons avec du texte, un ou deux octets par pixel et par couche quand nous travaillons avec des images. Est-ce la meilleure solution ? La théorie nous apprend que non.
Il est en effet plus efficace d’utiliser des codes plus courts pour des valeurs fréquentes et de réserver des codes plus longs pour les valeurs moins fréquentes. L’intérêt de cette méthode dépendra bien entendu de la distribution des valeurs à coder telle qu’on peut l’étudier en construisant l’histogramme des valeurs à coder. Pour une image, Photoshop sait faire ça très bien comme vous le savez.
En fait l’examen des histogrammes de quelques images comme celles que nous utilisons journellement est assez encourageant : il y a toujours dans les images naturelles des variations de fréquence significatives.
On va donc s’intéresser aux VLC (Variable Length Code), on dit aussi au codage entropique.
Nous voyons bien l’intérêt de la méthode mais la mise en oeuvre est un peu plus délicate. Prenons un petit exemple.
Supposons que nous ayons à traiter un message qui ne contient que 4 caractères que nous nommerons A, B, C et D. et que les fréquence de ces caractères dans notre message soient les suivantes :
A : 60 %
B : 30 %
C : 5 %
D : 5 %
On peut imaginer le code suivant :
A : 0 B : 00 C : 01 D : 10
Il nous permettra assurément de gagner de la place mais si nous recevons le message suivant : 00001, comment l’interpréter ?
4 A ? 2 B ? 2 A et 1 B? 1 B et 2 A ? Ça ne marche pas ! Nous venons de découvrir le problème de la synchronisation.
Comment le résoudre ?
Utiliser des caractères séparateurs ? c’est contradictoire avec l’objectif de compression.
La solution c’est le VLC préfixé.
Un code est préfixé s’il n’est le début d’aucun autre. Le VLC que nous avions tenté d’utiliser tout à l’heure n’était pas préfixé.
Revenons à notre exemple et essayons de corriger.
A : 0 B : 10 C : 110 D : 111 Ça marche ! Est-ce la solution optimale ? Comme nous l’avons optenue par tatonnement, on n’en sait rien mais rassurez-vous la théorie permet d’affirmer que oui.
Nous allons maintenant prendre un exemple un peu plus complexe et présenter une méthode permettant de déterminer un VLC efficace (même s’il n’est pas toujours optimal).
Supposons que nous voulions transmettre le message suivant :
LE PRESIDENT EST ENTRE DANS LA SALLE
Il compte 36 caractères et occupe dans un logiciel comme XPress ou WordPerfect 36 octets.
Nous allons compter les occurences des différents caractères de l’alphabet utilisés et les classer par fréquences décroissantes, nous obtenons la liste suivante :
E : 7
Espace : 6
L : 4
S : 4
N : 3
T : 3
A : 3
R : 2
D : 2
P : 1
I : 1
Nous allons maintenant regrouper les caractères en deux groupes dont les fréquences d’apparition sont aussi proches que possibles puis diviser chacun de ces groupes de la même façon jusqu’à parvenir à chacune des fréquences de départ (il est équivalent de travailler avec le nombre d’occurences ou les fréquences). Voici le développement du calcul sous forme de schéma :
|
|
On numérote les branches de l’arborescence en binaire et on parcourt chaque branche pour déterminer les codes qui figurent dans la colonne de droite.
On peut vérifier que l’on obtient bien un VLC préfixé.
Mesurons son efficacité.
Nous sommes parti d’un message de 36 caractères soit 36 x 8 = 288 bits
si l’on avait codé chaque caractère sur 4 bits (c’était suffisant), on utilisait 144 bits.
En utilisant le codage que nous venons de réaliser nous utiliserons :
(2 x 7) + (3 x 6) + (3 x 4)+ (3 x 4) + (4 x 3) + (4 x 3) +(4 x 3) + (4 x 2) + (4 x 2) + (5 x 1) + (5 x 1) = 14 + 18 +12 + 12 + 12 + 12 + 12 + 8 + 8 + 5 + 5 = 118 bits
Le taux de compression par rapport à la représentation sur 4 bits est s = 144/118 = 1,22.
L’algorithme que nous venons d’utiliser pour déterminer un VLC préfixé est appelé du nom de ses auteurs, l’algorithme de Shanon-Fano.
On lui préfère souvent un algorithme voisin qui est un peu plus complexe mais qui parvient au même résultat, celui de Huffman.
Ces méthodes sont utilisées directement dans les photocopieurs et elles interviennent en PAO comme méthode complémentaires. Il y a par exemple un codage de Huffman dans la méthode de compression JPEG.
Les algorithmes de type dictionnaire
Les méthodes statistiques, en particulier l’algorithme de Huffman, ont été très employées jusqu’en 78. C’est alors que sont apparues les méthodes de type dictionnaire .
Nous avons commencé, tout à l’heure, à compresser en tenant compte des répétitions d’octets mais dans les images que nous manipulons ce sont souvent des séquences d’octets, des motifs qui se répètent. Pourquoi ne pas utiliser ces répétitions pour compresser les données ?
Prenons un petit exemple pour faire comprendre l’intérêt de la méthode.
Combien la langue française comporte-t-elle de mots de 10 lettres ? environ 10 000.
Combien peut-on faire de mots différents de 10 lettres aves les 26 lettres de l’alphabet ?
2610 soit 1,4.1014 ce qui fait tout de même 140 000 milliards de mots. Autrement dit, les mots de 10 lettres qui ont un sens représentent 1 quatorze milliardième de l’ensemble des mots de 10 lettres.
Il est donc très judicieux si l’on veut coder efficacement ces mots, d’en dresser une liste et de les numéroter, on dit plutôt de les indexer.
Les algorithmes LZ**
C’est en 1977 que Jacob Ziv et Abraham Lempel ont publié un article qui est à la base de tous les algorithmes à dictionnaire que nous utilisons actuellement.
En 1984, l’américain Terry Welch améliore l’algorithme précédent et dépose un brevet. C’est la naissance de l’algoritme LZW. Il est plus performant que les méthodes statistiques. IL sert de base à la norme V42bis du CCITT que nous utilisons dans nos modems.
Le principe de l’algorithme LZW, c’est d’utiliser un dictionnaire dynamique qui contient des motifs du fichier traité.
L’inconvénient des algorithmes à dictionnaire, c’est qu’il est à priori nécessaire de transmettre le dictionnaire avec les données, ce n’est pas le cas avec LZW. Le dictionnnaire est construit à la compression et reconstruit à la décompression.
Ce qui est également intéressant, c’est qu’il est inutile de lire et d’étudier le fichier avant de le compresser. La compression s’effectue au fur et à mesure de la lecture, le compresseur détectant au fur et à mesure les séquences qui se répètent.
Nous n’expliciterons pas cet algorithme mais nous retiendrons deux points :
• d’une part, il s’agit d’un algorithme sophistiqué et « pilotable ». Il est possible par exemple de remettre à zéro le dictionnaire ou de modifier sa taille.
• d’autre part, on peut combiner LZW et algorithme de codage statistique. C’est ce que font des programmes comme ARJ ou PKZIP qui utilisent LZW puis Shanon-Fano.
|
|
