Teoría de la información. (la imposibilidad de) El compresor infinito

EL COMPRESOR TEORÍA DE LA INFORMACIÓN (LA IMPOSIBILIDAD DE) Comprimir consiste en eliminar la redundancia. una patente en EEUU para su tecnología HyperSpaceTM, que alardeaba de comprimir datos aleatorios. 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 burbuja 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ágicas. Todas estas empresas han desaparecido. 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 DEEEEEECCCCBBBFTTTT WCCAAAAAJJJLLLLL como: 15AB3ACD6E4C3BF4TW2C5A3J5L Lo que antes ocupaba 55 caracteres, ahora ocupa sólo 26: ¡una disminución del 53%! En el ejemplo anterior hemos usado una versión bastante pedestre de un algoritmo de codificación por longitud de recorrido (RunLength Encoding, RLE), pero que muestra la idea básica: eliminar aquello que se repite. rencias por Internet, etc. En resumen: permiten exprimir más nuestra capacidad de transmisión y almacenamiento de datos. 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 contrapartida, los compresores lossy alcanzan niveles de compresión mucho mayores que los compresores lossless (a costa de la calidad del fichero obtenido). Hay aplicaciones en las que es imprescindible usar compresores lossless, por ejemplo, en un documento de un procesador de texto: si usáramos un compresor lossy, perderíamos información, y al decomprimirlo, podríamos encontrarnos 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 inapreciable. Los conocidos formatos MP3, MPEG, AVI, etc. son formatos de compresión lossy: se consigue que el audio o el vídeo ocupen poco espacio a costa de disminuir su calidad. INFINITO B para terminar las investigaciones", "tenemos la tecnología pero hace falta un socio interesado en comercializar 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 "invento", un navegador de Internet llamado XWebs, que supuestamente multiplicaba por cuatro la velocidad de navegación. ZeoSync anunciaba en su página nada menos que cinco tecnologías relacionadas con la compresión de datos: codificador (BinaryAcceleratorTM), compresor (BitPerfectTM), secuenciador (Zero Space TunerTM), transformador de dominio (Relational Differentiation EncodingTM) y el conjunto de todo (TunerAcceleratorTM). 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 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? it, byte, compresión, tipo de datos... terminología que hace diez años hubiera dejado boquiabierto al más templado es hoy en día de uso corriente. 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 intensamente 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 aseguran haber superado el límite teórico (límite de Shannon) de compresión de datos. Generalmente, estos anuncios van asociados a peroratas como "necesitamos más dinero el escéptico 34 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 HyperDriveTM (de la Claude E. Shannon, el padre de la Teoría de la Información. (Bell Labs) que llegaron a obtener una patente --cosa fácil en EEUU, todo sea dicho--). Web Technologies nos asombraba con su compresor DataFiles/16TM, que comprimía cualquier archivo mayor de 64 KBytes a un dieciseisavo de su tamaño. David C. James obtuvo En compresión de datos se distingue entre dos tipos de compreso- Después de ver en qué consiste la res, los compresores sin pérdida compresión lossy y la compresión (lossless) y los compresores con lossless, podemos intuir que: pérdida (lossy). - La compresión lossless, al ser sin Los compresores eliminan la redundancia, posibilitando que La diferencia es evidente: pérdida de información, tiene un una conexión a Internet lenta per- cuando comprimimos un fiche- límite máximo de compresión. mita transmitir grandes volúmenes ro de ordenador con un compre- La compresión lossy, al ser con de datos, que se puedan realizar sor lossless, al descomprimirlo llamadas telefónicas y videoconfepérdida de información, no tiene 35 el escéptico (LA IMPOSIBILIDAD DE) EL COMPRESOR INFINITO un límite máximo de compresió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ímite, tenemos un 100% de compresión, o lo que es lo mismo, no tendremos nada de información. Por supuesto, siempre que se anuncia uno de estos "compresores mágicos" se habla de compresores lossless, que son los que presentan 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á). 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: - Los compresores lossless actúan 15551111111111555111111111111 eliminando la redundancia. 1111111133333322222224444111 1111111.... Al principio ya vimos una forma de eliminar redundancia: los algo- Como el mensaje M1 (representaritmos RLE. Veamos ahora otra do como 1111111111) aparece forma: los algoritmos de sustitu- mucho (35% de las veces) y es ción de códigos (normalmente se muy largo (10 caracteres) y el usan los dos conjuntamente, el mensaje M5 (representado como RLE y el de sustitución de códigos). 555) aparece poco (8% de las veces) y es corto (3 caracteres) una La sustitución de códigos para forma sencilla de comprimir concomprimir una cadena C (formada siste en intercambiar las represenpor varios mensajes enlazados uno taciones de los mensajes: a continuación de otro) consiste en cambiar la forma en que se representa 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). Al hacer esta "compresión", la cadena de mil mensajes tiene una Veámoslo con un ejemplo. longitud de 5.280 caracteres Imaginemos una fuente que emite (hemos conseguido más de un cinco mensajes: M1, M2, M3, M4 26% de compresión): y M5, con probabilidades 35%, 25%, 20%, 12% y 8% y longitudes 5555552222222444411111111113 (en caracteres) 10, 7, 6, 4 y 3. 333335555552222222222222255 555533333355533333322222225 Msj 5555511111111112222222333333 555444422222223333335552222 222222222244444444333333222 2222222222233333355511111111 1155511111111115555553333332 Si dejamos que la fuente emita mil 2222224444555.... mensajes, teniendo en cuenta las (ahora los 555 representan a M1, probabilidades y las longitudes de no a M5) los mensajes, la cadena emitida ocupará 7.170 caracteres: Podemos hacer lo mismo otra vez, 11111111111111111111222222244 intercambiando las representacio4455533333311111111111111111 nes de los mensajes M2 y M4: 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 desgracia 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 sentido en español). Ahora que ya sabemos "grosso modo" cómo funciona la compresión por sustitución de códigos, vemos que unos mensajes disminuyen 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 ocupan 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 información es completamente aleatoria (todos los mensajes tienen exactamente la misma probabilidad de aparición)? En este caso, no se puede comprimir la cadena, porque al hacer nuestros "intercambios de representaciones" no ganamos nada. La conclusión obvia es que llega un momento en que se ha eliminado 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 cualquier intento de "recomprimir" la 37 - Queremos conservar toda la información. - La compresión lossless es la única En adelante, hablaremos sólo de que conserva toda la información. ANTES QUE NADA ¿QUÉ ES LA INFORMACIÓN? La definición formal dice que la "información" de un mensaje es la medida en que dicho mensaje despeja la incertidumbre sobre algo. Con esta definició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. (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 En teoría de la información se dice que los mensajes mensaje xi: proporcionan la información, así que hablaremos indistintamente de "mensaje" o de "información", porque ésta última está asociada al primero. Debido al signo negativo, cuanto más improbable es También se dice que los mensajes son emitidos por un mensaje, más información aporta. Por ejemplo, una fuente de información, que se supone aleatoria aporta mucha más información decir "hoy en el (así que no podemos predecir qué mensaje va a salir Ecuador hace frío" que decir "hoy en el Ecuador de la fuente). Debido a que la fuente es aleatoria, la hace calor", porque lo primero es mucho más improestadística nos permite caracterizarla usando una bable que lo segundo. variable aleatoria X. La fuente de información puede ser prácticamente cualquier cosa: una persona dictándonos los números que salen del "bombo" de la Lotería, alguien dictá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 computadora 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úsculas, 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 el escéptico 36 Otro concepto de teoría de información que necesitaremos 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 mensajes modelada por la variable X, es decir, la cantidad 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 comprimir los mensajes que emite. 1112222222222222211111111111 1111111113333331111111111333 33322222221111111111111111111 1555222222233333311111111114 4442222222333333111111111122 222222222222444444443333332 2222222222222333333111111111 Tras esta nueva vuelta de tuerca, la cadena de mil mensajes ocupa sólo 4.890 caracteres (hemos conseguido un 32% de compresión respecto a la cadena original). el escéptico (LA IMPOSIBILIDAD DE) EL COMPRESOR INFINITO información ya comprimida será ejemplo, pasar de dominio tiempo a dominio frecuencia) para faciliinfructuoso. tar determinadas operaciones. Veamos un ejemplo sencillo de límite de compresión, con los mis- Podríamos preguntarnos si hacienmos mensajes que antes, pero do algún procesado (tal como una cambiando la probabilidad de apa- transformada de Fourier, una rición: ahora todos los mensajes transformada de Haar o cualquier son equiprobables (aparecen las otro procesamiento de señal) a la mismas veces): cadena sin comprimir (preprocesado) o a la cadena comprimida (postprocesado) sería posible alcanzar una mayor compresión. Es decir, ¿cambia el límite de compresión al cambiar el dominio en Una cadena formada por mil men- que representamos la información? sajes tiene ahora 6.000 caracteres. Intercambiemos las representacio- La respuesta es "no". La razón es nes de M1 y M5: que la teoría de la información se basa en la probabilidad, y el modelo probabilístico ya incluye todas las posibles transformaciones que se puedan hacer, porque al cambiar de dominio, lo único que camLa cadena formada por mil mensa- biamos es el modelo probabilístico jes vuelve a tener exactamente que usamos. 6.000 caracteres. No hemos conseguido nada. El lector puede com- Puede verse la demostración forprobar que tampoco se gana nada mal en el recuadro adjunto, aunque intercambiando las representacio- no es necesario entender la demosnes de M2 y M4, o haciendo cual- tración para seguir leyendo el artíquier otro cambio de representa- culo (puede pasarla por alto si lo ción. Lo único que quedaría por desea). hacer es aplicar un algoritmo RLE para conseguir algo parecido a CONCLUSIÓN esto: Como hemos visto a lo largo del artículo, llega un momento en que seguir aplicando algoritmos de compresión (RLE, sustitución de Transformaciones códigos, etc.) no disminuye el tamaño final, sino que lo aumenta: Las matemáticas y la física suelen hemos llegado al límite de comrecurrir a cambios de dominio (por 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 corresponde ése carácter? (es decir, cómo se tiene que descomprimir ése carácter) 5.000 dólares estadounidenses para quien consiga comprimir datos aleatorios, desafiando así el Teorema de la Complejidad de Kolmogorov (si se intenta comprimir 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). registrada de David C. James. - Pixelon es una marca registrada de Pixelon Corporation. Pau Garcia i Quiles Agradecimientos especiales a Félix Ares y Jean René Moreau por sus valiosos consejos y correcciones. 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) Aunque las tecnologías de compresión usadas hoy en día no siempre son óptimas, cualquier anuncio de tecnología de compresión con límites de compresión muy superiores a los actuales es muy probablemente falso. En cualquier caso, si una tecnologí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 inicio del artículo: no usamos esos compresores fantásticos porque no existen (ni existirán nunca: la analogí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: 2. Comp.compression FAQ, JeanLuc 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 compression 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 registradas de Web Technologies Premier Research Corporation y Minc son marcas registradas de Premier Research Corporation. Pegasus Technologies y HyperDrive son marcas registradas de Pegasus Technologies. HyperSpace es una marca 39 EL CAMBIO DE DOMINIO NO MEJORA LA COMPRESIÓN Dado un modelo probabilístico P y una función reversi- Podemos definir Q(C) tal que para cualquier cadena C, ble M, siempre existe un modelo probabilístico Q tal que Q(M(C)) = P(C), es decir, dos modelos probabilísticos diferentes (uno en cada dominio) nos dan el mismo resulQ(M(C)) = P(C), para cualquier cadena C. tado. Así pues, el cambio de dominio no mejora la entroComo M es reversible, para cualesquier cadenas C y D pía de la fuente y por tanto, no mejora la compresión. (tales que C D), se cumple que M(C) M(D). el escéptico 38 el escéptico