el escéptico
35
el escéptico
34
una patente en EEUU para su tec-
nología HyperSpace™, que alar-
deaba de comprimir datos aleato-
rios. Premier Research Corporation
hizo una aparición estelar con su
compresor Minc, otro que decía
poder comprimir datos aleatorios.
Pixelon se aprovechó de la burbu-
ja de las puntocom para vender
humo y dilapidar 35 millones de
dólares estadounidenses de sus
inversores, mientras decía haber
inventado un compresor de vídeo
y audio de propiedades casi mági-
cas. Todas estas empresas han des-
aparecido.
Para entrar en materia, veamos un
método sencillo de compresión. Si
sustituimos las repeticiones de una
letra por el número de veces que se
repite podríamos comprimir esta
secuencia:
AAAAAAAAAAAAAAABAAAC
D E E E E E E C C C C B B B F T T T T
WCCAAAAAJJJLLLLL
como:
15AB3ACD6E4C3BF4TW2C5A3J5L
Lo que antes ocupaba 55 caracte-
res, ahora ocupa sólo 26: ¡una dis-
minución del 53%!
En el ejemplo anterior hemos
usado una versión bastante pedes-
tre de un algoritmo de codificación
por longitud de recorrido (Run-
Length Encoding, RLE), pero que
muestra la idea básica: eliminar
aquello que se repite.
Los compresores eliminan la
redundancia, posibilitando que
una conexión a Internet lenta per-
mita transmitir grandes volúmenes
de datos, que se puedan realizar
llamadas telefónicas y videoconfe-
rencias por Internet, etc. En resu-
men: permiten exprimir más nues-
tra capacidad de transmisión y
almacenamiento de datos.
CONCEPTOS BÁSICOS
DE TEORÍA DE LA
INFORMACIÓN
La teoría de la información es la
rama de la matemática que estudia
qué es la información, cómo
medirla, cómo representarla y
cómo transmitirla. Este campo es
uno de los más jóvenes de las
matemáticas: su origen es el artí-
culo Una teoría matemática de la
comunicación, publicado en 1948
por Claude Shannon
.
Tipos de compresores: lossy y
lossless
En compresión de datos se distin-
gue entre dos tipos de compreso-
res, los compresores sin pérdida
(lossless) y los compresores con
pérdida (lossy).
La diferencia es evidente:
cuando comprimimos un fiche-
ro de ordenador con un compre-
sor lossless, al descomprimirlo
obtenemos exactamente el mismo
fichero que teníamos en origen,
porque el compresor no produce
pérdida de información. Con un
compresor lossy, en cambio, es
imposible recuperar el fichero tal y
como era en origen, porque el
compresor ha producido pérdida
de información. Como contraparti-
da, los compresores lossy alcanzan
niveles de compresión mucho
mayores que los compresores loss-
less (a costa de la calidad del
fichero obtenido).
Hay aplicaciones en las que es
imprescindible usar compresores
lossless, por ejemplo, en un docu-
mento de un procesador de texto:
si usáramos un compresor lossy,
perderíamos información, y al
decomprimirlo, podríamos encon-
trarnos con que nos faltan frases,
párrafos o imágenes.
En otras aplicaciones, en cambio,
se puede usar sin problemas un
compresor lossy. Los ejemplos
más claros son la voz y la imagen.
Como ni nuestro oído ni nuestro
ojo son perfectos, una disminución
moderada de la calidad es inapre-
ciable. Los conocidos formatos
MP3, MPEG, AVI, etc. son forma-
tos de compresión lossy: se consi-
gue que el audio o el vídeo ocupen
poco espacio a costa de disminuir
su calidad.
Después de ver en qué consiste la
compresión lossy y la compresión
lossless, podemos intuir que:
- La compresión lossless, al ser sin
pérdida de información, tiene un
límite máximo de compresión.
- La compresión lossy, al ser con
pérdida de información, no tiene
Comprimir consiste en eliminar la redundancia.
Claude E. Shannon, el padre de la
Teoría de la Información. (Bell Labs)
B
it, byte, compresión, tipo
de datos... terminología
que hace diez años hubiera
dejado boquiabierto al más tem-
plado es hoy en día de uso corrien-
te. Gracias al avance de la
Sociedad de la Información, la
informática y su vocabulario se
han expandido como la pólvora, a
la par que Internet se introducía en
miles de hogares y empresas.
Además de hacer la declaración de
la renta y comprar libros, Internet
ofrece muchas otras posibilidades.
El deseo de transmitir o almacenar
cada vez un mayor volumen de
datos sin cambiar el medio (línea
telefónica, tarjeta de memoria,
etc.) hace que se trabaje intensa-
mente en el campo de la Teoría de
la Información, especialmente, en
la compresión de datos.
Un compresor es un algoritmo que
disminuye el espacio ocupado por
cierta información. Cada año
vemos en los medios científicos y
especializados (New Scientist,
Nature, Byte, ZDNet, etc.) varios
anuncios de empresas que asegu-
ran haber superado el límite teóri-
co (límite de Shannon) de compre-
sión de datos. Generalmente, estos
anuncios van asociados a peroratas
como “necesitamos más dinero
para terminar las investigaciones”,
“tenemos la tecnología pero hace
falta un socio interesado en comer-
cializar la tecnología” (ergo gastar
dinero en la empresa), etc. ¿Les
suena de algo?
Un estudiante
irlandés de 16
años consiguió
engañar a un
jurado de doce
personas y ganó
el Premio al
Joven Científico
del Año 2002
con su “inven-
to”, un navega-
dor de Internet
llamado XWebs,
que supuesta-
mente multipli-
caba por cuatro
la velocidad de
n a v e g a c i ó n .
ZeoSync anun-
ciaba en su pági-
na nada menos
que cinco tecnologías relacionadas
con la compresión de datos: codifi-
cador (BinaryAccelerator™), com-
presor (BitPerfect™), secuenciador
(Zero Space Tuner™), transforma-
dor de dominio (Relational
Differentiation Encoding™) y el con-
junto de todo (TunerAccelerator™).
Pegasus Technologies afirmaba que
podía guardar 1,28 Gigabytes en un
disquete de 3,5” (cuya capacidad
normal es 1,44 Megabytes) gracias a
su tecnología HyperDrive™ (de la
que llegaron a obtener una patente
—cosa fácil en EEUU, todo sea
dicho—). Web Technologies nos
asombraba con su compresor
DataFiles/16™, que comprimía
cualquier archivo mayor de 64
KBytes a un dieciseisavo de su
tamaño. David C. James obtuvo
TEORÍA DE LA INFORMACIÓN
(LA IMPOSIBILIDAD DE)
EL COMPRESOR
I N F I N I T O
Desde hace muchos años vemos anuncios de empresas que dicen haber inventado
compresores de propiedades asombrosas: ratios de compresión de 100 a 1, de 1000
a 1, etc. ¿Por qué no los usamos si las ventajas son tan evidentes?
el escéptico
37
el escéptico
36
- Los compresores lossless actúan
eliminando la redundancia.
Al principio ya vimos una forma
de eliminar redundancia: los algo-
ritmos RLE. Veamos ahora otra
forma: los algoritmos de sustitu-
ción de códigos (normalmente se
usan los dos conjuntamente, el
RLE y el de sustitución de códigos).
La sustitución de códigos para
comprimir una cadena C (formada
por varios mensajes enlazados uno
a continuación de otro) consiste en
cambiar la forma en que se repre-
senta esa cadena. A la hora de
decidir cómo se hará el cambio, lo
fundamental es la probabilidad
con que se presenta parte de la
cadena (cada mensaje).
Veámoslo con un ejemplo.
Imaginemos una fuente que emite
cinco mensajes: M1, M2, M3, M4
y M5, con probabilidades 35%,
25%, 20%, 12% y 8% y longitudes
(en caracteres) 10, 7, 6, 4 y 3.
Si dejamos que la fuente emita mil
mensajes, teniendo en cuenta las
probabilidades y las longitudes de
los mensajes, la cadena emitida
ocupará 7.170 caracteres:
11111111111111111111222222244
4455533333311111111111111111
1112222222222222211111111111
1111111113333331111111111333
33322222221111111111111111111
1555222222233333311111111114
4442222222333333111111111122
222222222222444444443333332
2222222222222333333111111111
15551111111111555111111111111
1111111133333322222224444111
1111111....
Como el mensaje M1 (representa-
do como 1111111111) aparece
mucho (35% de las veces) y es
muy largo (10 caracteres) y el
mensaje M5 (representado como
555) aparece poco (8% de las
veces) y es corto (3 caracteres) una
forma sencilla de comprimir con-
siste en intercambiar las represen-
taciones de los mensajes:
Al hacer esta “compresión”, la
cadena de mil mensajes tiene una
longitud de 5.280 caracteres
(hemos conseguido más de un
26% de compresión):
5555552222222444411111111113
333335555552222222222222255
555533333355533333322222225
5555511111111112222222333333
555444422222223333335552222
222222222244444444333333222
2222222222233333355511111111
1155511111111115555553333332
2222224444555....
(ahora los 555 representan a M1,
no a M5)
Podemos hacer lo mismo otra vez,
intercambiando las representacio-
nes de los mensajes M2 y M4:
Tras esta nueva vuelta de tuerca, la
cadena de mil mensajes ocupa sólo
4.890 caracteres (hemos consegui-
do un 32% de compresión respec-
to a la cadena original).
El código más conocido, el Morse,
es un código de este tipo. La letra
más frecuente, la e, se representa
por un punto (es decir, la letra más
frecuente es la más corta). Por des-
gracia para el español, la e es la
más frecuente en inglés, mientras
que la más frecuente en español es
la a. Algo similar ocurre con la W,
codificada como “.--" (es decir,
relativamente corta, lo que tiene
sentido en inglés, pero ningún sen-
tido en español).
Ahora que ya sabemos “grosso
modo” cómo funciona la compre-
sión por sustitución de códigos,
vemos que unos mensajes dismi-
nuyen el espacio que ocupan (M1
y M2), otros lo aumentan (M4 y
M5) y algunos no lo varían (M3).
Como los mensajes que ocupan
más aparecen poco y los que ocu-
pan menos aparecen mucho, el
total del espacio ocupado es menor
tras la compresión.
Pero ¿qué ocurre cuando ya no se
pueden hacer más cambios de
representación? Dicho de otro
modo, ¿qué ocurre si la informa-
ción es completamente aleatoria
(todos los mensajes tienen exacta-
mente la misma probabilidad de
aparición)? En este caso, no se
puede comprimir la cadena, por-
que al hacer nuestros “intercam-
bios de representaciones” no gana-
mos nada.
La conclusión obvia es que llega
un momento en que se ha elimina-
do toda la redundancia (utilizando
RLE) y ya no se pueden hacer
intercambios de representaciones,
así que no se puede comprimir
más. Hemos llegado al “límite de
compresión”, que viene dado por
la entropía de la cadena (o fichero)
que deseamos comprimir y cual-
quier intento de “recomprimir” la
(LA IMPOSIBILIDAD DE) EL COMPRESOR INFINITO
Msj
un límite máximo de compre-
sión: podemos comprimir tanto
como queramos. Obviamente,
cuanto más comprimamos,
menos información tendremos
(es decir, peor será la calidad
final obtenida). En el caso lími-
te, tenemos un 100% de com-
presión, o lo que es lo mismo,
no tendremos nada de informa-
ción.
Por supuesto, siempre que se
anuncia uno de estos “compreso-
res mágicos” se habla de compre-
sores lossless, que son los que pre-
sentan mayores dificultades.
Conseguir un compresor lossy con
un nivel de compresión de 1000 a
1 es fácil (eso sí, la calidad se
resentirá).
En adelante, hablaremos sólo de
compresión de tipo lossless, que es
la que nos interesa en este artículo.
Sustitución de códigos
Las ideas básicas que debemos
tener en mente son las siguientes:
- Queremos conservar toda la
información.
- La compresión lossless es la única
que conserva toda la información.
La definición formal dice que la “información” de
un mensaje es la medida en que dicho mensaje des-
peja la incertidumbre sobre algo. Con esta defini-
ción estamos suponiendo que la información se
refiere a algo que desconocemos, es decir, algo que
desde nuestro punto de vista tiene un componente
aleatorio.
En teoría de la información se dice que los mensajes
proporcionan la información, así que hablaremos
indistintamente de “mensaje” o de “información”,
porque ésta última está asociada al primero.
También se dice que los mensajes son emitidos por
una fuente de información, que se supone aleatoria
(así que no podemos predecir qué mensaje va a salir
de la fuente). Debido a que la fuente es aleatoria, la
estadística nos permite caracterizarla usando una
variable aleatoria X.
La fuente de información puede ser prácticamente
cualquier cosa: una persona dictándonos los núme-
ros que salen del “bombo” de la Lotería, alguien dic-
tándonos nombres que lee al azar de la guía telefó-
nica, un archivo de ordenador, etc. En todos estos
casos, podemos reducir los mensajes a caracteres
alfanuméricos (texto y números), que en una com-
putadora se codifican como combinaciones de unos
y ceros.
Nuestro alfabeto y nuestro sistema numérico tienen
un conjunto finito de símbolos (las letras mayúscu-
las, las letras minúsculas, los números del 0 al 9,
etc.). Pongamos, por ejemplo, que son 500 símbolos
(en un caso genérico, hablaríamos de un alfabeto
formado por N símbolos). Debido a esto, los valores
de la variable aleatoria X (es decir, los mensajes)
son también finitos y son exactamente los mismos
(si los mensajes son de un símbolo, la fuente podrá
emitir como mucho N = 500 mensajes diferentes).
Matemáticamente, la información de un mensaje xi
(donde i es el número entre 1 y el número total de
mensajes posibles N; en nuestro ejemplo, i varía
entre 1 y 500) se caracteriza con un logaritmo en
base 2 y la probabilidad de que la fuente X emita ese
mensaje xi:
Debido al signo negativo, cuanto más improbable es
un mensaje, más información aporta. Por ejemplo,
aporta mucha más información decir “hoy en el
Ecuador hace frío” que decir “hoy en el Ecuador
hace calor”, porque lo primero es mucho más impro-
bable que lo segundo.
Otro concepto de teoría de información que necesi-
taremos es la entropía. La idea es muy similar a la de
la termodinámica: la entropía mide lo desordenada
que está la energía, en nuestro caso, lo desordenada
que está la información. La función entropía da la
cantidad media de información de la fuente de men-
sajes modelada por la variable X, es decir, la canti-
dad media de información que nos proporciona un
mensaje xi sobre X:
Como consecuencia de esta definición, cuanto
mayor es la entropía de una fuente, más información
tiene cada mensaje, es decir, más improbable (difícil
de predecir) es el mensaje. Así pues, cuanto mayor
es la entropía de una fuente, más difícil es compri-
mir los mensajes que emite.
ANTES QUE NADA ¿QUÉ ES LA INFORMACIÓN?
el escéptico
39
el escéptico
38
5.000 dólares estadounidenses
para quien consiga comprimir
datos aleatorios, desafiando así el
Teorema de la Complejidad de
Kolmogorov (si se intenta compri-
mir un fichero de datos aleatorios,
el tamaño del fichero comprimido
más el tamaño del compresor
siempre será mayor que el tamaño
del fichero sin comprimir).
REFERENCIAS
BIBLIOGRÁFICAS
1. “Comunicación de datos”, de J.
R. Vidal Català, J. Martínez
Zaldívar (Editorial de la
Universidad Politécnica de
Valencia, 1995)
2. Comp.compression FAQ, Jean-
Luc Gailly (http://www.faqs.org/
faqs/compression-faq).
3. There's no magic, Charles
Bloom (http://www.cbloom.com/
news/nomagic.html)
4. Information content and com-
pression limit
FAQ, Glyph
(http://www.geocities.com/Colleg
ePark/9315/infofaq.htm)
MARCAS CITADAS Y
EMPRESAS QUE LAS
HAN REGISTRADO
-
ZeoSync, BinaryAccelerator,
BitPerfect, Zero Space Tuner,
Relational Differentiation
Encoding y TunerAccelerator son
marcas registradas de ZeoSync
Corporation.
-
Web Technologies y
DataFiles/16 son marcas registra-
das de Web Technologies
-
Premier Research Corporation
y Minc son marcas registradas de
Premier Research Corporation.
-
Pegasus Technologies y
HyperDrive son marcas registra-
das de Pegasus Technologies.
-
HyperSpace es una marca
registrada de David C. James.
- Pixelon es una marca registrada
de Pixelon Corporation.
Pau Garcia i Quiles
(LA IMPOSIBILIDAD DE) EL COMPRESOR INFINITO
Agradecimientos especiales a
Félix Ares y Jean René Moreau
por sus valiosos consejos y correc-
ciones.
información ya comprimida será
infructuoso.
Veamos un ejemplo sencillo de
límite de compresión, con los mis-
mos mensajes que antes, pero
cambiando la probabilidad de apa-
rición: ahora todos los mensajes
son equiprobables (aparecen las
mismas veces):
Una cadena formada por mil men-
sajes tiene ahora 6.000 caracteres.
Intercambiemos las representacio-
nes de M1 y M5:
La cadena formada por mil mensa-
jes vuelve a tener exactamente
6.000 caracteres. No hemos conse-
guido nada. El lector puede com-
probar que tampoco se gana nada
intercambiando las representacio-
nes de M2 y M4, o haciendo cual-
quier otro cambio de representa-
ción. Lo único que quedaría por
hacer es aplicar un algoritmo RLE
para conseguir algo parecido a
esto:
Transformaciones
Las matemáticas y la física suelen
recurrir a cambios de dominio (por
ejemplo, pasar de dominio tiempo
a dominio frecuencia) para facili-
tar determinadas operaciones.
Podríamos preguntarnos si hacien-
do algún procesado (tal como una
transformada de Fourier, una
transformada de Haar o cualquier
otro procesamiento de señal) a la
cadena sin comprimir (preprocesa-
do) o a la cadena comprimida
(postprocesado) sería posible
alcanzar una mayor compresión.
Es decir, ¿cambia el límite de com-
presión al cambiar el dominio en
que representamos la información?
La respuesta es “no”. La razón es
que la teoría de la información se
basa en la probabilidad, y el mode-
lo probabilístico ya incluye todas
las posibles transformaciones que
se puedan hacer, porque al cam-
biar de dominio, lo único que cam-
biamos es el modelo probabilístico
que usamos.
Puede verse la demostración for-
mal en el recuadro adjunto, aunque
no es necesario entender la demos-
tración para seguir leyendo el artí-
culo (puede pasarla por alto si lo
desea).
CONCLUSIÓN
Como hemos visto a lo largo del
artículo, llega un momento en que
seguir aplicando algoritmos de
compresión (RLE, sustitución de
códigos, etc.) no disminuye el
tamaño final, sino que lo aumenta:
hemos llegado al límite de com-
presión.
Esto se puede ver incluso de forma
intuitiva: si siempre se pudiese
seguir comprimiendo, llegaría un
momento en que cualquier cadena
original se reduciría a un único
carácter. ¿Cómo saber a cuál de las
infinitas cadenas originales corres-
ponde ése carácter? (es decir,
cómo se tiene que descomprimir
ése carácter)
Aunque las tecnologías de com-
presión usadas hoy en día no siem-
pre son óptimas, cualquier anuncio
de tecnología de compresión con
límites de compresión muy supe-
riores a los actuales es muy proba-
blemente falso.
En cualquier caso, si una tecnolo-
gía de compresión lossless afirma
superar el límite de Shannon, no
hay duda de que mentirá, así que
no vale la pena perder tiempo en
ella. Ahora ya podemos contestar a
la pregunta que se planteaba al ini-
cio del artículo: no usamos esos
compresores fantásticos porque no
existen (ni existirán nunca: la ana-
logía más clara sería una máquina
de movimiento perpetuo).
Aún así, el lector osado puede
aceptar el reto de Mike Goldman:
Dado un modelo probabilístico P y una función reversi-
ble M, siempre existe un modelo probabilístico Q tal que
Q(M(C)) = P(C), para cualquier cadena C.
Como M es reversible, para cualesquier cadenas C y D
(tales que C D), se cumple que M(C) M(D).
Podemos definir Q(C) tal que para cualquier cadena C,
Q(M(C)) = P(C), es decir, dos modelos probabilísticos
diferentes (uno en cada dominio) nos dan el mismo resul-
tado. Así pues, el cambio de dominio no mejora la entro-
pía de la fuente y por tanto, no mejora la compresión.
EL CAMBIO DE DOMINIO NO MEJORA LA COMPRESIÓN