C'est la plus simple des méthodes de compression. Elle est basée sur le fait que dans un fichier, on trouve plusieurs octets consécutifs identiques. On va donc regrouper ces octets ensemble. Par exemple au lieu d'écrire - 065 - 065 - 065 - 065 - 065 - On va écrire - 005 - 065 - ce qui signifie « 5 octets de valeur 65 ». On a donc utilisé 2 octets au lieu de 5 : ici, on en a gagné 3. Mais on trouve des cas où il n'y a pas de compression : par exemple - 070 - 114 - 101 - 100 - devient - 001 - 070 - 001 - 114 - 001 - 101 - 001 - 100 - : on a perdu 4 octets.
Le cas le plus favorable est celui où les octets du fichier sont regroupés par paquets de 256 (on ne peut pas en regrouper davantage car le nombre de répétitions est codé sur 1 seul octet.) et donc lorsque la taille du fichier a été divisée par 128, alors que le moins favorable est celui où on ne trouve jamais deux octets consécutifs de même valeur : on a multipliée la taille par 2 :
Le graphique ci-dessus semble nous montre une moyenne de compression presque identique à la taille sans compression. Mais en fait c'est pire que cela car le nombre de chances que la taille double est beaucoup plus élevé que le cas où la taille est divisé par 128.
Par exemple pour un fichier de N octets (considérons N multiple de 256 pour faire plus simple). Il y a 1 chance sur 256 pour qu'un octet soit égale à celui qui le précède. Pour qu'un bloc de 256 octets ne comporte que des octets identiques, il faut donc que le second soit égale au premier (1 chance sur 256), puis il faut aussi que le 3e soit égale au 2e (encore 1/256) et ainsi de suite. ce qui fait (1/256)255 = 1/(256255), c'est à dire pratiquement aucune chance ! Pour le fichier en entier c'est pire : en considérant les (N/256) blocs, on trouve : 1/(256255)(N/256) = 1/(256255N/256).
Par contre pour qu'il n'y est aucune suite de deux octets identiques, l'opération ait ((255/256)255)(N/256) = (255/256)(255N/256), ce qui fait un pourcentage nettement plus important.
En fait, la méthode RLE n'est pas très puissante dans le cas général, et il vaut mieux l'employer lorsque l'on est sur d'obtenir compression : il vaut mieux l'utiliser pour des images que pour des textes...
Au début du fichier, mettre quelques octets qui indiquent la manière dont les blocs sont regroupés, manière qui fourni la meilleure compression. Par exemple : lecture un octet sur deux (on fait alors deux passages), en choisissant de coder verticalement ou horizontalement pour les images etc...
Une autre manière de faire et que j'utilisais avant pour mon format d'image : diminuer le nombre de couleurs à 128 (au lieu de 256), et se servir du bit récupéré pour indiquer si oui ou non il y a plus de 2 pixels consécutifs identiques si la réponse est affirmative, l'octet suivant indique le nombre de pixels.
Il y a aussi une autre méthode dans le même genre, et dont je me sert pour les images FWC. On suppose que chaque couleur d'une image est codée sur un mot 8 bits par exemple, ce qui fait 256 couleurs différentes. On supprime alors une couleur (par exemple la couleur 0). Lorsque le décodeur tombe sur un mot de valeur 0, cela l'avertit qu'il y a plus de 4 répétitions et il met par conséquent un Compteur à 4. Le mot suivant lui indique alors la couleur. Mais si la couleur est encore zéro, il ajoute 256 au compteur et ainsi de suite. Une fois la couleur déterminée il ajoute encore la valeur du prochain mot au Compteur. Il a alors trouvé Compteur répétitions de la même couleur.
