Ejecutar codificación de longitud

La codificación de longitud de ejecución ( codificación de longitud de ejecución en inglés , RLE corto ), la codificación de longitud de ejecución es un algoritmo de compresión simple sin pérdidas . Es adecuado para comprimir repeticiones más largas de símbolos. No pertenece al grupo de codificadores de entropía porque se basa en la frecuencia absoluta y no en la frecuencia relativa de los símbolos.

idea

La idea básica del algoritmo es reemplazar cada secuencia de símbolos idénticos con su número y, si es necesario, el símbolo. Esto significa que solo se marcan los lugares donde el símbolo cambia en el mensaje. Dado que la especificación de longitud solo crece logarítmicamente en comparación con la longitud de la secuencia , ahorra un espacio de almacenamiento considerable, especialmente con secuencias repetitivas largas. Por el contrario, cuanto más cortas sean las repeticiones, menor será el ahorro.

La codificación de longitud de ejecución se utiliza hoy en día como un paso de precodificación (por ejemplo, en la compresión de imágenes , como JPEG ) para ahorrar esfuerzo en el siguiente paso de codificación. (Por ejemplo, la codificación de Huffman ahorra mirar símbolos más largos, ya que estos ya se han reducido).

Ejemplo:

En lugar de una secuencia con cinco repeticiones del carácter 0 y tres veces 1

0000 0111

tu solo salva

5 3

Por lo tanto, el símbolo de inicio debe ser conocido o codificado adicionalmente.

Cuanto más largo sea un solo episodio, mayores serán los ahorros, porque

• para 10 repeticiones necesitas dos decimales,
• para 100 repeticiones necesitas tres decimales,
• para 1000 repeticiones necesita cuatro lugares decimales, etc.

Lo mismo se aplica a cualquier otro sistema numérico .

procedimiento

Cadenas de bits

Solo hay dos opciones para codificar secuencias de bits: una secuencia de ceros o una secuencia de unos. Se garantiza que cada secuencia de ceros será seguida por al menos uno, y viceversa también. La única excepción es cuando se llega al final del mensaje.

El codificador ahora está de acuerdo con el decodificador con qué bit comenzar. Esto puede ser por convención o, por ejemplo, por un bit adicional al principio. A continuación, las longitudes de las secuencias cero y uno se transmiten alternativamente. Entonces, el decodificador no tiene que hacer nada más que generar un número correspondiente de cero o uno bits para cada valor recibido.

Ejemplo:

La secuencia de inicio es:

1111 1110 0000 1000 0001 1111

Está codificado a partir de esto:

7 5 1 6 5

El número mínimo de dígitos binarios necesarios es tres, porque cubre el rango de números de 0 a 7. Luego, la secuencia comprimida se codifica en binario

111 101 001 110 101

Los 24 bits originales se podrían reducir a 15 bits.

Secuencias de símbolos de varios valores

Al comprimir secuencias de símbolos que constan de un alfabeto con más de dos símbolos, ya no está claro qué símbolo sigue a continuación (por ejemplo, los bytes tienen un alfabeto de 256 caracteres posibles). Además del número de repeticiones, también se debe enviar el símbolo que conforma la secuencia.

Una característica especial aquí es que el mensaje comprimido puede incluso ser más grande si el espacio de almacenamiento para el número de repeticiones es mayor que la secuencia en sí.

Ejemplo:

La secuencia de inicio es:

AAAA ABBB BBBB CDDD EE

Está codificado a partir de esto:

{A, 5}, {B, 7}, {C, 1}, {D, 3}, {E, 2}

En principio, un símbolo podría constar de dos letras en lugar de solo una:

{AA, 2}, {AB, 1}, {BB, 3}, {CD, 1}, {DD, 1}, {EE, 1}

En el peor de los casos (sin repeticiones), el mensaje "comprimido" sería más grande que el original. Del episodio

ABCD

haría

A1B1C1D1.

implementación

El algoritmo básico (sin optimizaciones) es fácil de implementar:

#include <stdio.h>

