Programemos un juego en C (V): Compresión de datos, técnicas mas eficientes

---

Indice de entradas sobre programación de juegos en C

---

Las técnicas de evitar repeticiones son sencillas y rápidas, ahora veremos técnicas que consiguen mejor ratio de compresión, aumentando un poco la complejidad. Cuando programamos para máquinas con recursos muy limitados, hay que promediar las cosas, si una rutina ocupa 1Kb y nos ahorra 3Kb es eficiente, si ahorra 2Kb efectiva, pero si ahorras 1Kb no sirve de nada, lo que ganas lo gastas. Luego está el tema de la velocidad, cuando descomprimes empleas un tiempo, si cuesta bastante descomprimir puede que no te sirva, ya que en máquinas lentas pueden afectar a la velocidad del juego. Todo es una lucha para conseguir que todo funcione correctamente.

Las técnicas con diccionarios se basan en buscar no elementos repetidos, sino en combinaciones de elementos diversos repetidos, comprimen mejor, pero requieren de un diccionario en el que se almacena los cambios que se han efectuado, para poder restaurarlos. Si el diccionario es muy grande no ganamos mucho, siempre en el término medio está la virtud. El procedimiento mas sencillo es la codificación de bytes pares.

Veamos como comprimimos nuestra cadena de ejemplo "aaaaabbbbbbbbbbbbbccddddddd", no es el mejor ejemplo, pero si uno bueno para entender el mecanismo. Empezamos cambiando las mas evidentes, aunque podemos elegir otros pares, hay que buscar siempre los que mas se repitan, por tanto "aa" por A, "bb" por B, "cc" por C y "dd" por D, nos queda "AAaBBBBBBbCDDDd". Solo con esto tenemos casi el 50%.

Segunda vuelta, cambiamos "AA" por 1, "BB" por 2, "CD" por 3 y "DD" por 4. Ya vemos que no tienen que ser elementos repetidos los que usamos, sino parejas. Nos queda "1a222b34d".

Tercera vuelta, cambiamos "1a" por M, "22" por N, 2b por O, 34 por P, y nos queda "MNOPd".

Cuarta vuelta, cambiamos "MN" por X, "OP" por Y y nos queda "XYd".

Quinta vuelta, cambiamos "XY" por * y nos queda "*d".

Sexta vuelta, cambiamos "*d" por A y nos queda "A".

Vemos que este método puede reducir todo a una sola letra, a costa de que el diccionario que lo acompañe sea mas grande, siempre se aplica en orden inverso para que no haya problemas. En nuestro caso el diccionario sería de 16 entradas de 3 elementos cada una, ocupa por tanto 48 posiciones, y hay que ver en que punto podemos dejar de comprimir cuando ya no ganes nada en contra de lo que ocupa el diccionario. También podemos ver que no podemos usar los mismos elementos sin tener mucho cuidado, si A puede significar "*d" o "aa" según el nivel, no sería posible recuperar los datos si no están bien separados los niveles. En nuestro ejemplo el diccionario ocupa mas que la cadena, pero si la cadena de origen fuera de 1.000 posiciones, y lo dejamos en 100, la compresión sería muy eficiente. Luego viene el tema de que hay que recorrer la cadena el número de entradas en el diccionario para descomprimir, o añadir información de los niveles para acelerar las pasadas, lo que como siempre es compromiso entre ganancia de espacio y velocidad. El diccionario resultante sería este

(6) A = *d
(5) * = XY
(4) Y = OP
(4) X = MN
(3) P = 34
(3) O = 2b
(3) N = 22
(3) M = 1a
(2) 4 = DD
(2) 3 = CD
(2) 2 = BB
(2) 1 = AA
(1) D = dd
(1) C = cc
(1) B = bb
(1) A = aa


Este tipo de compresión es sencillo de usar, pero requiere estudiar bien los datos de origen para maximizar el resultado. Para mejorarlo, podemos usar una variante en la que una combinación sea de mas de dos elementos. Veamos ejemplos con nuestros niveles. Los elementos que usamos en cada nivel son " ", "#",  "$", "@", ".", "*" y "|" son siete elementos. Podemos plantear las posibles combinaciones de los 7 elementos tomados de dos en dos nos da 42 posibilidades. Con esto tendríamos reducido nuestro tamaño a la mitad, añadiendo un diccionario de 126 caracteres. Otra técnica, en lugar de tantas combinaciones, vamos a usar otros niveles,  agruparemos los elementos repetidos de ocho en ocho, de cuatro en cuatro, luego de dos en dos, si lo hacemos en ese orden nunca hay problema para comprimir y luego descomprimir, y añado combinaciones muy usadas:

Z = "#|", A = "        ", B = "    ", C = "  ", D = "########", E = "####", F = "##", G = "........", H = "....", I = "..", J = ".#", K = " #", L = "# "

Con esto tenemos reducido a 6.030 caracteres. Podemos hacer una segunda vuelta, una tercera, y buscando combinaciones se puede reducir al nivel que deseemos. Por ejemplo podemos usar combinaciones como 1 = "C#", 2 = "#I", 3 = "$K", 4 = "CK", 5 = "#K", 6 = "#C", 7 = "F#", 8 = "BK", 9 = "B#", 0 = "$ ". Con estos dos niveles, que tampoco he estudiado demasiado, el resultado es que ocupa 5.270 caracteres, vamos ganando espacio. Seguro que si se estudian mejor las combinaciones de primer nivel ganaremos bastante espacio mas, eso es lo que hacen los programas de compresión, cuentan primero las combinaciones para encontrar las más usadas.

BEZ
B6 Z
9$CZ
CF6$#Z
1C00Z
F5 FKC E#Z
#4 F E6IZ
L$C$ACIZ
ELF5@FCIZ
9B DZ
BE7

D7Z
21B FZ
2CL$C$CZ
21$ECZ
2B@ FCZ
21KC3Z
EF F00Z
CL$C000Z
19B Z
CDE

Esto realmente va en línea, quedando en dos cadenas así, y seguramente si se distribuye en línea se ganará mejor compresión con las combinaciones "#| " y "#|#" que son muy numerosas.

BEZB6 Z9$CZCF6$#Z1C00ZF5 FKC E#Z#4 F E6IZL$C$ACIZELF5@FCIZ9B DZBE7

D7Z21B FZ2CL$C$CZ21$ECZ2B@ FCZ21KC3ZEF F00ZCL$C000Z19B ZCDE

En la siguiente entrada veremos el tercer sistema usual de compresión sencillo de usar, para el que necesitamos un poco mas de cálculos y el uso de las bases de numeración.