Compresión

  • Pere Cruells

  • Germán Sáez

PID_00206070
Ninguna parte de esta publicación, incluido el diseño general y la cubierta, puede ser copiada, reproducida, almacenada o transmitida de ninguna forma, ni por ningún medio, sea éste eléctrico, químico, mecánico, óptico, grabación, fotocopia, o cualquier otro, sin la previa autorización escrita de los titulares del copyright.

1.Introducción y método Huffman

1.1.Introducción

Actualmente, la cantidad de información que almacenamos y que transmitimos se está incrementando a pasos agigantados. Los sistemas mutimedia incluyen, cada vez más, imágenes, sonido, vídeos, distintos tipos de animaciones, videoconferencias, etc., que ocupan gran cantidad de memoria que se debe almacenar, procesar o transmitir. Estas grandes cantidades de información repercuten en el coste con incrementos tanto en el ámbito económico como de tiempo. Cuando la distribución de esta información es en línea, la transmisión de grandes volúmenes de información aumenta el tiempo de conexión, con lo que crece el coste de conexión, aumenta el tiempo de ocupación de canales de transmisión por parte del usuario y aumenta la probabilidad de que se produzcan errores en la transmisión. En definitiva, se reduce la calidad y aumenta el coste de la transmisión de datos.
Una forma de solucionar este problema es reduciendo la cantidad de memoria necesaria para almacenar la misma cantidad de información. Una vez se codifica la información en tiras de bits, se pueden comprimir, es decir, se reescribe la misma información usando un número menor de bits. Este proceso se denomina compresión. Podremos comprimir datos, imágenes, sonido, etc. Este proceso tiene su coste, pero el resultado es positivo en el sentido de que es mejor comprimir, transmitir y descomprimir, que simplemente transmitir sin haber comprimido.
La idea de la compresión es almacenar una cierta información en un espacio menor al que ocupa inicialmente. El principal cometido de la compresión es, por tanto, eliminar cualquier tipo de redundancia presente en la información, sea ésta una imagen, un sonido o un fichero de texto. En cierto modo, la compresión va en sentido contrario a la codificación. En la codificación nos ocupábamos de añadir cierta redundancia para asegurar así que después de los procesos de almacenamiento y/o transmisión, la información recuperada es la misma que la inicial, por medio de un sistema de detección y corrección de errores.
Existen muchos métodos de compresión, y pueden presentar muchas diferencias; en ocsiones, sólo tienen en común su objetivo de comprimir datos. Los métodos de compresión varían según las aplicaciones en las que tengan que usarse dependiendo de la velocidad de compresión y descompresión del método y de la pérdida de información que la compresión pueda provocar. En general, los métodos de compresión se pueden dividir en dos grupos: los métodos sin pérdidas y los métodos con pérdidas. Un método de compresión sin pérdidas permite recuperar exactamente toda la información original. Los métodos sin pérdidas se usan, en general, para bases de datos, procesadores de texto, hojas de cálculo, etc., en los que la recuperación exacta de los datos almacenados es esencial. Los métodos con pérdidas conllevan una cierta pérdida de precisión, pero a cambio se incrementa la compresión de forma sustancial. Este tipo de compresión acostumbra a usarse para imágenes y para voz, ya que en estos casos, la percepción visual y auditiva puede tolerar pérdidas casi inapreciables para nuestros ojos u oídos. La compresión con pérdida puede ajustarse a distintas calidades de almacenamiento, de forma que se gana calidad a cambio de una menor eficacia en la compresión.
El primer método de compresión de datos se conoce con el nombre de codificación de Shannon-Fano. Shanon y Fano desarrollaron un algortimo de codificación basándose en la idea de que en un mensaje aparecen partes que se repiten más que otras. El método asigna una codificación más corta a los fragmentos del mensaje que se repiten más veces, mientras que los trozos que menos aparezcan tendrán asignada una codificación más larga. Con esta idea tan simple, se consigue una buena compresión respecto a una codificación que asigne la misma cantidad de bits a cada fragmento del mensaje. Huffman mejoró rápidamente el método de Shannon-Fano, basándose en una idea similiar. En los últimos años, la codificación de Huffman ha sido sustituida por la codificación aritmética y los métodos basados en diccionario.
En este módulo veremos una idea general de los diferentes métodos de compresión de datos.
Sorprendentemente, es muy complicado conseguir una buena compresión de audio de forma efectiva. Compañías como Philips y Sony han invertido grandes cantidades de dinero para desarrollar algoritmos de compresión de audio.
Algunos programas o aplicaciones llevan su propio sistema de compresión incorporado, de forma que, al guardar los archivos, lo hacen de forma comprimida.

1.2.Método Huffman

Vamos a presentar uno de los primeros métodos de compresión sin pérdida de información: el método Huffman. Éste es un método estadístico ya que utiliza las frecuencias de repetición de caracteres o niveles de gris que se quieren comprimir. Hagamos una introducción a su funcionamiento con un ejemplo. Supongamos que tenemos que almacenar la siguiente imagen en blanco y negro:
m7e1_rec1.gif
Si asignamos a cada nivel de gris una codificación en binario, para poderlo almacenar por los sistemas usuales necesitaremos dos bits, ya que el número de diferentes niveles de gris es 4. Así, si asignamos a cada nivel de gris los bits:
m7e1_rec2.gif
Con esta codificación, la imagen se puede almacenar utilizando la tira de 32 bits:
00 01 10 11 11 00 01 10 01 01 00 01 01 01 01 00
que corresponde con la codificación por filas de los niveles de gris. Fácilmente, se puede utilizar esta tira de bits para reconstruir la imagen, una vez establecida la asignación entre nivel de gris y su codificación, simplemente traduciendo cada par de bits como un nivel de gris.
Si observamos el número de apariciones de los niveles de gris en nuestra imagen, podemos ver que los dos niveles de gris más claros aparecen pocas veces, mientras que el segundo nivel de gris aparece en muchas más ocasiones. La idea de los códigos de Huffman consiste en asignar una codificación más larga a los niveles de gris menos frecuentes, y una codificación más corta a los más frecuentes. Con ello se conseguirá que el número de bits necesario para almacenar la imagen sea menor. Calculemos la frecuencia de aparición de cada uno de los niveles de gris:
m7e1_rec3.gif
Así, podemos afirmar que, en términos absolutos, el primer nivel de gris aparece un , el segundo nivel de gris aparece , y el tercer y cuarto nivel de gris aparecen cada uno. A veces también se expresa en forma de probabilidad; en este caso, se dice que la probabilidad de aparición del primer nivel de gris es 0,25, la del segundo es 0,5 y la del tercero y cuarto, 0,125 cada uno.
Supongamos que utilizamos la siguiente codificación de acuerdo con la anterior idea expresada de asignar una codificación más larga al nivel de gris menos frecuente y una codificación más corta al más frecuente:
m7e1_rec7.gif
Entonces, con esta codificación la imagen se puede almacenar como:
10 0 110 111 111 10 0 110 0 0 10 0 0 0 0 10
Esta codificación nos proporciona un almacenamiento más económico, ya que utiliza 28 bits, en comparación con los 32 de la codificación anterior. Por tanto, nos hemos ahorrado 4 bits, es decir, un de bits. Ésta es la llamada tasa de compresión.
Lo que no parece tan fácil a primera vista es la recuperación de la imagen a partir de la codificación, ya que nosotros leeremos la tira de bits (sin separaciones):
10 0 110 111 111 10 0 110 0 0 10 0 0 0 0 10
Sin embargo, no existe tal problema, ya que esta codificación elegida está astutamente construida para que sea fácil recuperar la imagen. Veámoslo: si empezamos a leer la tira de bits, vemos que comienza por 1, por lo que el primer píxel puede ser tres de los niveles de gris, pero el siguiente bit es un 0 para el que sólo hay un nivel de gris con esta codificación. Por tanto, sabemos que el primer nivel de gris es el que hemos codificado como 10. Continuemos leyendo la tira de bits: el siguiente bit es un 0; sabemos que sólo hay un nivel de gris cuya codificación empiece por 0, es decir, que tenemos por ahora 10 0. El siguiente bit es 1, y para elegir entre los niveles de gris cuya codificación empieza por 1 miramos el siguiente bit que es un 1, lo cual nos descarta uno de los tres niveles de gris. Por tanto, habrá que leer un bit más: un 0, que ya determina completamente el nivel de gris. Así, ya tenemos los siguientes niveles de gris: 10 0 110. Podríamos seguir con la decodificación y, así, recuperaríamos la imagen.
Recuperad la porción de imagen 0010111 con la siguiente codificación:
m7e1_rec9.gif
m7e1_rec10.gif
m7e1_rec11.gif
m7e1_rec12.gif
m7e1_rec13.gif
Actividad
Codificad la imagen:
m7e1_rec14.gif
Siguiendo el mismo proceso que se ha utilizado en el ejemplo introductorio, es decir, calculad las frecuencias relativas de cada nivel de gris, asignad la codificación que se ha utilizado en el ejemplo (los códigos 0, 10, 110, 111 para los niveles de gris de más frecuentes a menos) para obtener la codificación Huffman de la imagen y evaluar el número de bits ahorrados (y por tanto, la tasa de compresión).
Por tanto, el método Huffman de compresión consiste en calcular las frecuencias de aparición de cada uno de los niveles de gris y asignar una codificación en bits que asocie un menor número de bits al nivel de gris más frecuente y un número de bits mayor al nivel de gris menos frecuente. De todos modos, la asignación de bits tendrá que hacerse de forma que la decodificación sea factible. Para ello se sigue el algoritmo de codificación de Huffman, que consiste en lo siguiente: en primer lugar, se calcula la frecuencia de aparición de cada nivel de gris para determinar así las probabilidades de aparición de cada uno en la imagen. En nuestro primer ejemplo, habíamos obtenido las probabilidades:
m7e1_rec15.gif
En segundo lugar, asignaremos la codificación utilizando un diagrama en forma de árbol auxiliar. Veamos qué es un árbol y cómo se construye con el mismo ejemplo que estábamos exponiendo. En primer lugar, se seleccionan las dos probabilidades menores: 0,125 y 0,125. Se sustituyen en la lista de probabilidades por la suma de ambas, es decir, la nueva lista de probabilidades es: 0,5 0,25 0,25, y se construye el primer paso del diagrama en forma de árbol.
m7e1_rec16.gif
Decimos que hemos puesto en los nodos las dos probabilidades y que confluyen en un nodo en el que figura la suma 0,25 de las dos probabilidades. Ahora procedemos de la misma forma con la nueva lista de probabilidades: 0,5 0,25 0,25. Las dos probabilidades más bajas son 0,25 y 0,25 que sumadas dan 0,5. De la misma forma, ampliamos el árbol fabricando un nodo nuevo para la suma de probabilidades y lo conectamos con las dos probabilidades que hemos sumado:
m7e1_rec17.gif
Ahora nuestra lista de probabilidades se reduce a 0,5 y 0,5, por lo que las dos probabilidades más bajas son estas dos que suman 1. El árbol queda:
m7e1_rec18.gif
Se puede observar que los nodos de los que no cuelga ningún otro nodo son precisamente las probabilidades de los niveles de gris originales. Para determinar el código Huffman, ahora sólo falta ir asignando a cada bifurcación del árbol nodo un 0 o un 1 comenzando desde el primer nodo, acumulando los bits de cada bifurcación como se puede ver en el diagrama:
m7e1_rec19.gif
Así, hemos llegado a la codificación que habíamos utilizado.
Los códigos Huffman fueron descubiertos por David A. Huffman, un ingeniero eléctrico de la Ohio State University, en 1952 mientras trabajaba en el MIT. Su método de compresión se utiliza en muchos campos, entre éstos módems, faxes y televisión de alta definición.
m7e1_rec20.gif
Hagamos ahora otro ejemplo con el proceso completo en el que se muestra que no sólo se utiliza el código Huffman para comprimir imágenes.
Comprimamos ahora el texto: IMAGEN DIGITAL. En primer lugar, calculemos las frecuencias de cada carácter y la probabilidad asociada:

