Run-length encoding

Le run-length encoding, appelé en français le codage par plages, 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 :

12W1B14W3B23W1B11W

Tandis que :

WBWBWBWBWB

donnerait :

1W1B1W1B1W1B1W1B1W1B

Ce qui est deux fois plus long.

Applications

Les formats d'images utilisent cette compression en considérant que toutes les lignes de pixels sont jointes pour former une unique séquence de couleur.

• 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 le principe de 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ée en trois plans de couleur (rouge, vert et bleu) où chaque plan est encodé comme une image en 8 bits/pixel.

RLE est aussi utilisé pour les fax Groupe 3 et Groupe 4 (Recommendations ITU-T T.4 et T.6), son usage le plus fréquent hors informatique. Les lignes, ici des succcessions de points blancs ou noirs, sont codées par leur longueur en pixel de chaque couleur. Mais les longueurs sont codées en fonction de leur fréquence d'apparition. Et ce codage fait partie de la spécification. Il s'agit d'une sorte de compression Huffman prédéfinie. Chaque segment est forcément de la couleur opposée et cette couleur ne doit donc pas être transmise, augmentant la compression. Dans l'exemple le W et B ne sont pas transmis. Par contre, cela implique que chaque ligne commence par une couleur connue. Et quand la longueur dépasse celle possible, on intercale l'autre couleur mais de longueur nulle.

La même compression peut être utilisée en niveaux de gris mais elle est alors peu efficace, de là la faible vitesse de transmission des fax pour de telles images.

Articles connexes

• Suite de Conway