Estamos muy familiarizados con los archivos comprimidos, los formatos *.zip, *.rar y otros son habituales cuando enviamos ficheros a través del correo electrónico o realizamos alguna descarga desde internet. También estamos muy acostumbrados a los formatos *.jpg, *.mpg o *.mp3.
¿Cómo se consigue la reducción en el tamaño de un archivo? Existen dos tipos de compresión:
- Con perdida: Este tipo de compresión es característica de los archivos de imágenes, video o música. Si en lugar de ver la imagen exacta que hemos tomado con la cámara vemos una aproximación nuestro ojo no será capaz de detectar esa pérdida de algunos matices, pero rebajará considerablemente el tamaño del archivo. Es frecuente poder escoger la calidad de la imagen final, es decir estamos asumiendo la cantidad de calidad que estamos dispuestos a perder.Por esta razón los archivos *.jpg, *.mp3, *.mpg, entre otros, no reducen su tamaño si intentamos comprimirlos con herramientas tipo WinZip. Estos archivos ya están comprimidos.
- Sin pérdida: En otros tipos de archivos, pensemos en un archivo ejecutable, una hoja de cálculo, un texto o una base de datos, no nos podemos permitir las aproximaciones. El dato debe ser exactamente el mismo antes y después de la compresión.
En la compresión con pérdida la reducción de tamaño se consigue eliminando información que a priori no es tan perceptible para el ojo o el oído humanos. Por ejemplo al algoritmo JPG se basa en transformar los canales RGB (red, green, blue) de una imagen en canales de color y luminancia (YUV). Los canales de color se remuestrean asignando el mismo color a grupos más grandes de píxeles contiguos, mismo color por ejemplo para 4 píxeles en lugar de color por píxel. El ojo humano es más sensible al brillo que al color, por ello notaríamos mucho la pérdida de calidad si redujéramos la información del canal de brillo, así que rebajamos la información de los canales de color de forma que nuestro ojo “no se dé cuenta”. El algoritmo MP3, por su parte, elimina detalles de la música basándose en el enmascaramiento sonoro.
En la compresión de archivos sin pérdida se utilizan diferentes algoritmos: LZ77, LZW, LZSS, Codificación Huffman, por citar algunos.
Como ejemplo de como funcionan este tipo de algoritmos explicaré brevemente el algoritmo Huffman. Este puede ser utilizado tanto para compresión como para encriptación de datos. Fue creado en 1952 y se basa en asignar códigos binarios de menor longitud a los símbolos que tienen mayor frecuencia.
Supongamos la frase: Lo que quiero
Ahora contaremos las veces que aparece cada carácter y ordenaremos la lista empezando por los de menor número de apariciones:
L(1)->i(1)->r(1)->o(2)->” “(2)->q(2)->u(2)->e(2)
Para obtener el código creamos el árbol binario:
1.- Cada elemento se convertirá en un árbol con un único nodo
2.- Tomamos los dos árboles con menor peso y los unimos creando uno nuevo, la raíz de los dos nodos será la suma de sus pesos. A la arista izquierda le asignamos el valor 0 y a la derecha
3.- El árbol recién creado formará ahora parte de la lista de árboles a unir. Tomamos nuevamente los dos que tengan menor peso, los unimos y procedemos como en el paso 2.
Continuamos hasta que tengamos un único árbol.
Para conocer el código de cada carácter debemos recorrer el árbol desde la raíz hasta la hoja correspondiente anotando el valor de cada rama (0 o 1).
Para el ejemplo este es el resultado del árbol con el código correspondiente.
El mensaje del ejemplo se codificaría como:
0110 100 101 110 111 00 101 110 111 0111 00 010 100
L o q u e q u i e r o
Empaquetando en bytes:
01101001 01110111 00101110 11101110 01011000
Como puede verse el resultado obtenido son 4 bytes frente a los 13 del mensaje original.
La tabla de codificación debe incluirse en el archivo comprimido para que durante el proceso de descompresión pueda recorrerse nuevamente el árbol para generar el fichero original.