Carácter

I

M

A

G

E

N

_

D

T

L

Frecuencia

3

1

2

2

1

1

1

1

1

1

Probabilidad

3/14

1/14

2/14

2/14

1/14

1/14

1/14

1/14

1/14

1/14

Carácter

I

M

A

G

E

N

_

D

T

L

Frecuencia

3

1

2

2

1

1

1

1

1

1

Probabilidad

3/14

1/14

2/14

2/14

1/14

1/14

1/14

1/14

1/14

1/14

Codificación

00

011

100

010

1010

1011

1100

1101

1110

1111
En segundo lugar, ordenemos todos los nodos en sus estado inicial para construir el árbol:
m7e1_rec21.gif
Ahora seleccionamos dos de los nodos de menor probabilidad y los unimos con un nodo con suma de las dos probabilidades:
m7e1_rec22.gif
Elegimos dos de los nodos de menor probabilidad y procedemos como en el paso anterior:
m7e1_rec23.gif
Volvemos a repetir el proceso:
m7e1_rec24.gif
Nos fijamos que, en este caso, las probabilidades más bajas son 1/14 y 2/14. De entre las diferentes posibilidades que tenemos para construir el siguiente nodo, elegimos una:
m7e1_rec25.gif
En este paso, las dos probabilidades más bajas son 2/14 y 2/14:
m7e1_rec26.gif
Nuevamente, repetimos el proceso:
m7e1_rec27.gif
En este penúltimo paso, las dos probabilidades más bajas son 4/14 y 4/14:
m7e1_rec28.gif
Y en el último paso, si todo se ha hecho correctamente la suma de las probabilidades tiene que dar 1:
m7e1_rec29.gif
Ahora se aplica el último paso del algoritmo para determinar el código Huffman, es decir, partiendo de la raíz del árbol se asigna 0 a una rama y 1 a la otra. En este proceso, se va descendiendo y acumulando el nuevo bit en la tira de bits que se tiene ya construida:
m7e1_rec30.gif
Por tanto, obtenemos la codificación:
La compresión quedará: 00 011 100 010 1010 1011 1100 1101 00 010 00 1110 100 1111.
El número de bits que se han utilizado es 45. Se observa que si no hubiésemos comprimido, habríamos necesitado numerar los diferentes diez símbolos: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9; por tanto, en base 2 hubiésemos necesitado 4 bits para cada número (que representa un carácter), y puesto que en total son catorce caracteres, nos hubiesen quedado 14 · 4 = 56 bits. Nos hemos ahorrado 11 bits, que representan un de tasa de compresión.
Uno de los inconvenientes de la implementación práctica del método Huffman es que para cada compresión se obtiene un conjunto de probabilidades diferente para cada carácter, nivel de gris, etc. y por tanto, una codificación distinta para cada compresión que realicemos. En este caso, para cada compresión es necesario adjuntar la tabla de codificación obtenida. Si se quiere estandarizar el proceso, es posible utilizar las frecuencias de aparición de las letras en el idioma que estemos utilizando, y usar siempre una misma codificación.

2.Algunos métodos de compresión

2.1.Compresión diferencial

