RLE (Run-Length Encoding)

Run Length Encoding (ou RLE, ou codage par plages) est une technique de compression de données (sans perte) basée sur les répétitions successives d'éléments.

Run Length signifie longueur de course, et en effet, avec RLE, ce qui importe c'est la longueur, la taille des répétitions (dans un texte, un message, etc.)

Le texte à encoder est parcouru pour trouver des suites de caractères identiques, noter alors le caractère et le nombre de répétition dans la séquence/suite.

Cette manière de procéder ne produit une compression que si le message est composé de nombreuses répétitions.

Variante d'écriture

Il est possible d'encoder en inversant les caractères et les décomptes.

Cas de données binaires

Si le message est composé de données binaires (0 et 1), alors il est possible d'utiliser RLE sans indiquer le caractère, les nombres suffisent. Le premier chiffre indiquant les 0 (ou bien les 1) puis en alternance.

Cas de données numériques

Si le message est composé de chiffres, alors utiliser un séparateur sous peine de ne plus pouvoir distinguer les caractères de leur nombre de répétition.

La décompression RLE consiste à parcourir le message formé de couples (caractère, nombre de répétition) et d'écrire l'équivalent en répérant le caractère le nombre de fois correspondant.

Cas de données binaires

Un message compressé avec RLE est composé de couples (Caractère-Nombre) ou triples (Caractère-séparateur-Nombre)

Les formats d'image Bitmap BMP et PCX utilisent RLE pour réduire la taille des fichiers.

RLE est particulièrement efficace pour les données comportant de longues séquences répétitives (ou motif identique). Les images binaires, les images avec des zones de couleur unie (comme les logos simples), ou les fichiers texte avec des caractères répétitifs bénéficient souvent d'une compression efficace avec RLE.

A l'inverse, RLE n'est pas efficace pour les données sans répétition ou contenant peu de répétitions. Dans ces cas, la taille des données compressées peut même augmenter par rapport à la taille d'origine.

RLE peut être combiné avec d'autres algorithmes de compression pour améliorer les performances (fichiers plus compacts).

Le code source de la fonction RLE pour l'encodage :
function RLE_Encode(input_string) {
encoded_string = ""
count = 1
for (i = 1; i < length(input_string); i++) {
if (input_string[i] == input_string[i - 1]) {
count = count + 1
}
else {
encoded_string += input_string[i - 1] + count
count = 1
}
}
encoded_string += input_string[i - 1] + count
return encoded_string
}

La fonction de décodage se programme ainsi :
function RLE_Decode(encoded_string) {
decoded_string = ""
for (i = 0; i < length(encoded_string); i+=2) {
char = encoded_string[i]
count = encoded_string[i+1]
decoded_string += string_repeat(char, count)
}
return decoded_string
}