Codarea lungimii de rulare (eng. r un- ength encoding , RLE ) sau codarea repetiției este un algoritm de comprimare a datelor care înlocuiește caracterele repetate (seria) cu un caracter și numărul repetărilor acestuia. O serie este o secvență formată din mai multe caractere identice. La codificare (ambalare, comprimare), un șir de caractere identice care alcătuiesc o serie este înlocuit cu un șir care conține caracterul care se repetă însuși și numărul repetărilor acestuia.
Luați în considerare o imagine care conține text negru pe un fundal alb solid . Când citiți pixelii unei astfel de imagini linie cu linie, vor exista o serie de pixeli albi (fond) și negri (litere) . O literă Bdenotă un pixel negru, iar o literă denotă W un pixel alb. Luați în considerare un șir de imagini arbitrare cu o lungime de 51 de caractere:
WWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWWSă numărăm numărul de caractere:
Total găsite 5 episoade. Să înlocuim seria cu numărul de repetări și caracterul care se repetă în sine:
9W3B24W1B14WRezultatul a fost o secvență de 12 caractere. Secvența originală a constat din 51 de caractere. Datele au fost comprimate de 51/12≈4,25 ori.
Să luăm un șir format dintr-un număr mare de caractere care nu se repetă:
ABCABCABCDDDFFFFFFDupă comprimarea prin metoda RLE, o astfel de linie va arăta astfel:
1A1B1C1A1B1C1A1B1C3D6FȘirul original este format din 18 caractere, iar șirul comprimat este format din 22. Dimensiunea datelor a crescut de 22/18≈1,22 ori.
Pentru ca după comprimare dimensiunea datelor să nu crească, alfabetul în care sunt înregistrate lungimile curselor este împărțit în două părți (de obicei egale). De exemplu, alfabetul numerelor întregi poate fi împărțit în două părți: numere pozitive și numere negative . Numerele pozitive sunt folosite pentru a înregistra numărul de repetări ale unui caracter, iar numerele negative sunt folosite pentru a înregistra numărul de caractere inegale care se succed.
Să numărăm personajele, ținând cont de cele de mai sus:
Șirul comprimat va fi scris astfel:
-9ABCABCABC3D6FȘirul original este format din 18 caractere, iar șirul comprimat este format din 15. Mărimea datelor a scăzut de 18/15=1,2 ori.
Să presupunem că implementarea metodei RLE pentru a înregistra lungimile seriei (pentru a număra numărul de caractere) utilizează o variabilă de tip întreg cu semnul „ ”. Într-o astfel de variabilă, puteți scrie numere de la -128 la 127 inclusiv. Ce se întâmplă dacă lungimea seriei este de 128 de caractere sau mai mult? În acest caz, seria este împărțită în părți, astfel încât lungimea părții să nu depășească 127 de caractere. De exemplu, o serie de 256 de caractere „A” ar fi codificată cu următorul șir (256=127+127+2): signed char
127A127A2AScrierea într-un limbaj de programare a algoritmului RLE, ținând cont de aceste restricții, este nebanală.
Desigur, codificarea folosită pentru stocarea imaginilor operează pe date binare și nu pe caractere ASCII , ca în exemplele discutate, dar principiul rămâne același.
Evident, o astfel de codificare este eficientă pentru date care conțin un număr mare de serii, de exemplu, pentru imagini grafice simple, cum ar fi pictograme și grafice. Cu toate acestea, această codificare nu este potrivită pentru imagini cu tonuri netede, cum ar fi fotografiile.
Formatele comune pentru împachetarea datelor cu RLE includ PackBits , PCX și ILBM .
Fișierele de date binare arbitrare pot fi comprimate prin codificarea lungimii de rulare , deoarece specificațiile de format de fișier includ adesea octeți repeți în zona de aliniere a datelor. Cu toate acestea, sistemele moderne de compresie (cum ar fi Deflate ) folosesc mai des algoritmi bazați pe LZ77 , care sunt o generalizare a metodei de codare a lungimii de rulare și operează pe secvențe de caractere de forma „BWWBWWBWWBWW”.
Datele audio care au cursuri lungi consecutive de octeți (cum ar fi mostre audio de calitate scăzută ) pot fi comprimate cu RLE după ce i-a fost aplicată codificarea Delta .
| Metode de compresie | |||||||
|---|---|---|---|---|---|---|---|
| Teorie |
| ||||||
| Fara pierderi |
| ||||||
| Audio |
| ||||||
| Imagini |
| ||||||
| Video |
| ||||||