Este método de compresión se basa en el hecho de que en una imagen, la diferencia de tonalidad de gris de un píxel al siguiente es probablemente pequeña. Es decir, el tono de gris de un píxel comparado con el siguiente será bastante parecido; de hecho, sólo cambia de forma sustancial en el caso de pasar por un contorno de la imagen. Así, para almacenar una imagen, bastará con almacenar el primer píxel y, a partir de ahí, en lugar de almacenar píxel a píxel, se almacena la diferencia de cada píxel con el anterior.
Supongamos que tenemos 256 tonos de gris distintos. En principio, para almacenar el tono de gris de cada píxel, deberemos almacenar una tira de bits que represente uno de estos 256 tonos de gris. Para ello necesitaremos 8 bits, ya que los códigos de gris en sistema decimal serán números comprendidos entre 0 y 255, y en sistema binario serán números comprendidos entre 00000000 y 11111111. Así, cada tira de 8 bits representa un número en sistema decimal entre 0 y 255. Si en lugar de almacenar 8 bits para cada píxel, almacenamos sólo el primer píxel, y a partir de ahí almacenamos la diferencia del número correspondiente entre el tono de gris de un píxel y el anterior, podremos reducir el número de bits necesario para todos los píxeles a partir del segundo. Si realmente tenemos poca diferencia en el tono de gris de un píxel a otro, las diferencias de números que debemos almacenar serán pequeñas, de forma que no será necesario utilizar 8 bits para cada píxel. Si, por ejemplo, podemos almacenar estas diferencias usando sólo 4 bits, habremos reducido la cantidad de memoria utilizada en casi un 50%.
Puesto que este método se basa en la baja diferencia entre los tonos de gris de píxeles cercanos, no podemos hacer un barrido en filas para el almacenamiento de la imagen. Esto podría comportar problemas, ya que el píxel de más a la derecha de una fila no tiene por qué tener un tono cercano al píxel de más a la izquierda de la fila siguiente. Para evitar esto, lo que haremos será almacenar la información de cada píxel con un barrido por filas en zigzag.
Ejemplo 1
Tenemos una imagen de 30 × 70 píxeles en 256 tonos de gris. ¿Cuántos bits son necesarios para almacenar esta imagen sin ningún método de compresión? Si utilizamos el método de compresión diferencial reduciendo de 8 a 4 bits, ¿cuántos píxeles utilizaremos para esta misma imagen? ¿Cuál es la tasa de compresión?
Esta imagen tiene 30 × 70 = 2.100 píxeles; si cada píxel usa 8 bits, esto significa que necesitamos 16.800 bits para su almacenamiento. Si comprimimos esta imagen con un método diferencial, dejaremos que el primer píxel ocupe la misma cantidad de memoria: 8 bits, mientras que los 2.099 píxeles restantes utilizarán la mitad. De esta forma, en total se necesitarán 8 + 2.099 × 4 = 8.404 bits para almacenar la imagen. Hemos utilizado 16.800 – 8.404 = 8.396 píxeles menos, esto significa una tasa de compresión de
Ejemplo 2
Supongamos que tenemos 16 tonos distintos de gris, que codificaremos como:
50003_m7_01.jpg
Queremos almacenar una imagen de 3 × 4 píxeles, de forma que sus tonos de gris serían, en sistema decimal:
50003_m7_02.jpg
Para almacenar esta imagen en dígitos binarios, deberemos usar 4 bits para cada número, de forma que usaremos 3 × 4 × 4 = 48 bits.
Vamos a comprimirla guardando el primer píxel y, a partir de éste, la diferencia con el anterior, haciendo un barrido en zigzag.
La información que deberemos guardar en sistema decimal sería:
50003_m7_03.jpg
Para almacenar esta información usaremos 4 bits para el primer píxel, igual que antes, pero reduciremos el número de bits para los 11 píxeles restantes. Tenemos que codificar números entre –4 y 3, tenemos un rango de ocho números que pueden ser codificados con sólo 3 bits. Así, usaremos 4 para el primer píxel, más 3 bits para los 11 restantes: 4 + 11 × 3 = 37 bits. Con sólo 37 bits almacenaremos esta imagen.
La tasa de compresión para este ejemplo será de
Actividad
Ejercicio 1
Queremos almacenar una imagen monocroma de 32 × 120 píxeles usando una escala de grises de 256 tonos. ¿Cuántos bits serán necesarios si no se comprime esta imagen? Aplicando una compresión diferencial, obtenemos como diferencias una serie de números comprendidos entre –25 y 36. ¿Cuántos bits ocupará esta misma imagen una vez comprimida? ¿Cuál será la tasa de compresión?
Ejercicio 2
Calculad la codificación en sistema decimal de una imagen monocroma en 256 tonos de gris de 6 × 5 píxeles una vez comprimida por el método diferencial, suponiendo que la tabla siguiente representa el tono de gris para cada píxel. Calculad cuántos bits de memoria serían necesarios para almacenar esta imagen antes y después de comprimirla.
50003_m7_04.jpg
Tal como hemos explicado, este método, es un método sin pérdidas, ya que adecuamos el número de bits para almacenar las diferencias al rango de las diferencias que se obtengan. Al ser un método para compresión de imágenes, se puede aceptar que tenga pérdidas imponiendo un rango menor en las diferencias. Así, en el momento de comprimir una imagen por este método, podemos imponer el número de bits para almacenar las diferencias, tanto si caben como si no, obteniendo pérdidas de información para los píxeles que no almacenáramos correctamente.

2.2.Compresión RLL (Run Length Limited)

El método de compresión Run Length Limited, conocido por RLL, es un método relativamente sencillo. Se basa en contar cuántos ceros hay entre cada dos unos. Explicaremos este método a partir del siguiente ejemplo.
Consideramos la siguiente tira de 50 bits:
10010001000010001000010001001000100001000001110001.
Contamos el número de ceros entre unos. En este caso sería:
0 2 3 4 3 4 3 2 3 4 5 0 0 3.
Guardamos esta información en sistema binario usando para cada número una tira de 3 bits:
000 010 011 100 011 100 011 010 011 100 101 000 000 011.
Hemos usado 42 bits para almacenar exactamente la misma información. La tasa de compresión en este caso será de
Este método, actualmente en desuso, se usaba para grabar información en discos duros. El ejemplo que hemos expuesto consiste en un ejemplo sin pérdidas, pero en general este método puede acarrear pérdidas si tenemos que almacenar algún número grande. Es decir, si en la tira que hay que comprimir aparece una tira de ceros seguida que sea relativamente grande. Veamos un ejemplo en el que se producen pérdidas.
Tenemos la siguiente tira de 50 bits:
00100000010011000100100000000000001011000010100101.
Queremos comprimirla con el método RLL y disponemos de 3 bits para almacenar cada número obtenido.
Contando el número de ceros que hay entre cada dos unos, tenemos:
2 6 2 0 3 2 13 1 0 4 1 2 1
Para almacenar estos números de sistema decimal a sistema binario, tenemos suficiente con 3 bits para todos excepto para el 13. Aquí tendremos una pérdida de información. Para que la pérdida no sea muy grave, una estratégia posible es decomponer el 13 en la suma de dos números, por ejemplo 7 + 6. Puesto que al descomprimir estos dos números insertaremos un 1, deberemos restar un 0 a uno de los dos, por lo que finalmente sustituimos el 13 por dos veces el 6.
010 110 010 000 011 010 110 110 001 000 100 001 010 001
Para descomprimir esta tira de bits, primero los pasaremos a sistema decimal, agrupando los bits de 3 en 3:
2 6 2 0 3 2 6 6 1 0 4 1 2 1
Y ahora escribiremos tiras de unos con el número correspondiente de ceros intercalados:
00100000010011000100100000010000001011000010100101
Observad que hemos obtenido la tira inicial con sólo una diferencia: ha aparecido un 1 en el puesto 28, cuando en la tira original había un 0. Hemos sufrido pérdida de información.
Actividad
Ejercicio 1
Comprimid por el método RLL las siguientes tiras de bits, usando siempre 3 bits para almacenar cada uno de los resultados del cómputo de ceros. Una vez comprimido, calculad la tasa de compresión y evaluad las posibles pérdidas de información.
a) 1001000100001000001000000100000001000000001101000011100010000100
b) 1001110100000000001001000100000000000000000100000010100000000111
Ejercicio 2
Descomprimid las siguientes tiras de bits, suponiendo que se han comprimido con el método RLL y que cada 3 bits corresponden al número de ceros entre cada 1. Calculad la tasa de compresión en cada caso. En el apartado a, la tira de bits original es de 64 bits de longitud, y en el apartado b, la tira de bits original es de 43 bits de longitud.
a) 010111100101111000110011110000000001101001010
b) 110110110001111000110011

2.3.Compresión aritmética

