Compression de données

Chapitre IV

Compression de données

1. Qu'est-ce que la compression de données?

La compression des données consiste à réduire la taille physique des blocs d'informations (texte, images, son, etc…).

Un logiciel de compression utilise, lors de la compression, un algorithme qui sert à optimiser les données en utilisant des considérations propres au type de données à compresser et lors de la décompression et pour reconstruire les données originales, il utilise l'algorithme inverse de celui utilisé pour la compression.

La méthode de compression dépend intrinsèquement du type de données à compresser : on ne compressera pas de la même façon une image qu'un fichier audio!

2. Critères de choix d'un algorithme de compression

Pour le choix d'un algorithme de compression, il existe trois critères à vérifier :

• Taux de compression :

C’est le Rapport de la taille du fichier compressé sur la taille du fichier initial.

Exemple : taille originale = 100 KO et taille compressée = 50 KO

Alors : Taux de compression = 50/100 = 0,5 = 50%

Le gain de compression = 100% - taux de compression

Dans ce cas, c’est égal à 100% - 50% = 50%

• Qualité de compression :

o Sans perte.

o Avec perte => Pourcentage de perte

• Vitesse de :

o Compression,

o Décompression

3. Compression symétrique et asymétrique

Dans le cas de la compression symétrique, la même méthode est utilisée pour compresser et décompresser l'information, il faut donc le même temps pour chacune de ces opérations. C'est ce type de compression qui est généralement utilisé dans les transmissions de données.

La compression asymétrique demande plus de temps pour l'une des deux opérations. On recherche souvent des algorithmes pour lesquels la compression est plus lente que la décompression.

4. Compressions sans perte

4.1. La compression RLE (ou RLC)

La méthode de compression RLE (RunLengthEncoding, parfois notée RLC pour RunLengthCoding) est basée sur la répétition d'éléments (bits ou caractères) consécutifs.

Dans cet algorithme, toute suite de bits ou de caractères identiques est remplacée par le couple : nombre d'occurrences ; bit ou caractère répété.

Le RLE est une technique utilisée dans les images matricielles (de formats BMP, PCX, TIFF), car une image est composée, d’une zone à une autre, par de plusieurs pixels contigus et de même couleur.

Etapes de RLE :

(1) Recherche des caractères (pixels) répétés au moins n fois (avec n fixé par l'utilisateur (au moins 3 fois))(car en dessous de 3 fois, RLE s'est avéré non rentable).

(2) Pour chaque caractère de la chaine (ou pixel de l’image), remplacer ses itérations par :

o Le nombre de fois de répétition du caractère (ou du pixel),

o Le caractère (ou le pixel) répété.

Exemple :

• La chaîne suivante de 14 caractères : "ABCCCCCCDDEEEE".

• On donne n = 3 fois

• La chaîne sera donc compressée en 10 caractères : ‘’1A1B6C2D4E’’

• Taux de compression : 10 / 14 = 71,4%.

• Gain de compression : 100% - taux de compression =100% -71,4% = 28,6%

Caractéristiques de compression RLE :

o Algorithme très simple.

o Taux de compression relativement faible.

o Adapté aux images matricielles qui comportent plus de répétitions.

Ainsi la compression RLE n'a du sens que pour les données possédant de nombreux éléments consécutifs redondants, notamment les images possédant de larges parties uniformes. Cette méthode a toutefois l'avantage d'être peu difficile à mettre en œuvre. Il existe des variantes dans lesquelles l'image est encodée par pavés de points, selon des lignes horizontales, verticales ou même en zigzag.

4.2. Le codage de Huffman (Algorithme de compression sans perte)

David Huffman a proposé en 1952 une méthode statistique qui permet d'attribuer un mot de code binaire aux différents symboles à compresser (pixels ou caractères par exemple). La longueur de chaque mot de code n'est pas identique pour tous les symboles: les symboles les plus fréquents (qui apparaissent le plus souvent) sont codés avec de petits mots de code, tandis que les symboles les plus rares reçoivent de plus longs codes binaires. On parle de codage à longueur variable (en anglais VLC pour variable length code) préfixé pour désigner ce type de codage car aucun code n'est le préfixe d'un autre. Ainsi, la suite finale de mots codés à longueurs variables sera en moyenne plus petite qu'avec un codage de taille constante.

Le codeur de Huffman crée un arbre ordonné à partir de tous les symboles et de leur fréquence d'apparition. Les branches sont construites récursivement en partant des symboles les moins fréquents.

La construction de l'arbre se fait en ordonnant dans un premier temps les symboles par fréquence d'apparition. Successivement les deux symboles de plus faible fréquence d'apparition sont retirés de la liste et rattachés à un nœud dont le poids vaut la somme des fréquences des deux symboles.

Les compressions basées sur ce type de codage donnent de bons taux de compressions, en particulier pour les images monochromes (les fax par exemple).

Le codage de Huffman est utilisé pour la compression du son au format MP3, des vidéos MPEG et

...