Dès le début de l'informatique, même si je ne saurais pas dater exactement quand, il a été question de stocker ou transmettre des données de manière efficace. Comment stocker ou transmettre un maximum de données avec un minimum d'espace ou de bande passante ? La compression de données répond à cette problématique avec des algorithmes qui repèrent l'information redondante pour la représenter de manière plus concise, ou bien qui éliminent des données jugées'(selon certains critères) moins utiles que d'autres.

Dans ce premier article, nous allons voir ce que j'imagine être la plus simple des méthodes et qui vient souvent à l'esprit en premier lorsque l'on découvre le sujet : la compression RLE (Run Length Encoding).

Le flux d'entrée

Imaginons une image en niveaux de gris que l'on pourrait représenter de cette manière :

................
....#######.....
..##@@@@@@@##...
.##@OOOOOOO@##..
.#@OoooooooO@#..
#@OoooooooooO@#.
#@OoooooooooO@#.
#@OoooooooooO@#.
#@OoooooooooO@#.
#@OoooooooooO@#.
#@OoooooooooO@#.
.#@OoooooooO@#..
.##@OOOOOOO@##..
..##@@@@@@@##...
....#######.....
................

Les niveaux de gris sont représentés par des caractères, et chaque caractère représente un pixel de l'image. L'image est de 16 lignes et 16 colonnes, soit 256 éléments. Ne nous occupons pas pour le moment de comment coder ces éléments. Ce sont juste des éléments.

L'idée générale

L'idée de la compression RLE vient de la constatation rapide qu'il existe des suites de données identiques dans les données, et que l'on peut même facilement énoncer. Par exemple, sur la première ligne, on peut dire qu'il y a 16 fois la valeur .. Sur la deuxième ligne, on peut dire qu'il y a 4 fois la valeur . puis 7 fois la valeur # puis 5 fois la valeur .. Et ainsi de suite.

C'est le principe de la compression RLE : on va remplacer les suites d'éléments identiques par deux éléments : le nombre de répétitions et la valeur répétée. Par exemple, la première ligne devient (16, '.'), la deuxième ligne devient (4, '.'), (7, '#'), (5, '.').

Voilà ce que cela donne pour l'image complète, si on met toutes les lignes bout à bout (sans les sauts de ligne) :