La compresión aritmética se basa en buscar un número decimal comprendido entre 0 y 1 siguiendo una serie de instrucciones que dependen del número de veces que se repite un carácter en la secuencia que queramos comprimir. Este número se escoge después de haber creado una sucesión de intervalos, cada vez menores, partiendo siempre del intervalo que va del 0 al 1. Cuanto más largo sea el mensaje que hay que comprimir, menor es el intervalo final, de forma que el número decimal que escogeremos para finalizar el proceso tendrá más cifras decimales significativas.
Pongamos un ejemplo. Supongamos que queremos comprimir la expresión XXY. De los tres caracteres, tenemos dos veces X, y una sola vez Y. Así, la frecuencia relativa de aparición de cada carácter es:
m7e2_rec4.gif
m7e2_rec4a.gif
El algoritmo se basa en dividir el intervalo [0,1] en dos porciones de longitud las dos probabilidades de los dos símbolos:
m7e2_rec5.gif
Como se puede observar, haremos la división colocando primero la probabilidad mayor y después la menor. Una vez tenemos dividido el intervalo, codificamos el primer carácter eligiendo el subintervalo del símbolo que hay que comprimir. En nuestro caso es X, por lo que elegimos el subintervalo [0,0.666]. Para codificar el siguiente carácter, procedemos como con el primero, sólo que esta vez la división del intervalo se hace en el intervalo seleccionado:
m7e2_rec6.gif
Para dividir el intervalo en 2/3 partes y 1/3 parte, hemos multiplicado su longitud por 2/3. Conviene no escatimar cifras decimales. Ahora vamos a elegir el subintervalo que corresponde al segundo carácter, que es el que estamos codificando: [0,0.444]. Por último para codificar el carácter Y, volveremos a dividir el último intervalo y elegiremos el subintervalo de la derecha:
m7e2_rec7.gif
Es decir, nos quedaremos con el intervalo [0.296,0.444]. Ahora, para dar la codificación, simplemente hay que dar un número de este subintervalo, por ejemplo 0,2967. La última cuestión técnica de cómo dar el número decimal no la detallamos, pero hay que tener en cuenta que debemos darlo en base dos y de forma que utilice el mínimo número de bits posible.
La descompresión se hace de una manera muy parecida, una vez conocidas las probabilidades de cada carácter. Veámoslo con una tira de tres caracteres entre X e Y con las probabilidades anteriores y comprimido como 0,5.
Por la situación del número 0,5 en la primera subdivisión, deducimos que el primer carácter es X:
m7e2_rec8.gif
De la segunda división (con el primer subintervalo), deducimos que el segundo carácter es Y:
m7e2_rec9.gif
Procedemos a hacer la última subdivisión, en este caso del subintervalo de la derecha:
m7e2_rec10.gif
Puesto que el número 0,5 queda en el subintervalo de la izquierda, el carácter correspondiente es X, por lo que la descompresión de 0,5 nos da XYX.
Hagamos una breve descripción de cómo se han obtenido los extremos del intervalo [0.592,0.666]: en primer lugar, se ha calculado la longitud del intervalo que hay que subdividir como 0,666 – 0,444 = 0,222. A continuación, se calculan las dos terceras partes de esta longitud: . Finalmente, se suma esta longitud al extremo de la izquierda: 0,148 + 0,444 = 0,592.

2.4.LZW

m7e2_rec12.gif
El método de diccionario más utilizado es LZW y todas sus variantes. Estos métodos partieron de los trabajos de los matemáticos Abraham Lempel y Jakob Ziv de los años 1977 y 1978, junto con modificaciones propuestas por Terry A. Welch en el año 1984. Con este método se implementan los compresores más conocidos, como pueden ser el PKZIP. A continuación describiremos la versión más sencilla de este método.
La idea principal es construir un diccionario en el que se guarden todas las cadenas de caracteres que aparecen en la información que hay que comprimir y almacenar como información comprimida los índices del diccionario que han aparecido.
Para fijar ideas, supongamos que estamos comprimiendo un texto. Este diccionario tendrá en las primeras 256 primeras entradas los caracteres ASCII y, a partir de esta posición, almacenaremos las cadenas de caracteres de longitud mayor que 2 que aparezcan en el texto.
En primer lugar, supongamos que tenemos un diccionario formado por los 256 caracteres ASCII numerados del 0 al 255, y tenemos el diccionario en blanco a partir de la posición 256.
Para comprimir una entrada llamada texto, el algoritmo procede según el siguiente esquema:
    tira:='vacía'
    repetir
                carácter:=leer un carácter de texto
                si tira+carácter está en el diccionario
                            entonces tira:=tira+carácter
                            sino escribir el código de tira en resultado_compresión
                                        añadir tira+carácter al diccionario
                                        tira:=carácter
                fin_si
    fin_repetir
    escribir el código de tira en la salida
En primer lugar, fijémonos en que este algoritmo va añadiendo al diccionario nuevas entradas, va manteniendo las dos variables carácter y tira, y produce una salida que es la resultado_compresión.
Veamos la evolución con un ejemplo: supongamos que tenemos que comprimir la entrada texto= /LEO/LEES/LEE formada por 13 caracteres ASCII (hemos utilizado "/" como carácter para separar palabras).
Iremos apuntando en cada momento el valor de cada variable. Al inicio del algoritmo, tenemos que inicializar la variable tira con 'vacía'. No importa qué valor tengan las otras variables, pero supondremos que también están vacías:
tira
=, carácter=, resultado_compresión=,
diccionario
= .... 0...255 caracteres ASCII
Ya hemos hecho la inicialización y ahora entramos en el bucle repetir. Leemos el primer carácter de texto y tenemos carácter=/. Nos preguntamos si tira+carácter=/ aparece como una entrada del diccionario. Sabemos que este carácter es un carácter ASCII y, por tanto, hay que hacer la operación tira:=tira+carácter, que da como resultado tira:=/. Así, tenemos por ahora:
tira
=/, carácter=/, resultado_compresión=,
diccionario
= .... 0...255 caracteres ASCII
Volvemos al inicio del bucle y leemos el segundo carácter de texto y tenemos carácter=L. Nos preguntamos si tira+carácter=/L está como una entrada del diccionario. Puesto que la respuesta es que no, debemos escribir el código de tira en la salida, con lo que tenemos resultado_compresión=/. Además, debemos añadir tira+carácter=/L al diccionario y colocar en tira el valor de carácter. Así, tenemos por ahora:
tira
=L, carácter=L, resultado_compresión=/,
diccionario
= .... 0...255 caracteres ASCII
                256 /L
Verdaderamente, pondríamos el carácter ASCII en lugar de "/", pero para clarificar la evolución del algoritmo escribiremos el propio carácter.
Volvemos al inicio del bucle y leemos el tercer carácter de texto y tenemos carácter=E. Nos preguntamos si tira+carácter=LE aparece como una entrada del diccionario. Puesto que la respuesta es que no, debemos escribir el código de tira en la salida, con lo que tenemos resultado_compresión=/L. Además, debemos añadir tira+carácter=LE al diccionario y colocar en tira el valor de carácter. Así, tenemos por ahora:
tira
=E, carácter=E, resultado_compresión=/L,
diccionario
= .... 0...255 caracteres ASCII
                256 /L
                257 LE
Volvemos a empezar una nueva iteración: leemos el cuarto carácter de texto y tenemos carácter=O. Nos preguntamos si tira+carácter=EO aparece como una entrada del diccionario. Puesto que la respuesta es que no, debemos escribir el código de tira en la salida, con lo que tenemos resultado_compresión=/LE. Además, debemos añadir tira+carácter=EO al diccionario y colocar en tira el valor de carácter. Así, tenemos por ahora:
tira
=O, carácter=O, resultado_compresión=/LE,
diccionario
= .... 0...255 caracteres ASCII
                256 /L
                257 LE
                258 EO
Siguiente iteración: leemos el quinto carácter de texto y tenemos carácter=/. Nos preguntamos si tira+carácter=O/ aparece como una entrada del diccionario. Puesto que la respuesta es que no, debemos escribir el código de tira en la salida, con lo que tenemos resultado_compresión=/LEO. Además, debemos añadir tira+carácter=O/ al diccionario y colocar en tira el valor de carácter. Así, tenemos por ahora:
tira
=/, carácter=/, resultado_compresión=/LEO,
diccionario
= .... 0...255 caracteres ASCII
                256 /L
                258 EO
                259 O/
Siguiente iteración: leemos el sexto carácter de texto y tenemos carácter=L. Nos preguntamos si tira+carácter=/L aparece como una entrada del diccionario. En este caso, la respuesta es que sí, por lo que debemos colocar tira+carácter=/L en la variable tira, es decir, que quedará tira=/L. Así, tenemos por ahora:
tira
=/L, carácter=L, resultado_compresión=/LEO,
diccionario
= .... 0...255 caracteres ASCII
                256 /L
                257 LE
                258 EO
                259 O/
Vamos a hacer la siguiente iteración: leemos el octavo carácter de texto y tenemos carácter=E. Nos preguntamos si tira+carácter=/LE aparece como una entrada del diccionario. Puesto que la respuesta es que no, debemos escribir el código de tira en la salida, con lo que tenemos resultado_compresión=/LEO 256. Además, debemos añadir tira+carácter=/LE al diccionario y colocar en tira el valor de carácter. Así, tenemos por ahora:
tira
=E, carácter=E, resultado_compresión=/LEO 256
diccionario
= .... 0...255 caracteres ASCII
                256 /L
                257 LE
                258 EO
                259 O/
                260 /LE
Siguiente iteración: leemos el noveno carácter de texto y tenemos carácter=E. Nos preguntamos si tira+carácter=EE aparece como una entrada del diccionario. Puesto que la respuesta es que no, debemos escribir el código de tira en la salida, con lo que tenemos resultado_compresión=/LEO 256 E. Además, debemos añadir tira+carácter=EE al diccionario y colocar en tira el valor de carácter. Así, tenemos por ahora:
tira
=E, carácter=E, resultado_compresión=/LEO 256 E
diccionario
= .... 0...255 caracteres ASCII
                256 /L
                257 LE
                258 EO
                259 O/
                260 /LE
                261 EE
