La compression de données

Voila un terme que l’on comprend aisément mais dont on explique difficilement le fonctionnement. C’est justement ce genre de notions que j’aime expliquer dans ce blog.

 

De manière générale, comprimer des données est un problème simple à formuler : «  Réduire l’espace occupé par une information ».
 

Cette compression peut se réaliser sans altération du contenu, on parle alors de compression sans perte mais il existe aussi des systèmes de compression altérant légèrement l’information originale de manière à accroitre la compression. Cette dernière opération est ainsi qualifiée de compression avec pertes car dans ce cas, l’opération inverse (la décompression) ne redonne pas exactement l’original.
 

En informatique, la compression de données peut être formulée ainsi : « Transformer une série de bits en une autre série de bits plus petite à l’aide d’un algorithme tout en conservant l’information, c’est-à-dire que l’opération inverse doit être possible»

Compression sans perte

L’algorithme de compression sans perte le plus simple à comprendre est le système de codage RLE (Run Length Encoding) qui consiste à compter les répétitions d’un caractère (ou d’un bit).

Exemple de codage RLE : le mot « ouuuuuaauuuuuu » est interprété comme étant une suite d’un « o », de 5 « u », de 2 « a » et de 6 « u », soit : « o5u2a6u ». Nous avons donc compressé 14 caractères en 7 caractères (taux de compression de 50%). Il est évident que ce type de codage est pertinent uniquement si de grandes chaines de caractères sont répétées. C’est le cas pour l’encodage des fax pour coder la succession des points noirs et blancs sur une feuille (codage CCITT).

Les autres techniques de compression sans perte sont des techniques de compression entropique. Ces algorithmes sont basés sur une étude statistique de l’information à compresser de manière à encoder les caractères récurrents sur très peu de bit. Les algorithmes entropiques les plus connus sont l’algorithme de Huffman et l’algorithme LZ77.

L’algorithme de Huffman

Le mieux pour comprendre cet algorithme est de donner un exemple. Fixons nous comme objectif de compresser la phrase « LES SCIENTIFIQUES SONT INTELLIGENTS ».

En représentation ASCII classique, il faut 7 bits par lettre (2^7 = 128 caractères au total) : cette phrase de 35 caractères occupera donc un espace mémoire de 35*7=245 bits.
 

Maintenant, en utilisant le codage de Huffman, nous allons étudier le nombre d’occurrences de chaque lettre dans le texte à compresser de manière à attribuer un plus petit nombre de bits aux lettres les plus utilisées :

- C, F, Q, U, O, G : 1 occurrence

- L, ESPACE : 3 occurrences

- T, N : 4 occurrences

- E, S, I : 5 occurrences

On construit alors un arbre ou chaque feuille représente une lettre accompagnée de son poids (le nombre d’occurrences). On prend alors les 2 poids les plus faibles pour les regrouper et obtenir un nœud ayant un poids égal à la somme des 2 feuilles et ainsi de suite jusqu’à obtenir un seul nœud à la fin.
 

Avec notre exemple :

a) On regroupe les lettres de poids « 1 » et on les additionne pour faire des nœuds de poids « 2 » (jaune)

b) On ajoute les 2 lettres de poids « 3 » à 2 nœuds de poids « 2 » pour faire des nœuds de poids « 5 » (vert)

c) On ajoute les 2 lettres de poids « 4 » aux nœuds de poids « 2 » et « 5 » pour faire des nœuds de poids « 6 » et « 9 » (magenta).

d) On ajoute les 3 lettres de poids « 5 » aux nœuds de poids « 5 », « 6 » et « 9 » pour faire des nœuds de poids « 10 », « 11 » et « 14 » (orange).

e) On termine l’arbre jusqu’à obtenir un nœud commun de poids « 35 » (rouge).

f) Reste à attribuer une série de bit à chaque lettre. Pour cela, on choisit d’ajouter un bit « 0 » pour les branches de gauche et un bit « 1 » pour les branches de droites et on obtient alors l’arbre suivant : 

La phrase « LES SCIENTIFIQUES SONT INTELLIGENTS »est donc transcrite ainsi :

0100 011 001 1000 001 00010 11 011 101 0000 11 00011 11 10010 10011 011 001 1000 001 01010 101 0000 1000 11 101 0000 011 0100 0100 11 01011 011 101 0000 011

