La codificación por longitud de ejecución ( RLE ) es una forma de compresión de datos sin pérdida en la que las ejecuciones de datos (ocurrencias consecutivas del mismo valor de datos) se almacenan como una única ocurrencia de ese valor de datos y un recuento de sus ocurrencias consecutivas, en lugar de como la ejecución original. Como ejemplo imaginario del concepto, al codificar una imagen construida a partir de puntos de colores, la secuencia "verde verde verde verde verde verde verde verde verde" se acorta a "verde x 9". Esto es más eficiente en datos que contienen muchas ejecuciones de este tipo, por ejemplo, imágenes gráficas simples como íconos, dibujos lineales, juegos y animaciones. Para los archivos que no tienen muchas ejecuciones, codificarlos con RLE podría aumentar el tamaño del archivo.
RLE también puede referirse en particular a un formato de archivo de gráficos temprano compatible con CompuServe para comprimir imágenes en blanco y negro, que fue ampliamente reemplazado 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 que se guarda con la extensión de archivo rle; es un mapa de bits codificado por longitud de ejecución, y el formato se utilizó para la pantalla de inicio de Windows 3.x.
Los esquemas de codificación de longitud de ejecución (RLE) se emplearon en la transmisión de señales de televisión analógica desde 1967. [1] En 1983, Hitachi patentó la codificación de longitud de ejecución . [ 2 ] [3] [4] RLE es particularmente adecuado para imágenes de mapa de bits basadas en paletas (que usan relativamente pocos colores) como íconos 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 tono continuo (que usan muchos colores) como fotografías, aunque JPEG lo usa en los coeficientes que quedan después de transformar y cuantificar bloques de imagen.
Los formatos comunes para datos codificados por 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 el color por longitud de ejecución para máquinas de fax , conocido como T.45. [6] Ese estándar de codificación de color de fax, que junto con otras técnicas se incorpora a la codificación Huffman modificada , [ cita requerida ] es relativamente eficiente porque la mayoría de los documentos enviados por fax son principalmente espacios en blanco, con interrupciones ocasionales de negro.
RLE tiene una complejidad espacial de , donde n es el tamaño de los datos de entrada.
La codificación por longitud de ejecución comprime los datos al reducir el tamaño físico de una cadena repetida de caracteres. Este proceso implica convertir los datos de entrada a un formato comprimido mediante la identificación y el recuento de las apariciones consecutivas de cada carácter. Los pasos son los siguientes:
desde itertools importar repetir , comprimir , agrupar pordef ilen ( iterable ): """ Devuelve el número de elementos en iterable. >>> ilen(x for x in range(1000000) if x % 3 == 0) 333334 """ # usando zip() para envolver la entrada con 1-tuplas que compress() lee como valores verdaderos. return sum ( compress ( repeat ( 1 ), zip ( iterable )))def rle_encode ( iterable , * , length_first = True ): """ >>> "".join(rle_encode("AAAABBBCCDAA")) '4A3B2C1D2A' >>> "".join(rle_encode("AAAABBBCCDAA", length_first=False)) 'A4B3C2D1A2' """ return ( f " { ilen ( g ) }{ k } " if length_first else f " { k }{ ilen ( g ) } " # ilen(g): longitud del iterable g para k , g en groupby ( iterable ) ) [7]
El proceso de decodificación implica reconstruir los datos originales a partir del formato codificado repitiendo los caracteres según su número. Los pasos son los siguientes:
desde itertools importar cadena , repetir , por lotesdef rle_decode ( iterable , * , length_first = True ): """ >>> "".join(rle_decode("4A3B2C1D2A")) 'AAAABBBCCDAA' >>> "".join(rle_decode("A4B3C2D1A2", length_first=False)) 'AAAABBBCCDAA' """ return cadena .from_iterable ( repetir ( b , int ( a )) si length_first de lo contrario repetir ( a , int ( b )) para a , b en batched ( iterable , 2 ) ) [7]
Considere una pantalla que contiene texto negro sobre un fondo blanco sólido. Habrá muchas líneas largas de píxeles blancos en el espacio en blanco y muchas líneas 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 el 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 escaneo 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 como este, 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 a menudo utilizan algoritmos basados en LZ77 , una generalización de la codificación de longitud de ejecución que puede aprovechar las ejecuciones de cadenas de caracteres (como BWWBWWBWWBWW).
La codificación de longitud de serie se puede expresar de varias maneras para acomodar las propiedades de los datos, así como algoritmos de compresión adicionales. Por ejemplo, un método popular codifica longitudes de serie para series de dos o más caracteres únicamente, utilizando un símbolo de "escape" para identificar series, o utilizando el propio carácter como escape, de modo que cada vez que un carácter aparece dos veces, denota una serie. En el ejemplo anterior, esto daría lo siguiente:
WW12BWW12BB3WW24BWW14Esto se interpretaría como una serie de doce W, una B, una serie de doce W, una serie de tres B, etc. En datos donde las series son menos frecuentes, esto puede mejorar significativamente la tasa de compresión.
Otro tema 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 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 ambos se puedan manejar 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).