Codificación de longitud de ejecución

La codificación de longitud de ejecución (RLE) es una forma de compresión de datos sin pérdida en la que ejecuciones de datos (secuencias en las que los mismos datos valor ocurre en muchos elementos de datos consecutivos) se almacenan como un solo valor de datos y cuenta, en lugar de la ejecución original. Esto es más eficaz en datos que contienen muchas de estas ejecuciones, por ejemplo, imágenes gráficas simples como iconos, dibujos lineales, el juego de la vida de Conway y animaciones. Para archivos que no tienen muchas ejecuciones, RLE podría aumentar el tamaño del archivo.

RLE también se puede usar para referirse a un formato de archivo de gráficos anterior admitido por CompuServe para comprimir imágenes en blanco y negro, pero fue ampliamente reemplazado por su último formato de intercambio de gráficos (GIF). RLE también hace referencia a un formato de imagen poco utilizado en Windows 3.x, con la extensión rle, que es un mapa de bits codificado de longitud de ejecución, que se utiliza para comprimir la pantalla de inicio de Windows 3.x.

Ejemplo

Considere una pantalla que contenga texto negro sin formato sobre un fondo blanco uniforme. Habrá muchas tiradas largas de píxeles blancos en el espacio en blanco y muchas tiradas cortas de píxeles negros dentro del texto. Una línea de escaneo hipotética, con B representando un píxel negro y W representando un blanco, podría decir lo siguiente:

WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWW

Con un algoritmo de compresión de datos de codificación de longitud de ejecución (RLE) aplicado a la línea de exploración hipotética anterior, se puede representar de la siguiente manera:

12W1B12W3B24W1B14W

Esto se puede interpretar como una secuencia de doce W, una B, doce W, tres B, etc., y representa los 67 caracteres originales en solo 18. Si bien el formato real utilizado para el almacenamiento de imágenes es generalmente binario en lugar de caracteres ASCII. así, el principio sigue siendo el mismo. Incluso los archivos de datos binarios se pueden comprimir con este método; las especificaciones de formato de archivo a menudo dictan bytes repetidos en archivos como espacio de relleno. Sin embargo, los métodos de compresión más nuevos, como DEFLATE, suelen utilizar algoritmos basados en LZ77, una generalización de la codificación de longitud de ejecución que puede aprovechar las cadenas de caracteres (como BWWBWWBWWBWW).

La codificación de longitud de ejecución se puede expresar de varias maneras para adaptarse a las propiedades de los datos, así como a los algoritmos de compresión adicionales. Por ejemplo, un método popular codifica longitudes de tirada para tiradas de dos o más caracteres solamente, usando un "escape" símbolo para identificar carreras, o usar el propio carácter como escape, de modo que cada vez que un carácter aparece dos veces, denota una carrera. En el ejemplo anterior, esto daría lo siguiente:

WW12BWW12BB3WW24BWW14

Esto se interpretaría como una ejecución de doce W, una B, una ejecución de doce W, una ejecución de tres B, etc. En datos donde las ejecuciones son menos frecuentes, esto puede mejorar significativamente la tasa de compresión.

Otra cuestión es la aplicación de algoritmos de compresión adicionales. Incluso con las ejecuciones extraídas, las frecuencias de diferentes caracteres pueden ser grandes, lo que permite una mayor compresión; sin embargo, si las longitudes de ejecución se escriben en el archivo en las ubicaciones donde ocurrieron las ejecuciones, la presencia de estos números interrumpe el flujo normal y dificulta la compresión. Para superar esto, algunos codificadores de longitud de ejecución separan los datos y los símbolos de escape de las longitudes de ejecución, de modo que los dos puedan manejarse de forma independiente. Para los datos de ejemplo, esto daría como resultado dos salidas, la cadena "WWBWWBBWWBWW" y los números (12,12,3,24,14).

Historia y aplicaciones

Los esquemas de codificación de longitud de ejecución (RLE) se emplearon en la transmisión de señales de televisión analógicas desde 1967. En 1983, Hitachi patentó la codificación de longitud de ejecución. RLE es particularmente adecuado para imágenes de mapa de bits basadas en paletas, como íconos de computadora, y fue un método popular de compresión de imágenes en los primeros servicios en línea, como CompuServe, antes de la llegada de formatos más sofisticados, como GIF. No funciona bien en imágenes de tonos continuos como fotografías, aunque JPEG lo usa en los coeficientes que quedan después de transformar y cuantificar bloques de imágenes.

Los formatos comunes para datos codificados de longitud de ejecución incluyen Truevision TGA, PackBits (de Apple, utilizado en MacPaint), PCX e ILBM. La Unión Internacional de Telecomunicaciones también describe un estándar para codificar tirada-longitud-color para máquinas de fax, conocido como T.45. El estándar, que se combina con otras técnicas en la codificación Huffman modificada, es relativamente eficiente porque la mayoría de los documentos enviados por fax son generalmente espacios en blanco, con interrupciones ocasionales de negro.