Lección
La teoría — Codificación por longitud de racha (RLE)
La codificación por longitud de series sustituye cada serie maximal de símbolos idénticos por un único par (símbolo, cuenta). A la lectura no llega el texto, sino dos números: N caracteres y R series. Cualquier otra cifra de la página es el cociente de esos dos.
Qué significa cada símbolo
N- el número de caracteres que entran — la longitud de lo que has escrito, nada más.
R- el número de series, es decir, bloques maximales de un mismo símbolo repetido. R sube en uno allí donde dos vecinos difieren: cuenta fronteras, no caracteres.
L̄N/R, la longitud media de las series. Es la única cantidad que decide el resultado.ratioN/2R, es decirL̄/2. Por encima de 1 la salida es menor que la entrada.
De dónde viene la fórmula
- Cuenta series, no caracteres. En
0010111100001111los vecinos difieren en cinco puntos, así que hay seis series y la fila muestraR=6. - El tamaño codificado es
2Ry nada más. De qué están hechas las series no entra nunca en la cuenta: seis series cuestan doce unidades, sean píxeles, letras o dígitos. - Divide:
ratio = N/2R = L̄/2. El equilibrio queda pues enL̄ = 2, y es exactamente alcanzable — escribeAABBy las barras marcan 4 bytes de entrada y 4 de salida. - Los dos sentidos no son simétricos. Hacia arriba no hay límite: una sola serie de un millón de caracteres se codifica en un par. Hacia abajo el suelo está en
0.50×y no se puede rebajar, porque lo peor que puede hacer una entrada es dar a cada carácter su propia serie.
Cómo leer lo que ves
Los cuatro ejemplos miden exactamente dieciséis caracteres, y por eso conviene leerlos como un conjunto. Línea de imagen tiene tres series y da 6 bytes. Series clásicas tiene cuatro y da 8. Máscara de bits tiene seis y da 12. Peor caso tiene dieciséis y da 32. La misma longitud de entrada, y sale entre 6 y 32 bytes — un factor cinco, decidido por completo por R. Escribe luego hello world: once caracteres, diez series, 20 bytes. La prosa corriente se sitúa en la parte baja de ese rango, y ésa es toda la razón por la que este método es una pieza dentro de los compresores y no un compresor por sí solo.
- Supone
- Que un par cuesta exactamente 2 unidades, que un símbolo y una cuenta ocupan lo mismo, y que una cuenta puede ser de cualquier tamaño. Los codificadores reales dan a la cuenta un ancho fijo — un byte, o sea 255 — y deben partir una serie más larga en varios pares, lo que sube el equilibrio algo por encima de 2. El supuesto de ancho igual falla justo donde este método brilla: en un fax de 1 bit el símbolo ocupa un bit y la cuenta no.
- Falla cuando
- El suelo de
0.50×no es un defecto pendiente de resolver. Un codificador sin pérdidas tiene que ser reversible, de modo que entradas distintas den salidas distintas; y hay menos cadenas cortas que largas a las que enviarlas. Todo esquema que acorte aunque sea una entrada alarga por fuerza alguna otra. Es un hecho de conteo, no una propiedad de este método. PackBits, en la tercera idea de arriba, baja su peor caso a un byte de control por cada 128 — menos del 1% — y hasta ahí llega cualquiera, porque el suelo se puede bajar sin límite pero nunca alcanzar. Lo que hace este método es llevar ese coste por fuera, en una lectura que puedes ver moverse.
Problema resuelto al detalle
-
Codificación run-length de AAAAAABBBCCDDDDD en cuatro pares 5 pasos
La codificación por longitud de ráfaga convierte AAAAAABBBCCDDDDD en cuatro pares. Calcula la compresión y, a continuación, la condición exacta bajo la cual este esquema hace que un archivo sea más grande.
-
La codificación es la evidente: reemplazar cada ráfaga por el carácter y su longitud. Dieciséis caracteres se reducen a cuatro pares.
-
Dos números describen cualquier entrada de este esquema —su longitud y su número de ráfagas— y su proporción es la longitud media de ráfaga. Aquí es 4.
-
Ahora contemos de forma rigurosa. Cada par cuesta dos símbolos, un carácter y un recuento, de modo que la salida es 2R frente a una entrada de N. Nada más sobre los datos importa.
-
Así pues, el esquema sale ganando exactamente cuando 2R < N, lo que se despeja como una longitud media de ráfaga superior a 2. Aquí son 8 frente a 16 —una reducción exacta a la mitad— y la línea de veredicto del panel dice lo mismo con un solo símbolo.
-
Por debajo de ese umbral pierde, y con una longitud media de ráfaga de 1 pierde al máximo: cada carácter se convierte en un par, duplicando el archivo.
Respuesta
La herramienta muestra N = 16 y R = 4, una ráfaga media de 4 y un ahorro de 2×. La condición es lo que hay que recordar: RLE comprime si y solo si las ráfagas promedian más de dos, y es uno de los pocos esquemas de compresión cuyo punto de equilibrio es un único número que se puede comprobar a simple vista. Escribe ABCD en la casilla y observa cómo se duplica su tamaño. Eso no es un fallo: es la razón por la que RLE solo sobrevive donde las ráfagas están garantizadas por construcción: líneas de escaneo de fax, mapas de bits dispersos y las regiones planas de un JPEG tras la cuantización, nunca en texto general.
-
Ruta de aprendizaje
Compresión a mano
Referencias (3)
- Insight block 3 — PackBits, and the control byte that bounds its worst case: Adobe Systems, TIFF Revision 6.0, section 9 (PackBits Compression), 1992 — the format where Apple's variant became a standard compression mode.
- The run lengths themselves as the thing to be coded: S. W. Golomb, "Run-length encodings (Corresp.)." IEEE Transactions on Information Theory 12(3), 399–401, 1966.
- And the earlier paper that measured how long runs in real pictures actually are: J. Capon, "A probabilistic model for run-length coding of pictures." IRE Transactions on Information Theory 5(4), 157–163, 1959.