Note utilisateur: 5 / 5

Etoiles activesEtoiles activesEtoiles activesEtoiles activesEtoiles actives
 

macro



En informatique, la place coûte cher...

Les barettes mémoire et les disques durs coûtent des sommes non négligeables, alors tout le monde s'efforce de ne pas trop les encombrer.
On a donc inventé des logiciels capables de compresser les données afin de les rendre moins volumineuses.

Ces opérations de compression sont également bienvenues lorsque l'on souhaite envoyer un fichier par mail ou à travers un réseau par exemple, afin de réduire sa taille, et par conséquent, son temps de transfert.

Mais comment fonctionnent ces logiciels de compression (comme WinZip, WinRAR, etc..) ?

C'est ce que nous allons découvrir...

 

Le principe

Prenons par exemple 30 lettres "A" :

001_GF

 

Il faut 30 octets dans la mémoire de l'ordinateur pour stocker cette suite de lettres.

Mais on pourrait noter la même information, de manière plus compacte :

002_GF

 

Et nous n'aurions alors besoin plus que de 3 octets seulement !

 

La compression (ou la décompression), c'est ça ! Pour une même donnée, on essaie de trouver la représentation la plus compacte possible.

 

On peut facilement passer de l'un à l'autre :

003_GF

 

Il existe de nombreuses méthodes différentes, plus ou moins astucieuses, pour gagner de la place : nous allons en voir quelques unes...

 

 

RLE (Run Lenght Enconding)

C'est exactemet notre exemple ci-dessus : on repère les répétitions et on les note de manière plus compacte.

On peut par exemple utiliser un symbole décimal comme "*" pour indiquer une répétition :

004_GF

 

C'est à dire :

005_GF

 

Ce système de compression est utilisé dans le format PCX, et dans certaines variantes du format TIFF.

 

 

Huffman

Huffman est un système de codage appellé "codage statistique".

Pour Huffman, il faut compter la fréquence de chaque caractère.

Imaginons que nous ayons compté la fréquence des lettres dans un texte :

006_GF

 

C'est à dire que dans notre texte, nous avions 92 lettres "A", 30 lettres "I", 11 lettres "M", etc...

La plus petite unité d'information que peut manipuler l'ordinateur est le bit : il vaut 0 ou 1.

On peut construire un arbre binaire :

007_GF

 

Plus une lettre est fréquente, moins on utilise de bits pour la représenter :

  • La lettre A (la plus fréquente) est représentée par un seul bit : 1
  • Pour la lettre I (un peu moins fréquente), on utilise 2 bits : 00
  • Pour la lettre O (encore moins fréquente), on utilise 3 bits : 010
  • Et ainsi de suite...

 

En binaire, le mot "MAISON" s'écrit normalement (en utilisant le code ASCII) :

008_GF

 

En Huffman (avec notre arbre binaire ci-dessus), le même mot devient :

009_GF

 

On a donc clairement gagné de la place !

  • Avant compression : notre texte prenait 48 bits (6 octets)
  • Après compression, il ne prend plus que 20 bits (2.5 octets)

Mais Huffman a un inconvénient : il faut faire une analyse de l'ensemble du texte avant de pouvoir le compacter, ce qui prend du temps.

Huffman est donc assez peu utilisé, surtout face aux performances d'autres algorithmes comme celui de Lempel-Kiv que nous allons voir dès à présent.

 

 

Lempel-Kiv

Le système Lempel-Kiv, lui, se construit au fur et à mesure un dictionnaire numéroté des "mots" déjà rencontrés.

S'il tombe sur un "mot" qu'il a déja croisé, il ne le recopie pas, mais il note uniquement son "numéro".

Voici à quoi ressemble l'algorithme de compactage :

010_GF

 

On commence avec un dictionnaire rempli avec tous les caractères existants (0 à 255) : par exemple 65 contient A, 66 contient B, etc...

 

Exemple : pour la chaîne : /WED/WE/WEE/WEB, il faut 15 x 8 = 120 bits pour la stocker en mémoire

Compactons-là avec Lempel-Kiv :

011_GF

 

L'algorithme sort : */WEBEB' et il ne faut donc plus que 4 x 8 + 6 x 9 = 86 bits (après /WED, on dépasse 255, il faut donc utiliser 9 bits).

 

Des variantes de cette méthode de compression sont utilisées dans les formats les plus courants : ZIP, RAR, ARJ, CAB, GIF, PNG, TIF...

C'est une méthode très populaire, et ce pour plusieures raisons :

  • elle est performante : elle compacte bien et rapidement toutes sortes de données
  • elle n'est pas très difficile à programmer
  • elle peut travailler sur des données au fur et à mesure qu'elles arrivent : pas besoin d'analyser toutes les données à l'avance comme avec Huffman
  • on peut utiliser des dictionnaires plus ou moins gros en fonction de la mémoire que l'on a à notre disposition (avec de petits dictionnaires, on compresse un peu moins bien les données, mais on compresse plus rapidement)
  • il existe de nombreuses variantes de Lempel-Kiv : LZ77, LZW, etc...

 

Les logiciels de compression les plus connus utilisent la méthode Lempel-Kiv, notamment WinZip et WinRAR

 

 

 

passez_le_test

 

 

greg

 

1000 caractères restants