La codificación de longitud de ejecución ( RLE ) es una forma de compresión de datos sin pérdidas en la que las ejecuciones de datos (secuencias en las que el mismo valor de datos ocurre en muchos elementos de datos consecutivos) se almacenan como un único valor de datos y se cuentan, en lugar de como la ejecución original. . Esto es más eficaz en datos que contienen muchas ejecuciones de este tipo, 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 utilizar para referirse a uno de los primeros formatos de archivos de gráficos admitidos por CompuServe para comprimir imágenes en blanco y negro, pero fue ampliamente suplantado por su posterior formato de intercambio de gráficos (GIF). RLE también se refiere 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.
Considere una pantalla que contiene texto negro sobre un fondo blanco sólido. 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 , donde B representa un píxel negro y W representa un píxel blanco, podría leerse de la siguiente manera:
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 sólo 18. Si bien el formato real utilizado para el almacenamiento de imágenes es generalmente binario en lugar de caracteres ASCII. De esta manera, 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 los 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 ejecuciones de 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 algoritmos de compresión adicionales. Por ejemplo, un método popular codifica longitudes de ejecución para ejecuciones de dos o más caracteres únicamente, usando un símbolo de "escape" para identificar las ejecuciones, o usando el carácter mismo como escape, de modo que cada vez que un carácter aparece dos veces denota una ejecución. En el ejemplo anterior, esto daría lo siguiente:
WW12BWW12BB3WW24BWW14Esto 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.
Otro asunto es la aplicación de algoritmos de compresión adicionales. Incluso con las ejecuciones extraídas, las frecuencias de los diferentes caracteres pueden ser grandes, lo que permite una mayor compresión; sin embargo, si las longitudes de las ejecuciones se escriben en el archivo en las ubicaciones donde se produjeron las ejecuciones, la presencia de estos números interrumpe el flujo normal y hace que sea más difícil de comprimir. 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 ambos 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).
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 ya en 1967. [1] En 1983, Hitachi patentó la codificación de longitud de ejecución . [2] [3] [4] RLE se adapta particularmente bien a imágenes de mapa de bits basadas en paletas , como iconos de computadora , y fue un método de compresión de imágenes popular en los primeros servicios en línea como CompuServe antes de la llegada de formatos más sofisticados como GIF . [5] No funciona bien en imágenes de tonos continuos como fotografías, aunque JPEG lo utiliza 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 color de tirada para máquinas de fax , conocido como T.45. [6] El estándar, que se combina con otras técnicas en la codificación Huffman modificada , [ cita necesaria ] es relativamente eficiente porque la mayoría de los documentos enviados por fax generalmente tienen espacios en blanco, con interrupciones ocasionales en negro.