Codificació Run-length

De Viquipèdia
Dreceres ràpides: navegació, cerca

La codificació Run-length (Run-length encoding, RLE) és una forma molt simple de compressió de dades en què seqüències de dades amb el mateix valor consecutiu són emmagatzemades com un únic valor més el seu recompte. Això és més útil en dades que contenen moltes d'aquestes seqüències, per exemple, gràfics senzills amb àrees de color pla, com icones i logotips.

Per exemple, si es considera una pantalla que conté text en negre sobre un fons blanc. Hi ha moltes seqüències d'aquest tipus amb píxels blancs en els marges buits, i altres seqüències de píxels negres a la zona del text. Suposant una línia (o scanline), on N representa les zones en negre i B les de blanc:

BBBBBBBBBBBBNBBBBBBBBBBBBNNNBBBBBBBBBBBBBBBBBBBBBBBBNBBBBBBBBBBBBBB

Si s'aplica la codificació run-length a aquesta línia, s'obtindrà el següent:

12B1N12B3N24B1N14B

Interpretat això com 12 bes, 1 ena, 12 bes, 3 enes, etc. El codi run-length representa l'original de 67 caràcters en tan sols 16 caràcters. Fins i tot fitxers de dades binàries poden ser comprimits utilitzant aquest mètode. Per aplicar aquesta codificació a dades binàries , només cal emprar el mateix principi, podent-lo utilitzar llavors en l'emmagatzematge d'imatges. El primer byte conté un nombre que representa el nombre de vegades que el caràcter està repetit. El segon byte conté el caràcter esmentat. En altres casos es codifiquen en un sol byte: 1 bit (0 o 1) i 7 bits per a especificar el nombre de caràcters consecutius.

No obstant això, sistemes de compressió més moderns sovint fan servir l'algorisme de deflació o altres algorismes basats en el LZSS, el qual té l'avantatge d'utilitzar seqüències de cadenes de caràcters.

Alguns formats que utilitzen aquesta codificació inclouen Packbits, PCX i ILBM.

La codificació run-length realitza una compressió de dades sense pèrdues i és molt utilitzat en imatges de 8 bits indexades (al principi va ser utilitzat per a imatges en blanc i negre). No funciona tan bé en imatges on varia constantment el color dels píxels com fotografies, encara que JPEG l'utilitza de manera efectiva en els coeficients que queden després de transformar i quantificar blocs d'imatges. Posteriorment ha format la base d'altres sistemes de compressió com ara el CCITT grup 3 - 1D.