Fișierele de date conțin frecvent același caracter repetat de mai multe ori într-o linie. De exemplu, fișierele text utilizează mai multe spații pentru a separa propozițiile, paragrafele de indentare, tabelele de formate și diagramele etc. Semnalele digitalizate pot avea, de asemenea, rulări aceleași valori, indicând faptul că semnalul nu se schimbă. De exemplu, o imagine a cerului pe timp de noapte ar conține lungi rulări ale caracterului sau caracterelor reprezentând fundalul negru. De asemenea, muzica digitalizată ar putea avea o rulare lungă de zerouri între melodii. Codificarea lungimii de rulare (RLE) este o metodă simplă de comprimare a acestor tipuri de fișiere.

Figura 27-1 ilustrează codificarea lungimii de rulare pentru o secvență de date care are nivele frecvente de zerouri. De fiecare dată când un zero este întâlnit în datele de intrare, două valori sunt înscrise în fișierul de ieșire. Prima dintre aceste valori este zero, un steguleț care indică faptul că începe compresia lungimii de rulare. A doua valoare este numărul de zerouri în rulare. Dacă lungimea medie de rulare este mai mare de doi, compresia va avea loc. Pe de altă parte, multe zerouri singure în date pot face fișierul codificat mai mare decât originalul.

Au fost dezvoltate multe scheme diferite de lungime de rulare. De exemplu, datele de intrare pot fi tratate ca octeți individuali sau grupuri de octeți care reprezintă ceva mai elaborat, cum ar fi numerele în virgulă mobilă. Codificarea lungimii de execuție poate fi utilizată numai pe unul dintre caractere (ca la zero de mai sus), mai multe caractere sau toate caracterele.

Un bun exemplu de schemă generalizată de lungime în execuție este PackBits, creată pentru utilizatorii Macintosh. Fiecare octet (opt biți) din fișierul de intrare este înlocuit cu nouă biți în fișierul comprimat. Al nouălea bit adăugat este interpretat ca semnul numărului. Adică, fiecare caracter citit din fișierul de intrare este între 0 și 255, în timp ce fiecare caracter scris în fișierul codat este între -255 și 255. Pentru a înțelege modul în care este utilizat, luați în considerare fișierul de intrare: 1,2,3,4,2,2,2,2,4 și fișierul comprimat generat de algoritmul PackBits: 1,2,3,4,2,-3,4. Programul de compresie transferă simplu fiecare număr din fișierul de intrare în fișierul comprimat, cu excepția rulării: 2,2,2,2. Acesta este reprezentat în fișierul comprimat prin cele două numere: 2, -3. Primul număr ("2") indică tipul caracterelor. Al doilea număr ("-3") indică numărul de caractere din rulare, găsite prin luarea valorii absolute și adăugând unu. De exemplu, 4,-2 înseamnă 4,4,4; 21,-4 înseamnă 21,21,21,21,21 etc.

Figura 27-1 Exemplu de codificare run-length.

Fiecare rulare de zerouri este înlocuită cu două caractere în fișierul comprimat: un zero care indică apariția compresiei, urmată de numărul de zerouri în rulare.

Un neajuns cu pachetele PackBits constă în faptul că cei nouă biți trebuie reformatați în octeții standard de opt biți utilizați în stocarea și transmisia pe computer. O modificare utilă a acestei scheme poate fi făcută atunci când intrarea este restricționată să fie text ASCII. După cum se arată în Tabelul 27-2, fiecare caracter ASCII este de obicei stocat ca un octet complet (opt biți), însă real utilizează doar șapte biți pentru a identifica caracterul. Cu alte cuvinte, valorile 127 până la 255 nu sunt definite cu nici un înțeles standardizat și nu trebuie să fie stocate sau transmise. Aceasta permite celui de-al optulea bit să indice dacă este în curs codarea lungimii de rulare.

Secțiunea următoare: Codificarea Huffman