Compression de données/Introduction

Compression de données

• Introduction
• Types de compression
• Techniques de compression sans perte
  • Codage par répétition
    • Run-length encoding
  • Codage entropique
    • Codage de Huffman
    • Codage de Shannon-Fano
  • Codage par dictionnaire
    • Lempel-Ziv-Welch (LZW)
  • Codage par modélisation de contexte
  • Transformée de Burrows-Wheeler
  • Archive de fichiers
• Techniques de compression avec pertes
  • Le format JPEG 2000
• Taux de compression
• Bibliographie et liens

Définition : Compression de données et décompression

La compression de données ou codage de source est l'opération informatique consistant à transformer une suite de bits A en une suite de bits B plus courte pouvant restituer les mêmes informations en utilisant un algorithme particulier. Opération de codage, elle raccourcit la taille (de transmission ou de stockage) des données au prix d'un effort de compression et de décompression. La décompression est l'opération inverse de la compression.

Avantages et inconvénients

La compression peut permettre de réduire la quantité de données à stocker. Les avantages possibles sont :

• réduire la capacité de stockage nécessaire, donc réduire le coût d'investissement,
• pouvoir stocker davantage de données sur un même support, donc éviter un surcoût en retardant la nécessité de recourir à un moyen de stockage supplémentaire,
• réduire le temps de chargement, particulièrement quand le temps de lecture est long,
• réduire l'emploi de la bande passante durant le transfert de données sur un réseau.

Les inconvénients sont :

• les données ne sont plus lisibles directement, il faut utiliser une application adaptée supportant l'algorithme de compression employé,
• la décompression est donc nécessaire avant de lire les données, ce qui peut prendre du temps. Sans certitude sur le gain par rapport à une lecture sans compression sur les systèmes les plus lents, il faut procéder à des mesures de performances pour vérifier s'il y a un gain de temps ;
• il n'est pas toujours possible d'implémenter un algorithme de compression, particulièrement sur les systèmes embarqués où la capacité de stockage peut être fortement limitée.

La section suivante présente un moyen simple de compresser des données.

Exemple de compression

L'exemple suivant illustre le principe de compression, employant un algorithme simple d'encodage des suites de caractères identiques. Le principe peut s'appliquer également aux fichiers binaires, en employant le terme octet au lieu de caractère.

Supposons qu'il faille stocker le texte suivant représentant un cadre :

+--------+
|        |
+--------+

Ce texte est composé de trois lignes de 10 caractères chacune, séparées par ce qu'on va supposer être un seul caractère de changement de ligne (Line feed, LF, pas de CRLF pour simplifier). Le texte source contient donc 32 caractères, soit 32 octets en supposant pour cet exemple que l'on code un caractère sur un octet :

• 1 caractère plus +
• 8 caractères moins/tiret -
• 1 caractère plus +
• 1 caractère de nouvelle ligne (\n)
• 1 caractère barre verticale |
• 8 caractères espace
• 1 caractère barre verticale|
• 1 caractère de nouvelle ligne (\n)
• 1 caractère plus +
• 8 caractères moins/tiret -
• 1 caractère plus +

Une manière de compresser ce texte est de réduire les répétitions en spécifiant le caractère répété et le nombre de répétitions, comme décrit par la liste précédente. Il suffit donc de coder une série de 11 couples de symboles (répétition, caractère) :

[ 1 ] [ + ] [ 8 ] [ - ] [ 1 ] [ + ] [ 1 ] [ \n ]
[ 1 ] [ | ] [ 8 ] [   ] [ 1 ] [ | ] [ 1 ] [ \n ]
[ 1 ] [ + ] [ 8 ] [ - ] [ 1 ] [ + ] 

En utilisant 1 octet par symbole, le texte compressé occupe donc 22 octets.

Cette technique est le principe des algorithmes RLE (Run-Length Encoding) encodant les suites de caractères répétés.

La décompression se fait simplement en lisant les symboles deux à deux (un nombre de répétitions et le caractère à répéter) en écrivant le caractère le nombre de fois indiqué.

Amélioration

Dans la suite compressée par la technique précédente, on remarque qu'il y a des séries de caractères répétés une seule fois.

Au lieu d'encoder chaque symbole sur un octet, une autre façon d'encoder est d'écrire :

• (a) soit un nombre de répétition suivi du caractère à répéter,
• (b) soit une longueur de séquence suivie des caractères non répétés.

Pour l'exemple précédent, cela donne les 18 symboles suivants :

 (b)         (a)         (b)                      (a)         (b)                      (a)         (b)
[ 1 ] [ + ] [ 8 ] [ - ] [ 3 ] [ + ] [ \n ] [ | ] [ 8 ] [   ] [ 3 ] [ | ] [ \n ] [ + ] [ 8 ] [ - ] [ 1 ] [ + ]

L'alternance entre (a) et (b) n'est qu'une coïncidence dû à l'exemple. Il peut y avoir différents caractères répétés à la suite, et plusieurs séquences de caractères non répétés à la suite, en particulier pour pallier la limite de stockage de la longueur de séquence ou du nombre de répétitions.

Il faut donc un moyen de distinguer entre les deux types de compteur, ce qui est généralement fait en réservant un bit dans un octet. Pour cet exemple, on choisit 0 pour une séquence de caractères non répétés, et 1 pour un nombre de répétition. Dans ce cas, il restera 7 bits dans l'octet pour coder soit un nombre de répétitions, soit une longueur de séquence, dans l'intervalle de 0 à 127. Afin d'optimiser l'intervalle, on utilise un décalage :

• Une séquence vide (longueur 0) n'ayant pas d'intérêt, on encode la longueur moins 1. On peut donc encoder des séquences de longueur comprise entre 1 et 128.
• Un nombre de répétition en dessous de 3 produisant plus ou autant de symboles qu'une séquence, on encode le nombre moins 3. On peut donc encoder un nombre de répétition compris entre 3 et 130.

En supposant que l'on encode chaque caractères sur un octet (ASCII), on obtient la forme compressée de 18 octets ci-dessous où le bit de poids fort de l'octet compteur indique le type (0 = (b) longueur de séquence de caractères non répétés - 1, 1 = (a) nombre de répétitions du caractère suivant - 3) :

  00    2B    85    2D    02    2B    0A     7C    85    20    02    7C    0A     2B    85    2D    00    2B
[b 1]-[ + ] [a 8]-[ - ] [b 3]-[ + ]-[ \n ]-[ | ] [a 8]-[   ] [b 3]-[ | ]-[ \n ]-[ + ] [a 8]-[ - ] [b 1]-[ + ]

Cette technique de compression sans perte est la base des algorithmes RLE (Run-Length Encoding), chacun définissant la façon d'encoder les symboles, certains étant adaptés à des données de taille plus petite ou plus grande qu'un octet.