Run-length encoding
Le run-length encoding est un algorithme de compression de données en informatique.
Le système s'applique essentiellement à des documents scannés en noir et blanc : au lieu de coder un bit par point, on dispose d'un compteur — en général sur un octet — indiquant combien de points blancs ou noirs se suivent. Comme il est rare de ne pas avoir au moins 8 pixels noirs ou 8 pixels blancs qui se suivent, et que 256 ne sont pas rares sur les endroits vierges ou les à-plats noirs, le système a bien pour effet une compression. S'il y a plus de 256 bits de la même couleur, on peut placer ensuite un octet spécifiant 0 bit de la couleur opposée, puis coder le nombre de bits qui restent...
Par exemple, considérons un écran de texte noir sur fond blanc. Il sera constitué de longues séquences de pixels blancs pour le fond, et de courtes séquences de pixels noirs pour le texte. Représentons une ligne d'un tel écran, avec B pour les pixels noirs et W pour les pixels blancs :
WWWWWWWWWWWWBWWWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWW
Un encodage RLE consiste alors à indiquer pour chaque suite de pixels d'une même couleur, le nombre de pixels de cette séquence. Le résultat comporte en général moins de caractères, bien que ce ne soit pas une obligation. On obtient par exemple pour la ligne précédente :
12WB14W3B23WB11W
Applications
- Le format BMP de Windows et OS/2 permet d'utiliser la compression RLE pour les images en 1, 4 et 8 bits/pixel (respectivement noir & blanc, 16 couleurs et 256 couleurs)
- Le format PCX utilise également la compression RLE pour les images en 8 et 24 bits/pixel. Dans le cas des images en 24 bits/pixel, l'image est en fait découpé en trois plans de couleur (rouge, vert et bleu) où chaque plan est encodé comme une image en 8 bits/pixel