(20,.), (7,#), (7,.), (2,#), (7,@), (2,#), (4,.), (2,#), (1,@), (7,O), (1,@), (2,#), (3,.), (1,#), (1,@), (1,O), (7,o), (1,O), (1,@), (1,#), (2,.), (1,#), (1,@), (1,O), (9,o), (1,O), (1,@), (1,#), (1,.), (1,#), (1,@), (1,O), (9,o), (1,O), (1,@), (1,#), (1,.), (1,#), (1,@), (1,O), (9,o), (1,O), (1,@), (1,#), (1,.), (1,#), (1,@), (1,O), (9,o), (1,O), (1,@), (1,#), (1,.), (1,#), (1,@), (1,O), (9,o), (1,O), (1,@), (1,#), (1,.), (1,#), (1,@), (1,O), (9,o), (1,O), (1,@), (1,#), (2,.), (1,#), (1,@), (1,O), (7,o), (1,O), (1,@), (1,#), (3,.), (2,#), (1,@), (7,O), (1,@), (2,#), (4,.), (2,#), (7,@), (2,#), (7,.), (7,#), (21,.)

Ce qui donne 89 couples de valeurs, soit 178 éléments au total. Contre 256 éléments dans l'image d'origine. On a donc bien réduit le nombre d'éléments nécessaires pour représenter l'image.

Mais attention, ce qui permet la réduction, ce sont les suites de même valeur.

Si les données sont constituées de valeurs souvent changeantes, la compression ne va pas bien fonctionner, voire donner plus d´éléments en sortie. Par exemple, si l'image n'etait constituée que de valeurs différentes de leurs précédentes, on devrait à chaque fois écrire (1, élément), et donc au final doubler le nombre d'éléments nécessaires. Pas très efficace.

Codage du flux compressé

Jusqu'à maintenant, on n'a parlé que d'éléments. Cependant, ces éléments doivent être codés d'une manière ou d'une autre pour être stockés sur la machine. Par exemple, on peut considérer assez facilement que le flux d'entrée est codé en caractères sur 8 bits. C'est trop pour 4 valeurs différentes (2 bits sont suffisants), mais on peut imaginer avoir d'autres valeurs sur les 256 possibles dans d'autres images.

On va donc garder cette représentation en 8 bits pour les éléments valeurs. Même en sortie.

Pour le nombre de répétitions, il faut faire un choix sur le plus grand nombre de répétitions possibles. Ces choix vont dépendre de la nature des données. Pour un premier choix, on va faire simple : 256 répetition maximum. Une image de 16x16 éléments monochrome serait donc codée par deux valeurs en 8 bits : (0, valeur). En effet, comme une répéition de 0 n'a pas de sens, on se sert du 0 pour coder 256.

Deux octets au lieu de 256, c'est pas mal. Mais on peut aussi imaginer que les images monochromes ne sont pas représentatives.

En prenant un octet pour les répétitions et un octet pour la valeur, le codage et le décodage sont très simples et la taille pour l'image exemple est de 178 octets, soit 178 octets pour 256 éléments.

Peut-on faire mieux ?

Oui. Il y a plusieurs manières différentes de coder un flux compressé RLE. La méthode indiquée précédemment est la plus simple. Mais on peut en imaginer d'autres.

Par exemple, on peut réserver une plage de nombres dans l'indication des répétitions pour indiquer un nombre d'octets à suivre qui seront recopiés tels quels (parce qu'ils ne présentaient pas de répétition en entrée).

Par exemple, sur un morceau en entrée comme :

....#.#.#.....

On code les valeurs

(r4, '.'), (c5, '#.#.#'), (r3, '.')

Où r signifie "répétition" et c signifie "copie".

D'un point de vue codage, on peut choisir que les valeurs 0 à 127 représentent des répétitions, et les valeurs 128 à 255 représentent des copies.

Voilà ce que cela donne pour l'image complète avec cette méthode :

(20,.), (7,#), (7,.), (2,#), (7,@), (2,#), (4,.), (2,#), (129,@), (7,O), (129,@), (2,#), (3,.), (131,#@O), (7,o), (131,O@#), (2,.), (131,#@O), (9,o), (135,O@#.#@O), (9,o), (135,O@#.#@O), (9,o), (135,O@#.#@O), (9,o), (135,O@#.#@O), (9,o), (135,O@#.#@O), (9,o), (131,O@#), (2,.), (131,#@O), (7,o), (131,O@#), (3,.), (2,#), (129,@), (7,O), (129,@), (2,#), (4,.), (2,#), (7,@), (2,#), (7,.), (7,#), (21,.)

47 éléments au lieu de 89. Des éléments de taille variable cependant. Ici la taille en octets est de 136 plutôt que 178. Ce qui est un nouveau gain (au prix d'une toute petite complexité supplémentaire à traiter à la décompression)

Peut-on faire encore mieux ?

Vous pouvez trouver d'autres manières de coder un flux compressé RLE. En fonction de la plateforme, de la nature des données, de la taille des éléments, etc, il est possible de trouver des ajustements et des variations qui permettent de gagner de la place.

Conclusion

La compression RLE est une méthode simple à comprendre et à implémenter. Le temps de compression et de décompression sont très rapides car les calculs sont très simples.

Elle peut donner de bons résultats sur des données avec beaucoup de plages de même valeur. C'est aussi une méthode non destructive : une fois décompressées, les données sont identiques à l'original avant compression.

Dans un prochain article, nous verrons une autre méthode de compression classique et qui fonctionne bien sur des répétitions de motifs.

Supplément

Le code que j'ai utilisé lors de l'écriture pour vérifier les exemples est disponible ici.