Siguiente iteración: leemos el décimo carácter de texto y tenemos carácter=S. Nos preguntamos si tira+carácter=ES aparece como una entrada del diccionario. Puesto que la respuesta es que no, debemos escribir el código de tira en la salida, con lo que tenemos resultado_compresión=/LEO 256 EE. Además, debemos añadir tira+carácter=ES al diccionario y colocar en tira el valor de carácter. Así, tenemos por ahora:
tira
=S, carácter=S, resultado_compresión=/LEO 256 EE
diccionario
= .... 0...255 caracteres ASCII
                256 /L
                257 LE
                258 EO
                259 O/
                260 /LE
                261 EE
                262 ES
Una más: leemos el undécimo carácter de texto y tenemos carácter=/. Nos preguntamos si tira+carácter=S/ aparece como una entrada del diccionario. Puesto que la respuesta es que no, debemos escribir el código de tira en la salida, con lo que tenemos resultado_compresión=/LEO 256 EES. Además, debemos añadir tira+carácter=S/ al diccionario y colocar en tira el valor de carácter. Así, tenemos por ahora:
tira
=/, carácter=/, resultado_compresión=/LEO 256 EES
diccionario
= .... 0...255 caracteres ASCII
                256 /L
                257 LE
                258 EO
                259 O/
                260 /LE
                261 EE
                262 ES
                263 S/
Ya falta menos: leemos el duodécimo carácter de texto y tenemos carácter=L. Nos preguntamos si tira+carácter=/L aparece como una entrada del diccionario. En este caso, la respuesta es que sí, por lo que debemos colocar tira+carácter=/L en la variable tira, es decir, que quedará tira=/L. Así, tenemos por ahora:
tira
=/L, carácter=L, resultado_compresión=/LEO 256 EES
diccionario
= .... 0...255 caracteres ASCII
                256 /L
                257 LE
                258 EO
                259 O/
                260 /LE
                261 EE
                262 ES
                263 S/
Ahora leemos el decimotercer carácter de texto y tenemos carácter=E. Nos preguntamos si tira+carácter=/LE aparece como una entrada del diccionario. En este caso, la respuesta es que sí, por lo que debemos colocar tira+carácter=/LE en la variable tira, es decir, que quedará tira=/LE. Así, tenemos por ahora:
tira
=/LE, carácter=E, resultado_compresión=/LEO 256 EES
diccionario
= .... 0...255 caracteres ASCII
                256 /L
                257 LE
                258 EO
                259 O/
                260 /LE
                261 EE
                262 ES
                263 S/
Ahora leemos el decimocuarto carácter de texto y tenemos carácter=E. Nos preguntamos si tira+carácter=/LEE aparece como una entrada del diccionario. Puesto que la respuesta es que no, debemos escribir el código de tira en la salida, con lo que tenemos resultado_compresión=/LEO 256 EES 260. Además, debemos añadir tira+carácter=/LEE al diccionario y colocar en tira el valor de carácter. Así, por ahora tenemos:
tira
=E, carácter=E, resultado_compresión=/LEO 256 EES 260
diccionario
= .... 0...255 caracteres ASCII
                256 /L
                257 LE
                258 EO
                259 O/
                260 /LE
                261 EE
                262 ES
                263 S/
                264 /LEE
El bucle ya no se puede repetir más veces porque se han acabado los caracteres para leer de la entrada texto. A continuación, debemos dar el último paso del algoritmo, es decir, escribir el código de tira en la salida, por lo que el texto comprimido queda:
resultado_compresión=/LEO 256 EES 260 E
Este algoritmo lo podemos entender como un ingenioso método de compresión en el que se construye un diccionario formado por los 256 caracteres ASCII seguido de tiras de caracteres ASCII que salen en la información que se tiene que comprimir. Las tiras que se introducen en el diccionario son, en primer lugar, las agrupaciones de dos en dos de caracteres contiguos de la entrada para comprimir. Así, si se observa el diccionario construido, podemos ver que las entradas en el diccionario son /L, LE, EO, O/. En el momento en que se llega a una entrada repetida, se acumula un carácter más de los leídos en la información que se tiene que comprimir; éste es el caso de la entrada 260 de nuestro diccionario, en la que se acumula a /L el siguiente carácter, de modo que queda /LE. También pasa en la entrada 264 del diccionario, en la que se tendría que poner /L, pero como ya está listada, se le añade el siguiente carácter: /LE. Sin embargo, también esta tira está entrada en el diccionario, por lo que se le añade el siguiente carácter: /LEE. Evidentemente, esta construcción del diccionario se hace numerando las entradas.
Observemos la salida comprimida del primer ejemplo:
resultado_compresión=/LEO 256 EES 260 E
Construyamos el diccionario que se obtendría al comprimir la entrada:
texto=/COMO/COMES/COME
En las primeras posiciones, vamos poniendo los caracteres contiguos de texto de dos en dos hasta encontrar que se repita alguno:
256=/C, 257=CO, 258=OM, 259=MO, 260=O/
Ahora encontramos la primera que se repite y, por tanto, le adjuntamos un carácter más:
261=/CO
Volvemos a encontrar una tira que se repite: la tira OM. Por tanto, añadimos un carácter más:
262=OME, 263=ES, 264=S/
Tenemos que entrar en el diccionario /C, pero ya está entrada, por lo que acumulamos un carácter más /CO, que también está entrado, por lo que todavía acumulamos un carácter más: /COM:
265=/COM, 266=ME
Por tanto, el diccionario nos quedaría:
256=/C, 257=CO, 258=OM, 259=MO, 260=O/, 261=/CO, 262=OME, 263=ES, 264=S/, 265=/COM, 266=ME
Se trata de los caracteres ASCII de los caracteres de la entrada, aunque por claridad hemos convenido de poner el carácter mismo, a parte de los códigos de las tiras repetidas que ha detectado el algoritmo. Se podría pensar en mejorar la compresión fijándose en el hecho de que, por ejemplo, la tira /L sale en el resultado de la compresión la primera vez sin comprimir. Mirando más detenidamente la salida comprimida, se observa que no sólo le pasa a /L, sino también a /LE. La razón por la que este algoritmo no realiza esta simplificación es debida al proceso de descompresión que ahora explicaremos, después de exponer un ejemplo más de cálculo de la salida comprimida.
El proceso de descompresión es muy fácil si sustituimos cada código por la entrada del diccionario que le tocaría. Pensemos que la compresión no contiene el diccionario, por lo que se tiene que construir a la vez. En los dos ejemplos vemos cómo se procede:
Ejemplo 1
Descomprimamos:
resultado_compresión=/LEO 256 EES 260 E
Para ello es inmediata la primera parte, ya que podemos descomprimir:
texto_descomprimido=/LEO
Ahora nos encontramos con el primer código, para lo que tenemos que construir el diccionario asociado al fragmento de tira descomprimida:
256=/L, 257=LE, 258=EO
Ahora podemos identificar qué es lo que tenemos que sustituir por el código 256, y podemos continuar hasta:
texto_descomprimido=/LEO/LEES
Como antes, para descomprimir el código 260, debemos continuar con la construcción del diccionario:
256=/L, 257=LE, 258=EO, 259=O/, 260=/LE, 261=EE, 262=ES
Y ahora, ya se puede acabar de descomprimir:
texto_descomprimido=/LEO/LEES/LEE
Ejemplo 2
Descomprimamos:
resultado_compresión=/COMO 256 258 ES 261 ME
Como antes, es inmediata la primera parte, ya que podemos descomprimir:
texto_descomprimido=/COMO
Ahora nos encontramos con el primer código, para lo que tenemos que construir el diccionario asociado al trozo de tira descomprimida:
256=/C, 257=CO, 258=OM, 259=MO
Ahora podemos identificar qué es lo que tenemos que sustituir por el código 256, y podemos continuar hasta:
texto_descomprimido=/COMO/COMES
Como antes, para descomprimir el código 261, debemos continuar con la construcción del diccionario:
256=/C, 257=CO, 258=OM, 259=MO, 260=O/, 261=/CO, 262=OME, 263=ES
Y ahora, ya se puede acabar de descomprimir:
texto_descomprimido=/COMO/COMES/COME
Las tasas de compresión se determinan calculando lo que se necesitaría para codificar sin compresión y el tamaño de la información comprimida. Si el texto no es muy largo, con un diccionario de 512 entradas sería suficiente, por lo que se necesitarían 9 bits para codificar cada entrada. Evidentemente, en las implementaciones prácticas de este compresor no sería válido este diccionario. En el primer ejemplo hemos obtenido 10 entradas de diccionario en el resultado comprimido, en comparación con las 13 que se necesitarían, por lo que hemos ganado 3 caracteres. Para ser honrados tendremos que comparar la efectividad de compresión con la escritura del texto sin comprimir utilizando 8 bits, que se necesitan para representar todos los caracteres ASCII, por lo que el número de bits que se necesitan para el texto sin comprimir es 13 · 8 = 104 bits, mientras que el comprimido necesita 10 · 9 = 90 bits; por tanto, esto supone una mejora de 14 bits, por lo que la tasa de compresión será de Este método de compresión es muy potente, pero, evidentemente, su eficacia queda patente cuando el volumen de información que se comprime es más alto que el de estos ejemplos.

