Codificación por longitud de racha (RLE)

Cada racha — sin importar su longitud — cuesta lo mismo almacenar: 2 unidades, una para el símbolo y otra para el conteo. Una racha de longitud L solo merece la pena codificarla cuando eso cuesta menos que escribir L caracteres en bruto — es decir, cuando L es mayor que 2. Promediado sobre toda la entrada, esa condición se convierte en L̄ = N/R mayor que 2, donde N es la longitud total y R es el número de rachas — exactamente la línea que comprueba la fórmula de arriba. Esta es también la razón por la que RLE es un compresor de propósito general pobre: el texto en inglés, el código fuente y los datos aleatorios rara vez tienen rachas más largas que 2, por lo que RLE se reserva para datos diseñados a propósito para tener rachas largas — escaneos de fax de 1 bit, bitmaps dispersos e imágenes con paleta y áreas de color plano. Los formatos reales llevan la idea más lejos: PNG aplica un filtro delta Paeth/Sub/Up sobre cada línea de escaneo antes de comprimir, convirtiendo primero los degradados suaves en largas rachas de diferencias casi nulas — RLE (a través de DEFLATE) hace el resto. Prueba el ejemplo del peor caso de arriba: dieciséis caracteres distintos dan dieciséis rachas de longitud 1, así que la codificación necesita 32 unidades para almacenar 16 — la entrada duplica su tamaño.

La codificación por longitud de series es la única idea de compresión que podrías reinventar por tu cuenta: en lugar de escribir WWWWWWW letra por letra, dices simplemente "7 W" — el mismo atajo que usamos al leer "triple siete" en un número de teléfono. Recorre los datos en una sola pasada de izquierda a derecha y no recuerda nada más allá de la serie que está contando, lo que la hace rápida y fácil de transmitir en flujo. Y es sin pérdidas: a partir de los pares (símbolo, cuenta) puedes reconstruir el original exactamente, a diferencia de JPEG o MP3, que descartan detalle para siempre.

La RLE ingenua puede duplicar los datos incompresibles, pero la variante PackBits de Apple — nacida en el MacPaint de los años 80 y aún un modo de compresión estándar en TIFF — está diseñada para casi nunca crecer. Cada bloque empieza con un byte de control con signo: un valor no negativo significa "los siguientes bytes son literales", uno negativo "repite el byte siguiente". Los datos únicos se copian tal cual en bloques de hasta 128 bytes, así que el peor caso añade solo un byte de control por cada 128 — menos del 1 % de sobrecarga en vez del 100 % que la RLE ingenua puede alcanzar.