Leçon
La théorie — Codage par plages (RLE)
Le codage par plages remplace chaque plage maximale de symboles identiques par un seul couple (symbole, compte). Ce qui arrive dans l’affichage n’est pas le texte mais deux nombres : N caractères et R plages. Toutes les autres valeurs de la page sont le quotient de ces deux-là.
Ce que signifie chaque symbole
N- le nombre de caractères en entrée — la longueur de ce que vous avez tapé, rien de plus.
R- le nombre de plages, c’est-à-dire de blocs maximaux d’un même symbole répété. R augmente de un partout où deux voisins diffèrent : il compte des frontières, pas des caractères.
L̄N/R, la longueur moyenne des plages. C’est la seule quantité qui décide du résultat.ratioN/2R, soitL̄/2. Au-dessus de 1, la sortie est plus petite que l’entrée.
D’où vient la formule
- Comptez des plages, pas des caractères. Dans
0010111100001111les voisins diffèrent en cinq endroits : il y a donc six plages et la ligne afficheR=6. - La taille codée vaut
2R, et rien d’autre. Ce dont les plages sont faites n’entre jamais dans le calcul — six plages coûtent douze unités, qu’il s’agisse de pixels, de lettres ou de chiffres. - Divisez :
ratio = N/2R = L̄/2. L’équilibre se situe donc àL̄ = 2, et il est exactement atteignable — tapezAABBet les barres affichent 4 octets à l’entrée, 4 à la sortie. - Les deux sens ne sont pas symétriques. Vers le haut, aucune limite : une seule plage d’un million de caractères se code en un couple. Vers le bas, le plancher est à
0.50×et ne peut être franchi, car le pire que puisse faire une entrée est de donner à chaque caractère sa propre plage.
Comment lire ce que vous voyez
Les quatre exemples font exactement seize caractères, ce qui vaut la peine de les lire comme un ensemble. Ligne d’image a trois plages et donne 6 octets. Plages classiques en a quatre et donne 8. Masque binaire en a six et donne 12. Pire cas en a seize et donne 32. Même longueur en entrée, et il sort de 6 à 32 octets — un facteur cinq, réglé entièrement par R. Tapez ensuite hello world : onze caractères, dix plages, 20 octets. La prose ordinaire se loge au bas de cette plage, et c’est toute la raison pour laquelle le codage par plages est un composant de compresseur plutôt qu’un compresseur.
- Suppose
- Qu’un couple coûte exactement 2 unités, qu’un symbole et un compte ont la même largeur, et qu’un compte peut être de taille quelconque. Les codeurs réels donnent au compte une largeur fixe — un octet, donc 255 — et doivent scinder une plage plus longue en plusieurs couples, ce qui remonte légèrement l’équilibre au-dessus de 2. L’hypothèse de largeur égale échoue le plus nettement là où le codage par plages excelle : dans un fax en 1 bit, le symbole tient sur un bit, le compte non.
- Ne tient plus quand
- Le plancher à
0.50×n’est pas un défaut qu’on pourrait supprimer par ingénierie. Un codeur sans perte doit être réversible : des entrées distinctes doivent donner des sorties distinctes, et il y a moins de chaînes courtes que de chaînes longues vers lesquelles envoyer. Tout procédé qui raccourcit ne serait-ce qu’une entrée en rallonge donc une autre. C’est un fait de dénombrement, pas une propriété du codage par plages. PackBits, dans le troisième éclairage ci-dessus, ramène son pire cas à un octet de contrôle pour 128 — moins de 1% — et personne ne va plus loin, car le plancher peut être abaissé sans limite mais jamais atteint. Le codage par plages se contente de porter ce coût à l’extérieur, dans un affichage qu’on peut regarder bouger.
Problème entièrement résolu
-
Encodage par plages de AAAAAABBBCCDDDDD en quatre paires 5 étapes
Le codage par plages transforme AAAAAABBBCCDDDDD en quatre paires. Calculez la compression, puis la condition exacte sous laquelle ce schéma rend un fichier plus grand.
-
Le codage est le plus évident : remplacer chaque plage par le caractère et sa longueur. Seize caractères se réduisent ainsi à quatre paires.
-
Deux nombres décrivent toute entrée de ce schéma — sa longueur et son nombre de plages — et leur rapport donne la longueur moyenne des plages. Ici, il vaut 4.
-
Comptons maintenant rigoureusement. Chaque paire coûte deux symboles, un caractère et un décompte, la sortie est donc de 2R pour une entrée de N. Rien d'autre concernant les données n'importe.
-
Le schéma est donc gagnant exactement lorsque 2R < N, ce qui équivaut à une longueur moyenne de plage supérieure à 2. Ici, 8 contre 16 — une réduction de moitié nette — et la ligne de verdict sur le panneau indique la même chose en un seul symbole.
-
En dessous de ce seuil, il est perdant, et pour une longueur moyenne de plage de 1, il perd de manière maximale : chaque caractère devient une paire, doublant la taille du fichier.
Réponse
L'outil affiche N = 16 et R = 4, une longueur moyenne de plage de 4 et un gain de 2×. La condition essentielle à retenir est la suivante : le codage RLE compresse si et seulement si les plages mesurent en moyenne plus de deux, et c'est l'un des rares schémas de compression dont le point de rentabilité est un nombre unique vérifiable à l'œil nu. Saisissez ABCD dans la zone de texte et observez la taille doubler. Ce n'est pas un défaut — c'est la raison pour laquelle le RLE ne survit que là où les plages sont garanties par construction : lignes de balayage de fax, bitmaps creux, et zones unies d'un JPEG après quantification, jamais sur du texte général.
-
Parcours
La compression à la main
Références (3)
- Insight block 3 — PackBits, and the control byte that bounds its worst case: Adobe Systems, TIFF Revision 6.0, section 9 (PackBits Compression), 1992 — the format where Apple's variant became a standard compression mode.
- The run lengths themselves as the thing to be coded: S. W. Golomb, "Run-length encodings (Corresp.)." IEEE Transactions on Information Theory 12(3), 399–401, 1966.
- And the earlier paper that measured how long runs in real pictures actually are: J. Capon, "A probabilistic model for run-length coding of pictures." IRE Transactions on Information Theory 5(4), 157–163, 1959.