3.Otros formatos y software de compresión

3.1.GIF, JPEG y MPEG

Una imagen está formada por un conjunto de píxeles, unidad mínima de nuestro sistema de representación de imágenes. En las imágenes monocromáticas, cada píxel tiene asociado un nivel de gris por medio de un número entre 0 y M. 0 significa ausencia total de luz, y M, la máxima luminosidad. Del número de píxeles (resolución) y del nivel de gris por píxel que se pueda expresar depende la calidad de la imagen. En general, se ha comprobado que aunque la resolución es importante, lo es más aún el número de niveles de gris (o de colores) que se pueden expresar. Por ejemplo, la nitidez que se consigue duplicando el número de niveles de gris es mayor que si se hace lo mismo con el número de píxeles (aunque puede producir el efecto de "sierra").
La cantidad de memoria necesaria para almacenar una imagen puede ser muy alta. Una pantalla de 800 × 600 píxeles con 16 bits por píxel para representar el color del píxel nos da un total de 7.680.000 bits, equivalente a 960.000 bytes (1 byte equivale a 8 bits), que son 937,5 KB (1 KB equivale a 1.024 bytes).
Para almacenar imágenes en movimiento necesitamos mucha más memoria, ya que es necesario almacenar o procesar muchas más imágenes. Esto es así porque el usuario necesita ver al menos 24 imágenes por segundo, si se quiere evitar el molesto efecto de "parpadeo".
El formato GIF para imágenes es, junto con el formato JPG, uno de los más conocidos, al ser el tipo de imágenes que se pueden insertar en páginas web. Las siglas GIF corresponden a Graphics Interchange Format. El método de compresión que se usa para almacenar imágenes en este formato está basado en el algoritmo LZW, y fue creado en 1987 por CompuServe.
Las siglas JPEG corresponden a Joint Photographic Experts Group, nombre del equipo que diseñó el algoritmo para comprimir imágenes que ahora conocemos como JPEG o como JPG. El método JPEG fue diseñado para comprimir tanto imágenes en color como en una escala de grises, pero siempre pensando en imágenes reales. Este método de compresión no es apropiado para imágenes que no sean reales, como dibujos tipo cómic o dibujos lineales.
El algoritmo de compresión JPEG se da con pérdidas, con lo cual la imagen que se obtiene al descomprimir no es exactamente igual a la imagen original antes de ser comprimida. El algoritmo consigue gran parte de la compresión gracias a las limitaciones del ojo humano, especialmente usando el hecho de que pequeñas variaciones en el color de una imagen no son tan perceptibles como los grandes contrastes entre partes claras y partes oscuras. El método de compresión JPEG admite una variante sin pérdidas, pero pierde su gran capacidad de compresión, de forma que casi no se usa.
Las siglas MPEG provienen de Moving Picture Experts Group. Existen varios tipos de compresores bajo estas mismas siglas. Estos compresores se usan para almacenar información audiovisual. Las variantes de este algoritmo se han adaptado para almacenar vídeos en CD, para la transmisión en televisión digital, películas en DVD, sonido para la telefonía de banda ancha y vídeos para navegadores de Internet.

3.2.ZIP

Uno de los formatos de compresión de ficheros más populares es el ZIP. El método de compresión que usa está basado en el método LZW. A continuación explicaremos el uso de WinZip, un programa de compresión de ficheros para Windows con este formato.
1) Compresión y descompresión con WinZip
Uno de los programas más usados para comprimir ficheros en formato ZIP es WinZip. Aun así, existen otros programas para comprimir y descomprimir archivos en formato ZIP. Otros métodos para compresión de ficheros son los que generan archivos con extensión .arj, .rar, .ace, .zip, .tar, .cab, .gz, etc. El mismo programa WinZip permite descomprimir este tipo de formatos.
El programa puede conseguirse en la web http://www.winzip.com. Este programa no es freeware, pero explicaremos su funcionamiento por ser uno de los más populares. La instalación de este programa no requiere demasiadas explicaciones. Empezaremos ejecutando el fichero de instalación e iremos siguiendo los pasos que se nos indican. Al no ser un programa freeware, deberemos aceptar las condiciones de la licencia de uso.
m7e3_rec1.gif
m7e3_rec2.gif
Las operaciones continúan con los pasos siguientes:
m7e3_rec3.gif
m7e3_rec4.gif
En el primero de estos dos pasos, deberemos elegir qué versión del programa deseamos utilizar: Wizard o Classic. La versión Wizard es más fácil de usar, pero aconsejamos instalar la versión Classic. Una vez instalado el programa, no tiene ninguna complicación pasar de una versión a otra. El siguiente paso nos permite seleccionar la instalación de distintas opciones del programa. Recomendamos instalar todas las opciones, con lo que seleccionaremos Express setup.
En el siguiente paso encontramos la ventana:
m7e3_rec5.gif
Si hacemos clic sobre el botón Associations... podremos escoger qué tipo de ficheros comprimidos queremos poder descomprimir con el WinZip. Si deseamos descomprimir todos los ficheros posibles, podemos pasar directamente al siguiente paso, en el que se realiza la instalación y finaliza el proceso. Si no deseamos descomprimir algún tipo de archivo con el WinZip, deberemos deseleccionarlo de la lista que se obtiene al entrar en Associations...
m7e3_rec6.gif
Una vez efectuada la instalación, tenemos varias formas de ejecutar el programa. Una de las más cómodas es desde el Explorador de Windows. Para comprimir uno o varios ficheros, simplemente los seleccionamos y hacemos clic sobre el botón derecho del ratón. Aparecerán dos opciones del programa WinZip:

  • Add to Zip: para comprimir los ficheros seleccionados y ponerlos en un fichero de extensión .zip.

  • Add and E-Mail directorio.zip: esta opción comprime los ficheros seleccionados, crea un fichero tipo .zip y lo adjunta a un mensaje de correo electrónico a punto para su envío.

m7e3_rec7.gif
Con la primera opción tenemos la posibilidad de crear este archivo en la carpeta que deseemos y deberemos escribir un nombre para el archivo comprimido. La segunda opción es muy práctica en caso de que sólo queramos crear el fichero para mandarlo por correo electrónico. WinZip abrirá una nueva ventana del programa de correo electrónico que tengamos establecido por defecto y adjunta el archivo comprimido. Por defecto nombra el archivo comprimido con el nombre de la carpeta donde se encuentren los ficheros que hemos comprimido.
En caso de que sólo queramos comprimir un fichero, tendremos una tercera opción que nos ofrece crear directamente un archivo ZIP con el mismo nombre que el fichero que queremos comprimir.
En la ventana de diálogo que aparece en esta forma de utilización de WinZip, disponemos de varias opciones para la compresión; podemos decidir distintas acciones sobre los ficheros que utilicemos, encriptar la compresión, etc. Esta ventana es muy parecida a la que obtendremos si ejecutamos el programa WinZip y seleccionamos la opción Add.
Hay varias formas de realizar la compresión:

  • Maximum (slowest): es la compresión máxima, aunque requiere un poco más de tiempo.

  • Normal: compresión normal.

  • Fast: menor compresión pero más rápida de realizar.

  • Super fast: menor compresión que el caso anterior e incluso más rápida de realizar.

  • None: esta opción no comprime, simplemente almacena uno o varios ficheros en un archivo ZIP sin comprimirlos.

