Codage par plages (RLE)

Chaque plage — quelle que soit sa longueur — coûte le même stockage : 2 unités, une pour le symbole, une pour le nombre. Une plage de longueur L ne vaut la peine d'être codée que lorsque cela coûte moins que d'écrire L caractères bruts — c'est-à-dire quand L est supérieur à 2. En moyenne sur toute l'entrée, cette condition devient L̄ = N/R supérieur à 2, où N est la longueur totale et R le nombre de plages — exactement la limite que vérifie la formule ci-dessus. C'est aussi pourquoi le RLE est un mauvais compresseur généraliste : le texte anglais, le code source et les données aléatoires ont rarement des plages plus longues que 2, c'est pourquoi le RLE est réservé aux données conçues exprès pour avoir de longues plages — les scans fax en 1 bit, les bitmaps creux et les images à palette avec des aplats de couleur. Les formats réels poussent l'idée plus loin : le PNG applique un filtre delta Paeth/Sub/Up sur chaque ligne de balayage avant la compression, transformant d'abord les dégradés doux en longues plages de différences proches de zéro — le RLE (via DEFLATE) fait le reste. Essaie l'exemple du pire cas ci-dessus : seize caractères distincts donnent seize plages de longueur 1, donc le codage nécessite 32 unités pour stocker 16 caractères — l'entrée double de taille.

Le codage par plages est la seule idée de compression qu'on pourrait réinventer tout seul : au lieu d'écrire WWWWWWW lettre par lettre, on dit simplement "7 W" — le même raccourci qu'on emploie en lisant "trois fois sept" dans un numéro de téléphone. Il parcourt les données en une seule passe de gauche à droite et ne retient rien au-delà de la plage qu'il compte, ce qui le rend rapide et facile à diffuser en flux. Et il est sans perte : à partir des paires (symbole, compte) on reconstruit l'original à l'identique, contrairement au JPEG ou au MP3, qui jettent le détail pour de bon.

Le RLE naïf peut doubler des données incompressibles, mais la variante PackBits d'Apple — née dans le MacPaint des années 1980 et toujours un mode de compression standard du TIFF — est conçue pour ne presque jamais grossir. Chaque bloc commence par un octet de contrôle signé : une valeur non négative signifie "les octets suivants sont littéraux", une valeur négative "répète l'octet suivant". Les données uniques sont copiées telles quelles par blocs allant jusqu'à 128 octets, si bien que le pire cas n'ajoute qu'un octet de contrôle pour 128 — moins de 1 % de surcoût au lieu des 100 % que le RLE naïf peut atteindre.