El algoritmo de compresión utilizado para los gráficos de La Carretera es un algoritmo muy sencillo, el más sencillo de todos, y por lo tanto falla mucho en determinadas circunstancias.
Éste algoritmo es muy antiguo, y es utilizado en las máquinas de fax y en el formato de compresión de mapas de bit bitonales TIFF. Dicho algoritmo es conocido como CCITT (Comité Consultivo Internacional Telegráfico y Telefónico) GRUPO 3, y se basa en que en una cadena de datos, los datos que se repiten consecutivamente pueden ser sustituidos por el número de veces que se repiten, seguido del dato en sí. Veamos, por ejemplo, la siguiente cadena de datos en hexadecimal.
B0 B0 B0 B0 B0 B0 B0 B0 B0 B0 55 55 55 55 E9 E9 E9 E9 E9 E9 E9 E9 00 00 00
Podemos comprobar que el dato B0 se repite diez veces, el dato 55 cuatro veces, E9 ocho veces y el 00 tres veces, la cadena entera consta pues de un total de veinticinco bytes. El algoritmo de compresión CCITT 3 transformaría ésta cadena en ésta otra.
0A B0 04 55 08 E9 03 00
Ahora la cadena, una vez comprimida, sólo consta de ocho bytes. ¡De veinticinco bytes a sólo ocho! No está mal, ¿Verdad?
Pero hay un pequeño problema, ¿qué pasa cuando en la cadena de datos éstos no se repiten o no se repiten consecutivamente? Veamos ésta otra cadena.
A9 00 8D 20 D0 8D 21 D0 A2 25
Ahora el algoritmo de compresión transformaría ésta cadena en ésta otra.
01 A9 01 00 01 8D 01 20 01 D0 01 8D 01 21 01 D0 01 A2 01 25
Como se puede ver, el algoritmo a "inflado" la cadena al doble de bytes que tenía la original.
Por regla general, éste método de compresión funciona bastante bien cuando hay más de dos bytes consecutivos repetidos, habiendo compresión nula cuando sólamente hay dos bytes consecutivos repetidos, y siendo nefasta, como acabamos de ver, cuando no hay bytes que se repitan consecutivamente.
NOTA: El algoritmo de compresión del CCITT GRUPO 3 es el mismo que el RLE o Run-length encoding, sólo que el Comité Consultivo Internacional Telegráfico y Telefónico lo incluyó dentro del grupo 3 de sus estándares de transmisión de datos para fax. ¡Se nota que trabajo en las telecomunicaciones!
Proximamente: La subrutina de descompresión de pantallas de La Carretera al desnudo.