Las opciones dentro de Action sirven para decidir cómo actuar sobre los ficheros. Si estamos añadiendo ficheros en un archivo tipo ZIP, debemos escoger la opción adecuada según queramos reemplazar ficheros en caso de solapamientos, borrarlos, etc. Las opciones que hay que elegir son:

  • Add (and replace) files: añade todos los ficheros seleccionados al archivo ZIP que estemos creando.

  • Freshen existing files: esta opción renueva posibles ficheros existentes en el archivo ZIP, en caso de que estemos añadiendo ficheros a un archivo ZIP ya existente.

  • Move files: esta opción actúa igual que la opción Add, pero una vez incluidos los ficheros en el archivo ZIP los borra del disco.

  • Update (and add) files: comprobad cuáles de los ficheros seleccionados no están en un archivo Zip existente y cuáles han cambiado desde la creación del archivo Zip y los actualiza.

También deberemos señalar las opciones:

  • Save full path info: marcando esta casilla guardaremos los ficheros y, al descomprimirlos, se mantendrán ordenados según en qué carpetas de Windows están almacenados. Si dejamos la casilla sin marcar, tendremos todos los ficheros en una misma carpeta en el momento de la descompresión.

  • Store filenames in 8.3 format: si dejamos esta casilla sin marcar, los nombres de los ficheros se almacenan usando su nombre en Windows (es decir, acepta nombres de fichero largos). Marcando esta casilla, los ficheros comprimidos se guardan en el archivo ZIP con su nombre de ocho dígitos.

WinZip permite, asimismo, añadir una contranseña a la compresión de ficheros, de forma que quien quiera descomprimir este fichero, sólo podrá hacerlo si dispone de la contraseña. Para ello sólo es necesario presionar el botón Password y escribir una contraseña en el momento de efectuar la compresión.
La forma más sencilla de descomprimir un archivo WinZip es haciendo doble clics en el archivo desde el mismo Explorador de Windows. Las instrucciones que hay que seguir para la descompresión son relativamente simples.
Una vez comprimido un fichero a formato ZIP, podemos encontrarnos que, al mandarlo a un usuario, éste no disponga del programa para descomprimirlo. Esto se soluciona fácilmente creando un fichero tipo EXE, que se descomprime al ejecutarlo. Una vez creado el archivo ZIP lo abrimos con el WinZip haciendo doble clic en el fichero desde el Explorador del Windows, o bien abriendo el archivo ZIP directamente con el programa WinZip. Una vez vemos el contenido del archivo ZIP, seleccionamos la opción Make EXE file dentro del menú Action.
Otra opción interesante de WinZip es comprimir uno o varios ficheros o carpetas en un solo archivo para poder guardarlo en un disquete. Un problema típico es querer guardar un archivo que ocupa más de 650 Mb en un CD-ROM, cuya capacidad máxima no permite almacenar un fichero de estas características. Para conseguirlo, seleccionamos el fichero, o ficheros y carpetas, que deseamos guardar en el CD-ROM y comprimimos con el WinZip pero creando directamente el archivo en el CD-ROM. WinZip empezará la compresión y guardará el contenido en el CD-ROM. Una vez el disquete esté lleno, WinZip solicitará un nuevo CD-ROM. Así sucesivamente con tantos CD-ROM como sea necesario hasta acabar la compresión y almacenamiento. Para descomprimir un fichero ZIP que tengamos en varios CD-ROM deberemos insertar, en primer lugar, el primer CD-ROM. WinZip detectará que se trata de un fichero troceado en varios CD-ROM. A continuación sólo es necesario seguir las instrucciones que nos proporciona el programa.
Tal como hemos estudiado anteriormente, para comprimir un fichero se aprovechan las repeticiones dentro del mismo, es decir, aprovecha la redundancia para comprimir más el fichero. Con los dos ejercicios siguientes podremos experimentar este hecho.
Actividad
Ejercicio 1
Cread un fichero de texto con el Bloc de Notas del Windows y escribid, únicamente, cien líneas con cincuenta caracteres '1' cada línea. Para conseguir esto de forma fácil, utilizad las opciones de copiar y pegar adecuadamente. Guardad este fichero con el nombre fichero100.txt. Abrid de nuevo el fichero y copiad las cien líneas de unos y pegadlas cinco veces más, consiguiendo un fichero como el anterior pero con quinientas líneas de unos. Guardad este fichero con el nombre fichero500.txt. Hemos creado dos ficheros, uno con cien líneas de unos y otro con quinientas. Observad las propiedades de los dos ficheros para comparar la memoria necesaria para almacenarlos. Comprimid cada uno de estos dos ficheros en un archivo ZIP (escoged la máxima compresión) y comparad la memoria utilizada para cada uno de los dos archivos obtenidos. ¿Cuál es la tasa de compresión para cada uno de estos archivos?
Ejercicio 2
Ahora crearemos otro fichero de texto, pero con un texto donde no haya tanta redundancia como en el anterior. Copiad los dos primeros capítulos de El Quijote de la Mancha de la web del Instituto Cervantes: http://cvc.cervantes.es/obref/quijote/indice.htm y pegadlos en un fichero de texto. Guardad este fichero y comprimidlo con WinZip con máxima compresión. Observad cuál ha sido la tasa de compresión de este fichero y comparadla con el grado de compresión de los dos ficheros del ejercicio anterior.
2) Otros programas para compresión y descompresión ZIP: FreeZip, ARJ Folder, etc.
Existen varios programas, además de WinZip, para la compresión y descompresión de formato ZIP. Citaremos un par de estos programas simplemente como información a nivel de usuario.
Uno de éstos es FreeZIP. Su funcionamiento es parecido al WinZip, aunque no tiene todas las mismas aplicaciones. Al igual que WinZip, se integra con el Explorador de Windows y usa asociaciones de archivos y menús contextuales para comprimir o descomprimir archivos. También permite la inclusión de nombres largos de directorios y subdirectorios.
El programa ARJ Folder se creó para los archivos comprimidos tipo ARJ, aunque también permite descomprimir archivos con otros formatos como RAR, ACE, ZIP, TAR, CAB, etc. Permite la protección de archivos comprimidos con contraseña y se adapta a Windows de forma parecida a los descritos anteriormente.

3.3.MP3

Terminaremos este módulo con el formato de compresión de sonido más famoso, el MP3. No ha sido ninguna casualidad el espectacular auge de este formato, sólo hay que tener en cuenta que el tamaño de una canción normal de cuatro minutos en el formato WAV puede ocupar unos 40 MB, mientras que al ser comprimida en un fichero MP3, sólo ocupa unos 4 MB.
1) Fundamentos del MP3
MP3 es el acrónimo de MPEG Audio Layer 3 (MPEG Layer-3 Low Bitrate Audio Coding). Este sistema de compresión fue desarrollado por la MPEG en colaboración con el Instituto Fraunhofer, y se estandarizó posteriormente con el nombre de ISO-MPEG Audio Layer 3. Éste es un método de compresión con pérdidas, aunque éstas no son perceptibles para el oído humano. El proceso consiste en la aplicación de algoritmos que se encargan de eliminar o modificar todo aquello que es superfluo para nuestro oído. Destacan las siguientes técnicas dentro del proceso de codificación:
a) El efecto de enmascaramiento se basa en la ocultación de ciertos sonidos cuando otros prevalecen. La codificación debe elegir qué sonido queda enmascarado en cada momento; de esta forma no codificamos los sonidos que quedan en segundo plano.
b) El umbral acústico mínimo consiste en no codificar sonidos a frecuencias fuera del intervalo de percepción de nuestro oído, es decir, fuera del intervalo que va de 20Hz a 20Khz.
c) La reserva de bytes: ciertas partes de las canciones no pueden ser codificadas en un intervalo fijo sin alterar la calidad. Para solucionar esto, el algoritmo de codificación utiliza una pequeña cantidad de bytes para aumentar la amplitud del intervalo bajo ciertas condiciones.
d) El Joint Stereo se basa en que, a partir de cierta frecuencia, el oído no es capaz de apreciar la localización de un sonido. A partir de esto, el formato MP3 graba ciertas frecuencias con una señal mono, acompañada de cierta información que permite restaurar la localización espacial del sonido.
e) El algoritmo de Huffman es utilizado para finalizar el proceso de compresión. La ventaja de utilizar este algoritmo se basa en la rapidez de la decodificación y en que ganamos hasta un 20% de espacio.
2) Sofware de compresión y reproducción
Para comprimir un fichero WAV a un fichero MP3 necesitamos un programa codificador, también llamado encoder. Existen muchos programas, podemos citar L3Enc, MP3Enc, Blade, PsytelMp4, XingMP3, Lame, Vorbis, etc. Estos programas normalmente sólo son el motor de codificación, es decir, forman parte de otro programa que tiene una interfaz Windows y que utiliza este motor para hacer la compresión. Estas interfaces se llaman FrontEnds, y podemos encontrarlas de todo tipo en Internet. Se encuentran ligadas a un único encoder y otras que pueden trabajar con varios, de manera que se elige qué motor se quiere utilizar para realizar la compresión.
La descompresión es realizada por el reproductor. Al igual que en el campo de compresores, también hay muchos reproductores. Los más extendidos son WinAmp, Sonique, Real JukeBox, XingMPEG Player, 4MP3, etc.
Uno de los FrontEnds más completos, ya que contiene la mayoría de los motores que hemos comentado y que además es gratuito, es el CDex, que se puede encontrar en http://cdexos.sourceforge.net. Respecto a los reproductores, el Winamp es el mas extendido y se puede encontrar en http://www.winamp.com/.
La compresión del audio está evolucionando de una forma vertiginosa. Hay muchos intereses económicos en este campo, y esta circunstancia crea importantes recursos humanos y económicos dedicados tanto al desarrollo de nuevos formatos de compresión como MP4 o OGG de Vorbis, como a la protección mediante marcas de agua, etc.