int main()
{
   int n = 1; /* Anzahl der Wiederholungen */
   int ch = -1; /* Aktuelles Zeichen */
   int prev_ch = getchar(); /* Vorheriges Zeichen */

   do {
      ch = getchar();

      if ((ch != prev_ch) || (n == 255)) /* Symbol/Wiederholungen-Tupel ausgeben, falls ein anderes Symbol kommt oder die maximal darstellbare Anzahl erreicht. */
      {
         /* printf("%c%c", prev_ch, n); */ /* Binäre Ausgabe */
         printf("%c, %d\n", prev_ch, n); /* Lesbare Ausgabe als 2er-Tupel */

         n = 0; /* Beginn einer neuen Folge */
      }

      prev_ch = ch;
      ++n;
   } while (ch != EOF);

   return 0;
}

Modificaciones

A veces hay muy pocas repeticiones en un mensaje. Para evitar que cada ocurrencia en un alfabeto de valores múltiples sea reemplazada por una tupla con longitud 1 (por ejemplo,  ABC→ A1B1C1), solo se codifican secuencias de cierta longitud (por ejemplo, cuatro o más ).

Pero luego necesita un carácter especial (carácter de escape ), que indica que sigue una tupla comprimida. En el caso ideal, este carácter o símbolo especial no aparece de otra manera en el mensaje; de ​​lo contrario, se elige un símbolo que se supone que ocurre raramente. La característica especial de este símbolo es que debe codificarse como una tupla cada vez (incluso si solo aparece una vez), de lo contrario no es posible diferenciar entre el símbolo y la tupla.

Ejemplo :

El mensaje original es:

Auus die Maaaaauuuuus (Longitud: 21 caracteres)

Elegimos el carácter "s" como carácter de escape (para mayor claridad). Además, solo codificamos secuencias que contienen al menos tres repeticiones:

Auuss1 die Msa5su5ss1 (Longitud: 21 caracteres)

Si una letra se repite más de tres veces o si es el carácter de escape , la salida del carácter de escape indica que sigue una tupla con especificación de longitud. A esto le sigue el número de repeticiones y finalmente el símbolo correspondiente.

De hecho, el carácter de escape genera requisitos de memoria adicionales, pero en el presente caso esto se compensa con el ahorro de secuencias de longitud 1. El mensaje se codificaría ingenuamente de la siguiente manera:

1A2u1s_1d1i1e_1M5a5u1s (Longitud: 22 caracteres)

Con el formato de archivo PCX , se usa un carácter de escape diferente dependiendo del número de repeticiones (estas constituyen una cuarta parte del juego de caracteres en PCX), de modo que los caracteres de escape y longitud coincidan para formar un carácter.

Aplicaciones

La codificación de longitud de ejecución se utiliza en combinación con una codificación Huffman modificada para la transmisión de fax de acuerdo con la recomendación ITU-T T.30 ("fax G3"). La codificación de la longitud de tirada consigue buenos resultados, especialmente al transmitir páginas en blanco y negro, ya que las áreas blancas largas se alternan con áreas negras más cortas.

En la compresión con pérdida de imágenes, la codificación de longitud de ejecución se aplica a los coeficientes individuales después de la transformación en el dominio de la frecuencia. Después de la cuantificación, en particular, normalmente hay muchos valores o ceros idénticos que se pueden comprimir eficazmente con la codificación de longitud de ejecución. Luego, estos datos "precomprimidos" se comprimen aún más con la codificación Huffman .

Formatos de archivo

Los formatos de archivo más conocidos que utilizan la codificación de longitud de ejecución son algunos formatos gráficos más antiguos, como Windows Bitmap , GEM Image , Targa o PCX . En Microsoft Windows , la extensión de archivo * .rle se usa generalmente para imágenes comprimidas con RLE .

literatura

• David Salomon: Compresión de datos: la referencia completa . 4ª edición. Springer, 2007, ISBN 978-1-84628-602-5 . 

Evidencia individual

1. ↑ T.30: Procedimientos para la transmisión de documentos por fax en la red telefónica general conmutada. UIT-T, consultado el 15 de agosto de 2013 .  

• David Salomon: Compresión de datos: la referencia completa . 4ª edición. Springer, 2007, ISBN 978-1-84628-602-5 , págs. 23-31 . 
• Jens-Rainer Ohm : Tecnología de comunicación multimedia . Springer, 2004, ISBN 3-540-01249-4 , págs. 479-481 .