Compression de données/Run-length encoding
Le run-length encoding, appelé en français le codage par plages, est un algorithme de compression de données sans perte en informatique. L'introduction de ce livre donne une explication de cet algorithme et des problématiques d'encodage liés.
Principe
modifierÀ l'origine, le système s'appliquait essentiellement à des documents scannés en noir et blanc, en particulier la transmission de télécopies. 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 fréquent d'avoir au moins 8 pixels noirs ou 8 pixels blancs de suite, 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 (comme en*) pour les pixels noirs et W (comme en*) pour les pixels blancs :
WWWWWWWWWWWWBWWWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWW
Un encodage Run Length Encoding consiste à 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 ça ne soit pas toujours le cas. On obtient, par exemple, pour la ligne précédente :
12W1B14W3B23W1B11W
Tandis que
WBWBWBWBWB
donnerait :
1W1B1W1B1W1B1W1B1W1B
Ce qui est deux fois plus long.
Remarque : dans le dernier cas, il serait plus efficace d'écrire uniquement la lettre si elle est seule (sans le chiffre 1). On aurait alors toujours au maximum la même taille.
Améliorations
modifierLe dernier exemple de la section précédente montre un cas où le codage systématique par un couple (compteur, donnée) peut doubler la taille dans le cas où le compteur vaut 1, ce qui est très fréquent.
On peut obtenir un meilleur encodage en encodant les séquences d'octets non répétés en spécifiant le type du compteur avec un bit. Par exemple, 0 pour un compteur donnant le nombre d'octets à copier sans répétition, et 1 pour un compteur donnant le nombre de répétition de l'octet suivant.
Applications
modifierLes formats d'images utilisent cette compression en considérant que toutes les lignes de pixels sont jointes pour former une unique séquence de couleurs.
- 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 (Recommandations ITU-T T.4 et T.6), son usage le plus fréquent hors informatique. Les lignes, ici des successions 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, dû à la faible vitesse de transmission des fax pour de telles images.