De Wikipedia, la enciclopedia libre
Saltar a navegación Saltar a búsqueda
No confundir con la duración limitada .

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 ocurre el mismo valor de datos en muchos elementos de datos consecutivos) se almacenan como un valor y recuento de datos únicos, en lugar de como 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 de líneas, 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 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.

Ejemplo [ editar ]

Considere una pantalla que contiene texto negro sin formato 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 exploración hipotética , en la que 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 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. Mientras que 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, a menudo usan 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 ejecución se puede expresar de varias formas 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 ejecución para ejecuciones de dos o más caracteres únicamente, utilizando un símbolo de "escape" para identificar las ejecuciones, o utilizando el carácter en sí 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:

WW12BWW12BB3WW24BWW14

Esto se interpretaría como una serie de doce W, una B, una serie de doce W, una serie de tres Bs, etc. En los 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 corridas extraídas, las frecuencias de diferentes caracteres pueden ser grandes, lo que permite una mayor compresión; sin embargo, si las longitudes de las corridas están escritas en el archivo en las ubicaciones donde ocurrieron las corridas, 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 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).

Historia y aplicaciones [ editar ]

Se emplearon de codificación (RLE) los sistemas de longitud de ejecución en la transmisión de señales de televisión analógicas tan atrás como 1967. [1] En 1983, de longitud ejecutar la codificación fue patentada por Hitachi . [2] [3] [4] RLE es particularmente adecuado para imágenes de mapa de bits basadas en paletas , como iconos de computadora , y era 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 como fotografías, aunque JPEGlo usa en los coeficientes que quedan después de transformar y cuantificar bloques de imagen.

Los formatos comunes para datos codificados de longitud de ejecución incluyen Truevision TGA , PackBits , PCX e ILBM . La Unión Internacional de Telecomunicaciones también describe un estándar para codificar tiradas en color 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 requerida ] es relativamente eficiente porque la mayoría de los documentos enviados por fax son generalmente espacios en blanco, con interrupciones ocasionales de negro.

Ver también [ editar ]

Referencias [ editar ]

  1. ^ Robinson, AH; Cherry, C. (1967). "Resultados de un esquema de compresión de ancho de banda de televisión prototipo". Actas del IEEE . IEEE . 55 (3): 356–364. doi : 10.1109 / PROC.1967.5493 .
  2. ^ "Ejecutar patentes de codificación de longitud" . Consorcio de Preguntas Frecuentes de Internet . 21 de marzo de 1996 . Consultado el 14 de julio de 2019 .
  3. ^ "Método y sistema de compresión y restauración de datos" . Patentes de Google . 7 de agosto de 1984 . Consultado el 14 de julio de 2019 .
  4. ^ "Método de registro de datos" . Patentes de Google . 8 de agosto de 1983 . Consultado el 14 de julio de 2019 .
  5. ^ Dunn, Christopher (1987). "¡Sonríe! ¡Estás en RLE!" (PDF) . El Transactor . Transactor Publishing . 7 (6): 16–18 . Consultado el 6 de diciembre de 2015 .
  6. ^ Recomendación T.45 (02/00): Codificación de color de longitud de ejecución . Unión Internacional de Telecomunicaciones . 2000 . Consultado el 6 de diciembre de 2015 .

Enlaces externos [ editar ]

  • Codificación de longitud de ejecución implementada en diferentes lenguajes de programación (en Rosetta Code )