Compresión RLE

Introducción

La compresión RLE (Run-Length Encoding) es una compresión relativamente antigua y muy usada. Se usa frecuentemente en archivos de imágenes como PCX (PiCture eXchange), PSD (PhotoShop Document), TGA, etc. Se usa también en muchos juegos debido a la sencillez de su implementación, velocidad de descompresión y baja memoria temporal necesaria. El algoritmo RLE se usa conjuntamente con el LZ77 para obtener un algoritmo que se comporta bastante bien con cadenas con muchos bytes seguidos repetidos y con secuencias repetidas.

Conceptos

Sea la cadena: AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABCDEFGAABBBBBBBBAAAA

La compresión RLE indicaría algo así: Sólo con repeticiones: <REP:40>A<REP:1>B<REP:1>C<REP:1>D<REP:1>E<REP:1>F<REP:1>G<REP:2>A<REP:8>B<REP:4>A Repeticiones y secuencias: <REP:40>A<SEC:6>BCDEFG<REP:2>A<REP:8>B<REP:4>A

De este modo, es posible codificar una cadena en un formato comprimido con una secuencia binaria de bits de varias formas, como usar uno o varios bytes exclusivamente para indicar la longitud que se repite seguidos de la secuencia (generalmente de un byte) que se repite. Una vez hecho esto, se vuelve a indicar la longitud, y así sucesivamente.

Por ejemplo, si hemos determinado que la implementación de RLE va a usar un byte para la longitud y va a repetir bytes, la cadena en hexadecimal <01><01><01><01><01><01><01><01><02><03><01><01><03><02><FF><FF><FF> se codificaría de la siguiente manera: <07><01><00><02><00><03><01><01><00><03><00><02><02><FF>

Nótese que para una repetición de 8 se ha usado el caracter "7" debido a que el 0 indicará 1, el 1, 2, el 2 3 y así sucesivamente. De esta manera, se aumenta el rango desde 0-255 a 1-256, pues nunca se va a querer repetir un byte 0 veces, ya que no tendría sentido.

Esta versión del RLE es de gran utilidad cuando hay muchos bytes repetidos contiguos y pocas variaciones. Sin embargo, hemos visto que cuando hay secuencias diferentes, tenemos que usar un byte adicional para indicar longitud 1 para cada byte que no tenga bytes idénticos contiguos.

Por ejemplo, <01><02><03><04><05><06> se codificaría <00><01><00><02><00><03><00><04><00><05><00><06>. De este modo, ocuparía el doble de espacio que el original.

Para evitar este problema, se complica un poco mas el algoritmo disminuyendo la longitud máxima de repetición pero mejorando estos casos. Para ello, se usa por ejemplo el último bit de la longitud para determinar si lo siguiente es una repetición o una secuencia. La longitud de las secuencias se usa para leer los bytes de la longitud y copiarlos tal cual al destino.

Si determinamos que el último bit del byte de longitud estará activo para secuencias e inactivo para repeticiones, podremos guardar secuencias de 1-128 bytes y repeticiones de 1-128 bytes.

Por ejemplo, <01><01><01><01><01><01><02><03><04><05><06><05><05> se codificaría de la siguiente manera: <05><01><85><01><02><03><04><05><06><01><02>.

Recuerda que en binario <05> es 00000101 y <85> es 10000101.

Enlaces de interés

RLE en la Wikipedia

RLE en Google

Pequeña descripción de algunos algoritmos de compresión (incluido RLE)