Codificare run-length

Codificare run-length (din limba engleză run-length encoding, prescurtat RLE) este o formă de compresie de date fără pierderi în care seriile de date (apariții consecutive ale aceleiași valori) sunt stocate ca o singură apariție a acelei valori împreună cu numărul aparițiilor consecutive, în loc de seria originală. De exemplu, o secvență „verde verde verde verde verde” dintr-o imagine construită din puncte colorate ar putea fi scurtată la „verde x 5”.

Codificarea run-length este cea mai eficientă pe datele care conțin multe astfel de serii, de exemplu imagini grafice simple precum pictograme, desene liniare, jocuri și animații. Pentru fișierele care nu au multe serii, codificarea lor prin RLE ar putea mări dimensiunea fișierului.

RLE se poate referi și la anumite formate de imagine care utilizează această codificare. RLE este un format timpuriu de fișier grafic, susținut de CompuServe pentru comprimarea imaginilor alb-negru, ulterior înlocuit pe scară largă de formatul lor mai recent, Graphics Interchange Format (GIF). Este, de asemenea, numele unui format de imagine puțin folosit în Windows 3.x, salvat cu extensia de fișier rle, constând într-o hartă de biți codificată prin run-length; a fost utilizat ca format pentru ecranul de pornire al Windows 3.x.

Schemele de codificare run-length (RLE) au fost folosite în transmisia semnalelor de televiziune analogică încă din 1967.^[1] În 1983, codificarea run-length a fost brevetată de Hitachi.^[2][3][4] RLE este deosebit de potrivit pentru imagini bitmap bazate pe paletă (care folosesc relativ puține culori), precum pictogramele de calculator, și a fost o metodă populară de compresie a imaginilor pe primele servicii online, precum CompuServe, înainte de apariția unor formate mai sofisticate precum GIF.^[5] Nu funcționează bine pe imagini cu tonuri continue (care folosesc foarte multe culori), precum fotografiile, deși JPEG o folosește pe coeficienții rămași după transformarea și cuantizarea blocurilor de imagine.

Formate comune pentru datele codificate prin run-length includ Truevision TGA, PackBits (dezvoltat de Apple, folosit în MacPaint), PCX și ILBM. Uniunea Internațională a Telecomunicațiilor descrie, de asemenea, un standard pentru codificarea run-length a culorilor pentru aparatele de fax, cunoscut sub numele de T.45.^[6] Acest standard de codificare a culorilor pentru fax, care, împreună cu alte tehnici, este încorporat în codificarea Huffman modificată, este relativ eficient deoarece majoritatea documentelor faxate sunt în principal spații albe, cu întreruperi ocazionale de negru.

• Codificare RLE secvențială: această metodă procesează datele câte o linie o dată, scanând de la stânga la dreapta. Este utilizată frecvent în compresia imaginilor. Alte variații ale acestei tehnici includ scanarea datelor pe verticală, pe diagonală sau pe blocuri.
• Codificare RLE cu pierderi: în această variantă, unii biți sunt eliminați intenționat în timpul compresiei (adesea prin setarea la 0 a unuia sau a doi biți semnificativi ai fiecărui pixel). Acest lucru duce la rate de compresie mai ridicate, afectând în același timp minimal calitatea vizuală a imaginii.
• Codificare RLE adaptivă: folosește scheme de codificare diferite în funcție de lungimea seriilor, pentru a optimiza ratele de compresie. De exemplu, seriile scurte pot folosi un format de codificare diferit față de seriile lungi.

• Codificarea run-length implementată în diferite limbaje de programare (pe Rosetta Code)
• Bibliotecă header-only pentru codificare run-length, cea mai mică implementare posibilă (aproximativ 20 de linii de cod sursă) în ANSI C. Software liber, compatibil cu Truevision TGA, suportă și elemente de 8, 16, 24 și 32 de biți.