Ejercicios de autoevaluación

1. Los métodos de compresión se pueden clasificar en dos tipos que son...

a) los métodos LZW y los métodos ARJ.
b) los que sirven para comprimir imágenes y los que sirven para comprimir audio.
c) con pérdidas y sin pérdidas.

2. El método de Shannon-Fano...

a) es uno de los más potentes métodos de compresión de datos y, a pesar de que fue el primer método que se creó, sigue siendo el más usado.
b) fue el primer método de compresión de datos que se creó, pero quedó en desuso rápidamente en cuanto apareció el método de Huffman.
c) es un método de compresión con pérdidas para videoconferencias.

3. Comprimimos un fichero de datos que ocupa originalmente 32.000 bytes, y una vez comprimido, ocupa 14.400 bytes. La tasa de compresión ha sido de...

a) 45%.
b) 55%.
c) 17,6%.

4. Una imagen de 20 × 100 píxeles en 16 tonos de gris se comprime por un cierto método. Si la tasa de compresión es del 30%, ocupará...

a) 700 bytes.
b) 225 bytes.
c) 750 bytes.

5. Dada una imagen 4 × 3 píxeles en 16 tonos de gris, se codifican los tonos de gris con números en sistema decimal entre 0 y 15. A cada píxel le corresponde un tono de gris según la tabla siguiente:
76508_m4_01.gif
Entonces, la compresión de la imagen con el método diferencial en sistema decimal será...

a) 7 1 1 0 3 1 1 3 1 1 0 0.
b) 7 1 1 0 –3 –1 –1 3 1 –1 0 0.
c) 7 1 1 –4 1 3 –5 3 1 –1 0 0.

6. El método de compresión RLL es un método...

a) sin pérdidas gracias a que la longitud de almacenamiento es limitada.
b) que puede ser con pérdidas o sin pérdidas, dependiendo de la longitud de almacenamiento que usemos.
c) que no es de compresión.

7. Las imágenes con formato GIF usan como método de compresión...

a) un algoritmo basado en el método de compresión LZW.
b) el mismo algoritmo que JPEG.
c) una compresión diferencial.

8. El formato JPEG está creado para...

a) dibujo lineal.
b) dibujos animados en vídeo.
c) fotografías e imágenes del mundo real.

9. Algunas de las grandes ventajas del formato ZIP son...

a) que crea archivos con un formato que se puede distribuir por la Red y su tasa de compresión es superior al 75% para cualquier fichero.
b) que admite nombres largos (tipo Windows) para los ficheros, aunque sólo sirve para comprimir ficheros de datos.
c) que permite comprimir varios ficheros en un solo archivo, también permite crear archivos comprimidos autoejecutables y puede comprimir un solo fichero fragmentado en varios archivos.

10. El método de compresión LZW es un método...

a) basado en el uso de las probabilidades de aparición de caracteres.
b) de diccionario.
c) con pérdidas.

11. Tenemos la tira de caracteres comprimida por el método LZW siguiente: JA 256 256. Al descomprimirla, obtendremos...

a) JAAJAJ.
b) AJAJAJ.
c) JAJAJA.

12. Comprimimos la expresión YXYY con el método aritmético. La compresión puede ser...

a) 0,4.
b) 0,25.
c) 0,6.

13. El método de compresión aritmético...

a) es un método con pérdidas, ya que la descompresión no recupera nunca la información original.
b) es un método sin pérdidas.
c) es un método de diccionario.

14. Comprimimos la tira de caracteres GMMD con el método de Huffman. La tasa de compresión para este ejemplo será...

a) 12,5%.
b) 20%.
c) 25%.

15. Hemos comprimido con el método Huffman una palabra en castellano. La codificación de los caracteres que intervienen es A = 10, I = 11 y L = 0. ¿Cuál de las siguientes tiras es la compresión?

a) 100011.
b) 000111.
c) 111000.

Solucionario

1. a) Incorrecto. LZW y ARJ son sólo dos algoritmos de compresión.
b) Incorrecto. También hay métodos de compresión para datos, vídeo, etc.
c) Correcto.

2. a) Incorrecto. Actualmente está en desuso.
b) Correcto.
c) Incorrecto. Es un método sin pérdidas para compresión de datos.

3. a) Incorrecto. Repasad vuestros cálculos.
b) Correcto.
c) Incorrecto. Repasad vuestros cálculos.

4. a) Correcto.
b) Incorrecto. Para almacenar 16 tonos de gris, necesitaremos 4 bits en sistema binario: de 0000 a 1111. Calculad el número de bits que ocupará la imagen sin comprimir y aplicad después la tasa de compresión. Recordad que 1 byte equivale a 8 bits.
c) Incorrecto. Para almacenar 16 tonos de gris, necesitaremos 4 bits en sistema binario: de 0000 a 1111. Calculad el número de bits que ocupará la imagen sin comprimir, y aplicad después la tasa de compresión. Recordad que 1 byte equivale a 8 bits.

5. a) Incorrecto. Recordad que tenéis que calcular la diferencia entre el tono de gris de un píxel con el anterior.
b) Correcto.
c) Incorrecto. Recordad que para este método la imagen se codifica por filas en zigzag.

6. a) Incorrecto. Al fijar la longitud de almacenamiento, podemos perder información en la compresión por RLL.
b) Correcto.
c) Incorrecto. Sí que es un método de compresión.

7. a) Correcto.
b) Incorrecto. JPEG y GIF no usan el mismo formato de compresión.
c) Incorrecto. A pesar de que la compresión diferencial sea para imágenes, el formato GIF usa otro método de compresión.

8. a) Incorrecto. Falso. Releed el apartado sobre JPEG.
b) Incorrecto. Falso. Releed el apartado sobre JPEG.
c) Correcto.

9. a) Incorrecto. Un archivo ZIP se puede distribuir por la Red, pero la tasa de compresión a formato ZIP no tiene por qué ser superior al 75%.
b) Incorrecto. Admite nombres largos y puede comprimir cualquier tipo de fichero.
c) Correcto.

10. a) Incorrecto. La versión básica de este método no utiliza las probabilidades en ningún momento.
b) Correcto.
c) Incorrecto. La versión básica de este método es sin pérdidas.

11. a) Incorrecto. Notad que la primera entrada del diccionario es 256=JA.
b) Incorrecto. Notad que comienza por JA.
c) Correcto.

12. a) Incorrecto. En este caso, la segunda letra sería una Y.
b) Incorrecto. En este caso, la segunda letra también sería una Y.
c) Correcto.

13. a) Incorrecto. Sí es posible recuperar la información original.
b) Correcto.
c) Incorrecto. No es un método de diccionario.

14. a) Incorrecto. Calculad cuántos bits son necesarios para codificar sólo los tres caracteres G, M y D, además de buscar la compresión Huffman de esta palabra.
b) Incorrecto. Calculad cuántos bits son necesarios para codificar sólo los tres caracteres G, M y D, además de buscar la compresión Huffman de esta palabra.
c) Correcto.

15. a) Correcto.
b) Incorrecto. Esta palabra no se puede descomprimir con esta codificación.
c) Incorrecto. Se obtiene la palabra IALL, que no existe en castellano.