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

 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).

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.

 

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).

   

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.