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 …