|
 Trouver une ressource
Vous ne trouvez pas de réponse à votre problème ? Alors posez la question dans le forum. Souvenez-vous qu'il n'y a jamais de question bête, mais rester dans l'ignorance parce que l'on n'ose pas poser une question, ça c'est une erreur !
[Tous langages] Les compressions (partie 1)
 Tutorial
Les Compressions - Partie 1
Depuis quelques années, et malgré l'évolution incessante des supports informatiques, les capacités de nos HD ayant presque décuplé en 10 ans, les mathématiques du chaos se sont introduites dans nos ordinateurs pour ne garder que les octets utiles.
WinZip, WinRar, WinAce pour ne citer qu'eux, des noms que l'on a tous au moins une fois entendu.
Ce sujet est extrèmement vaste, c'est pourquoi je vais le séparer en 3 parties, correspondant aux trois méthodes de compressions principales, que je place par ordre de popularité croissante : la compression sans perte, la compression avec perte, et les compressions composites (Deflate etc.).
Je ne développerais pas non plus les formes adaptatives ou logiques des compressions, ni les formes dynamiques, ni les codages d'ordre supérieur, ce tuto s'adresse avant tout aux débutants. Peut etre dans un un prochain article ? hehe...
Vous devez qd meme etre familier avec la notion de Bit, d'Octet (ou Byte) = 8 bits. Et savoir lire et compter couremment. En français :) donc ca ne s'adresse pas aux professionnels (Je vous passe aussi l'histoire de l'entropie de Andreï Kolgomorov, qui est qd meme à la base).
Bonne lecture :)
Partie I : La compression sans pertes
Il y a, ici aussi, un nombre immense de méthodes, je ne cite que les principales, je les développe en bas, de la plus compliqués à la plus simple :
- La compression par dictionnaire (LZW par exemple)
- La compression arithmétique
- La compression de longueur (PICT, RLE)
Toutes ces méthodes sont dites asymétriques : on met plus de temps a compresser qu'à décompresser.
Le principe : on remplace un octet ou une série d'octet par un code plus court.
1. La compression par dictionnaire
Méthode : on utilise un "dictionnaire" de "mots" connus pour compresser, ces mots sont des séries d'octets. Il sont efficaces sur des séries qui se répètent.
Un exemple : LZW (du nom des inventeurs, Abraham Lempel, Jacob Ziv, Terry Welch)
PseudoCode (j'utilise & pour symboliser la concaténation, notez aussi que la syntaxe "tantque x=prochain caractère" attribue a x la valeur de chaque lettre du message):
tantque (k = prochaincaractere)
{
si (w & k) est dans le dico
w = w & k;
sinon
ajouter (w & k) au dico
sortir l'index de w dans le dico;
w = k;
}
Ce qui donne, sur la chaine WABWAAWAAA par exemple (le dico contient les 255 caractère ascii de base, c'est pourquoi on compte à partir de 256) :
w k sortie index dico
- W
W A W 256 WA
A B A 257 AB
B W B 258 BW
W A
WA A <256> 259 WAA
A W A 260 AW
W A
WA A
WAA A <259> 261 WAAA
A - A
On obtient donc, a partir du message WABWAAWAAA (10 octets) le message WAB<256>A<259>A (en considérant que les codes tiennent sur 1 octet de 9 bits, 8+8+8+9+8+9+8 = 58 bits = 7,25 octets mais les octets c'est entier, donc 8 octets)
Pour décompresser, la méthode est encore plus simple (donc plus rapide)
PseudoCode :
lire un caractère k;
afficher k;
w = k;
tantque ( k = prochain caractère/code )
{
entrée = index de k dans le dico;
affichée l'entrée;
ajouter w & entrée[0] au dictionnaire;
w = entrée;
}
Je précise que entrée[0] représente le premier caractère de la chaine entrée.
Donc si on décode ce que l'on a plus haut :
w k affichage index dico
- W W
W A A 256 WA
A B B 257 AB
B <256> WA 258 BW
<256> A A 259 WAA
A <259> WAA 260 AW
<259> A A 261 WAAA
A -
Remarquez que l'on retrouve le meme message (ca vaudrais mieux quand meme :p) mais également le meme dictionnaire...
Evidemment cette méthode a ses failles, si on a + de 256 combinaisons, et qu'on ne peut pas utiliser + de 9 bits pour un code, on peut remettre à 0 le dico et continuer, a condition que le décodeur remette à zéro son dico aussi...
La principale faiblesse de ces méthodes (LZ77, LZ78 et toute la série des LZ...) est qu'elles s'appliquent avant tout sur des données qui se répètent. Mais quand il s'agit de caractères qui se répètent, ces codes ne les compressent pas bien (essayez de compresser AAAAAAAAAAA, LZ77 vous donnerais A(-1;1)(-2;2)(-4;4)...) les données doivent etre en ligne, on compressera mieux WAWAWA que AWWAAW.
on a donc...
2. Les compressions Arithmétiques
Il existe deux principales compressions arithmétiques
L'une des plus celebre est la compression dite de Huffman (de l'inventeur David Huffman, 1952, aussi appelée compression CCITT). L'autre, est une étude des probabilités.
2.1. La compression statistique
La méthode : Prenons un texte, a tout hasard, BILL GATES...
Calculons, sur un intervalle entre 0.0 et 1.0 la probabilité que chaque lettre apparaisse :
B = 0.1
I = 0.1
L = 0.2
(espace) = 0.1
G = 0.1
A = 0.1
T = 0.1
E = 0.1
S = 0.1
On va maintenant attribuer un ensemble de probabilités croissantes aux lettres (soit p la probabilité, l'ordre des lettres n'a pas d'importance, le tout etant que le décodeur ait la meme table):
(espace) 0 <= p < 0.1
A 0.1 <= p < 0.2
B 0.2 <= p < 0.3
E 0.3 <= p < 0.4
G 0.4 <= p < 0.5
I 0.5 <= p < 0.6
L 0.6 <= p < 0.8
S 0.8 <= p < 0.9
T 0.9 <= p < 1.0
Puis on utilise l'algorithme de compression (pseudocode, attention, ce n'est pas du C, d'ailleurs il faut remplir les tableaux high_range et low_range et la variable nChars)
int nChars; (nombre de lettres, ici 9)
float low_range[nChars]; (bornes inférieures de l'ensemble pour chaque lettre)
float high_range[nChars]; (bornes supérieures de l'ensemble)
char c;
low = 0.0;
high = 1.0;
tantque (c = prochaincaractère) {
range = high - low;
high = low + range * high_range(c);
low = low + range * low_range(c);
} Ce qui donne :
On doit donc transmettre un code entre 0.2572167752 et 0.2572167756
Pour le décodage, on procède comme suit :
Le code est entre 0.2 et 0.3, donc la 1ere lettre est B. On soustrait au code la valeur de la borne inférieure de l'espace de B, puis on divise le code par l'intervalle de probabilité de B (0.3-0.2 = 0.1)... Ce qui donne :
Code Lettre Nouveau code Intervalle
0.2572167752 = B => 0.572167752 0.1
0.572167752 = I => 0.72167752 0.1
0.72167752 = L => 0.6083876 0.2
0.6083876 = L => 0.041938 0.2
0.041938 = (espace) => 0.41938 0.1
0.41938 = G => 0.1938 0.1
0.1938 = A => 0.938 0.1
0.938 = T => 0.38 0.1
0.38 = E => 0.8 0.1
0.8 = S => 0 0.1
Quand on a atteint 0, la décompression est finie. Meme si cette méthode est séduisante et peut se révéler efficace, elle possède des faiblesses évidentes : plus le message est long, plus il y a de décimales (on a alors pensé utiliser des entiers, mais on reste limité)...
2.2. La compression de Huffman (non, pas Oeuf Man)
Prenons un texte (grande littérature) : ABCBBAC
Nous n'avons que trois lettres, et aucune suite redondante (donc LZ.. n'aura aucune efficacité).
La méthode : on attribue à chaque caractère présent un code binaire. L'avantage c'est que l'on a maximum 256 caractère, donc la taille maxi d'un code est de 8 bits, autrement dit, dans le pire des cas, on obtient la meme taille qu'au départ.
Pour calculer le code binaire d'un caractère, on utilise l'arbre de Shannon-Fano, ou arbre de Huffman :
En divisant successivement en 2 et en ajoutant en fonction du coté, par convention 0 à gauche, 1 à droite, le bit, on obtient des codes pour chaque caractère :
A : 00
B : 01
C : 10
D : 11
Soit ici, deux bits par caractère. Si on prend le message ABCDDCBA, incompressible avec LZW, on obtient un code de 2+2+2+2+2+2+2+2 (=8×2) = 16 bits soit 2 octets. On a un ratio de (8-2)/8 = 3/4 = 75% de compression (pas mal hehe)
En fait, il faut préciser au programme qui va décompresser à quoi correspondent ces codes, cad rentrer "code = caractère" pour chaque code ... Donc dans la réalité on n'aura pas 75% de compression sur un message aussi court
Mais qu'en est-il de notre AAAAAA ? On le coderait comme une série de 0000... mais on peut faire mieux, non ?
3. Les compressions de longueur
Elles ont une efficacité plus marquée sur les séries d'octets, mais peuvent doubler la taille du fichier si les données sont trop différentes...
Un exemple, RLE (Run Lenght Encoding).
La méthode : on replace chaque octet par un couple d'octets.
Exemple : AAAAABBBCCC [11 octets]
RLE : (A, 5)(B, 3)(C, 3) [6 octets]
Hehe oui là ca marche, mais la :
Texte : ABCDEFG [7 octets]
RLE : (A,1)(B,1)(C,1)(D,1)(E,1)(F,1)(G,1) [14 octets]
Là on ne compresse plus rien... C'est pourquoi ces méthodes ne sont utilisées que lorsqu'elles sont nécessaires (notemment pour le JPEG) et que les compresseurs "publics" comme WinRar ou WinAce ne les utilisent pas.
Le Pixel-Packing, utilisé dans le format d'image PICT d'Apple, consiste à condenser les données, en écrivant par dessus les 0 à droite le début de l'octet suivant :
un octet : [00011100]
le suivant : [11111110]
alors on aura : [000111|11] [111110--]]
(On ne gagne que 2 bits) et pour savoir où les bits sont ainsi juxtaposés, le fichier contient un index... donc on ne gagne pas grand chose...
Fin de la partie 1
Prochaine partie : La compression avec perte
Un grand merci à MM. S.Maadi, Y. Peneveyre, et C. Lambercy...
Pour plus d'info, le site de Mark Nelson : http://www.dogma.net/markn/
 Commentaires
|