Ce qui représente au total 122 bits au lieu de 245 bits, soit un taux de compression de 50% environ. Le codage de Huffman est extrêmement performant et est utilisé comme dernière étape dans beaucoup d'autres algorithmes de compression.
 

L’algorithme LZ77 ou codage par dictionnaire

Cet algorithme permet de remplacer des séquences récurrentes par la position et la longueur de la première occurrence dans une fenêtre glissante. Par exemple, dans cet article, on retrouve le mot « compression » de nombreuses fois et au lieu de le réécrire à chaque fois, on pourrait simplement dire de revenir de « n » caractères en arrière et de recopier les « p » caractères suivants (p=11 dans le cas du mot « compression »).

Exemple :

« La compression est géniale, elle permet la compression de fichiers de toutes sortes ainsi que la compression de l’espace mémoire »

« La compression est géniale, elle permet la (41,11) de fichiers de toutes sortes ainsi que la (97,11) de l’espace mémoire »

 
On a donc réduit le nombre de caractère total de cette phrase. Cet algorithme s'avère très intéressant quand de grandes suites de caractères sont très récurrentes.
 

ZIP

Toute personne utilisant les ordinateurs est familière du format de compression dénommé zip (le plus souvent géré à l’aide du fameux logiciel pour Windows winzip). Zip est en fait un algorithme de compression sans perte permettant de compresser n’importe quel fichier informatique (texte, image, son, etc.). En fait, le zip utilise un algorithme dénommé deflate qui n’est rien d’autre que la succession d’un codage Huffman puis d’un codage LZ77.

 

Compression avec pertes

Ici, le principe consiste à exploiter les faiblesses de l’homme. En effet, notre ouïe et notre vue ne sont pas parfaites et de nombreuses informations contenues dans les fichiers audios ou visuels sont souvent inutiles car imperceptibles par nos sens. On comprend donc aisément que ce type de compression ne s’applique qu’aux fichiers audio, aux images, et aux films. De plus, une altération moindre de la qualité audio ou vidéo peut permettre de très importants taux de compression (supérieurs à 10).
 

Les formats les plus répandus sont bien évidemment le mp3 pour la musique, le jpeg pour les images et le mpeg-4 pour la vidéo (utilisé par divX et Xvid).

 

Toutes ces méthodes de compression reposent sur de très nombreux phénomènes de nos sens comme notre plus ou moins bonne sensibilité à différentes couleurs ou lumière ou bien notre sensibilité à différentes fréquences sonores. Néanmoins, toutes les techniques de compressions avec pertes utilisent la quantification pour réduire drastiquement la taille des fichiers puis une technique de codage sans perte à la fin peut être appliqués : c’est par exemple le cas dans les images jpeg où un codage RLE puis Huffman sont appliqués après la quantification.
 

 

 Mon chat en jpeg qualité 8 (44ko) et qualité 0 (21ko)
 

La quantification numérique

Pour coder une information sonore ou visuelle en format numérique, il faut procéder à une discrétisation du signal d’origine. Cette expression barbare, également appelée quantification, signifie que pour transformer un son ou une suite d’images (analogique) en format numérique (une suite binaire de « 1 » et de « 0 »), il faut « découper » l’information en petits éléments dans le temps mais aussi dans l’espace. Par exemple, un son étant caractérisé par une amplitude et une fréquence (voir billet précédent sur le son), il faut segmenter le signal dans le temps ainsi que son amplitude (quantification temporelle et spatiale).

 
 

Quantification d'un signal

En général, on choisit un débit de données cible à atteindre et le pas de quantification adéquat est ensuite déduit. La réduction du débit de données d’un média sonore ou visuel entrainera donc une réduction de sa taille mais également une dégradation de sa qualité en conséquence.
  

Exemple de quantification dans les mp3

Outre différentes techniques utilisées par le format mp3 pour réduire la taille des fichiers audio sans altérer notre perception des morceaux, la quantification est l’étape capitale de compression.

Par exemple pour un morceau de musique que l’on souhaite compresser en mp3, si on choisit un débit cible de 192 kbits / seconde, la qualité du morceau reste très bonne tout en réduisant le fichier CD de base d’un facteur 7 environ (il faut une oreille experte et un très bon matériel Hi-Fi pour déceler la différence). En revanche, si l’on compresse ce même morceau à un débit de 32 kbits / seconde, la qualité sera médiocre, toute personne verra immédiatement la différence mais le fichier sera 24 fois plus petit !