Comunicaciones
Límites en la compresión de la información
- Skip Navigation :
- Inicio :
- Divulgación :
- Informática :
- Física :
- Religiones :
- Fraudes médicos :
Escepticismo
en España
Escepticismo
en América
Con la implantación masiva de las tecnologías de la información se ha llegado a la necesidad de manejar gran cantidad de datos, ya sea para almacenarlos o para su transmisión, esto ha dado lugar a la necesidad de idear sistemas que compriman. Un compresor es una algoritmo que disminuye el espacio ocupado por cierta información.
Es habitual encontrar en revistas de informática, ya sea especializadas o de divulgación, anuncios de empresas que aseguran haber superado el límite teórico de compresión de datos. Por ejemplo en Irlanda un estudiante de dieciséis años consiguió engañar a un jurado de doce personas al serle adjudicado el premio al “Joven Científico” del año 2002, por haber propuesto una navegador de internet llamado Xwebs, que supuestamente multiplicaba por cuatro la velocidad de navegación.
La empresa ZeoSync (Florida-EE.UU.) anunciaba en su página cinco tecnologías relacionadas con la compresión de datos: codificador, compresor, secuenciador, transformador de dominio y el conjunto de todos, logrando una compresión de 100 a 1. Pegasus Technologies afirmaba que podía guardar 1.28 gigaoctetos en un disquete de 3.5 pulgadas (con capacidad de 1.44 Moctetos) mediante su tecnología, patentada en Estados Unidos, HyperDrive. Web Technologies propone su compresor Datafiles/16 que lograba comprimir cualquier archivo mayor de 64 KB a un dieciseisavo de su tamaño. Otra tecnología patentada en Estados Unidos fue HyperSpace, que comprimía datos aleatorios, al igual que otro compresor Minc. La empresa Pixelon se aprovechó de la burbuja tecnológica para dilapidar 35 millones de dólares de los inversores en un supuesto compresor de vídeo y audio de propiedades casi mágicas. La realidad es que ninguno de esos compresores fue comercializado y estas empresas han desaparecido.
Un método sencillo de compresión consiste en sustituir la repeticiones de una letra por el número de veces que se repite por ejemplo se podría comprimir la siguiente secuencia:
AAAAAAAAAAAAAAABAAACDEEEEEECCCCBBBFTTTTWCCAAAAAJJJLLL
como:
15AB3ACD6E4C3BF4TW2C5A3J5K
lo que antes ocupaba 55 caracteres ahora sólo ocupa 26 es decir se ha logrado una disminución del 53%.
El sistema anterior es un ejemplo sencillo de una algoritmo de codificación por longitud de recorrido (RLE), básicamente consiste en eliminar lo que se repite.
Teoría de la información
La teoría de información es una rama de la teoría matemática de la probabilidad y la estadística que estudia la información y todo lo relacionado con ella: canales, compresión de datos, criptografía y temas relacionados. Su origen se debe al artículo "Una teoría matemática de la comunicación" publicado en 1948 por Claude Shannon.
Los compresores de datos se pueden clasificar en dos tipos: sin pérdida (losless) y con pérdida (lossy). Por ejemplo al comprimir un fichero de ordenador se usa un compresor sin pérdida pues al descomprimirlo se recupera exactamente el mismo archivo original, no se producen pérdidas de información. Mientras que con un compresor con pérdidas no se recupera el fichero tal como era el origen, una ejemplo son los ficheros de voz e imágenes, al ser nuestro oído y nuestra vista imperfectos no se percibe que la información ha sufrido pérdidas. Son habituales los formatos MP3, MPEG, AVI, etc.
La compresión sin pérdida de información tiene un límite máximo de compresión mientras que la compresión con pérdida no tiene un límite, se puede comprimir tanto como deseemos. Cuanto más comprimamos la información será peor la calidad obtenida, si llegamos a comprimir al 100 por 100 no se tendrían nada de información. Los compresores citados anteriormente se anunciaban del tipo sin pérdidas que son los que interesan en informática y que siempre tienen un límite de compresión.
Sustitución de código
Además de los algoritmos RLE existen las algoritmos de sustitución de códigos, incluso se pueden utilizar los dos conjuntamente. La sustitución de códigos para comprimir una cadena formada por varios mensajes enlanzados uno a continuación del otro, consiste en cambiar la forma en que se representa esa cadena. Para efectuar el cambio se ha de considerar la probabilidad con que se presenta cada parte de la cadena (cada mensaje).
Por ejemplo, se dispone de una fuente que emite cinco mensajes, del M1 al M5, con probabilidades 35%, 25%, 20%, 12% y 8% respectivamente y longitudes de 10, 7, 6, 4 y 3 caracteres respectivamente. Como el mensaje M1 aparece mucho (35% de las veces) y es muy largo (10 caracteres) y el mensaje M5 aparece poco (8% de las veces) y es corto (3 caracteres), una forma sencilla de comprimir sería intercambiar las representaciones de los mensajes:
se pueda hacer lo mismo intercambiando la representaciones de los mensajes M2 y M4:
El código más conocido, Morse, es de este tipo. La letra más frecuente es la e que se representa por un punto (la letra más frecuente es la más corta de representar). Sin embargo en castellano la e no en la más habitual, sino la a, algo análogo sucede con la w.
Según el ejemplo previo, se observa que unos mensajes disminuyen el espacio que ocupan (M1 y M2), otros lo aumentan (M4 y M5) y algunos no varían (M3). Los mensajes que ocupan más aparecen poco y los que ocupan menos aparecen mucho, resultando que el espacio total ocupado es menor tras la compresión.
Si la información es completamente aleatoria es decir que todos los mensajes tienen exactamente la misma probabilidad de aparición, no es posible hacer cambios de representación es decir no se puede comprimir la cadena porque aunque hiciéramos los intercambios no se ganaría nada. Se llega al límite de compresión cuando se ha eliminado la redundancia (utilizando RLE) y no se pueden hacer intercambio de representaciones. Este límite viene dado por la entropía de la cadena de deseamos comprimir y cualquier intento no tendrá ningún resultado.
En física se suele recurrir a cambios de dominio para facilitar determinadas operaciones por ejemplo pasar del dominio tiempo al dominio frecuencia. Se podría pensar que mediante una transformada de Fourier o de Haar sobre la cadena sin comprimir o la cadena comprimida sería posible lograr una mayor compresión. Esto es imposible, la teoría de la información se basa en la probabilidad y el modelo probabilístico incluyendo a las posibles transformaciones que se puedan hacer, porque el cambiar de dominio significa cambiar el modelo probabilista que usamos.
Conclusión
En cualquier proceso de compresión siempre se llega a una situación en que no se logra disminuir el tamaño final, incluso puede aumentarse, entonces se ha llegado al límite de compresión. Aunque las tecnologías usadas actualmente no siempre son óptimas, la publicidad de tecnologías con límites muy superiores a los actuales es muy probable que sean falsas. Si una tecnología de comprensión sin pérdidas afirma superar el límite de Shannon, no hay duda de que es falsa.
Referencias:
Códigos de compresión de la información. Diego Marco López, Jorge González Maestro. Universidad Valladolid.
Endlesscompression
Incredible Claims DataCompression.info
La imposibilidad del compresor infinito. Garcia Quiles, Pau. El Escéptico, 18, primavera 2005.
There´s no magic. Charles Bloom.
Experts Question Compression Breakthrough. Sam Costello. PCWorld, 11, 2002.
Compresión de datos. Diego Sevilla (Universidad de Murcia).
Es habitual encontrar en revistas de informática, ya sea especializadas o de divulgación, anuncios de empresas que aseguran haber superado el límite teórico de compresión de datos. Por ejemplo en Irlanda un estudiante de dieciséis años consiguió engañar a un jurado de doce personas al serle adjudicado el premio al “Joven Científico” del año 2002, por haber propuesto una navegador de internet llamado Xwebs, que supuestamente multiplicaba por cuatro la velocidad de navegación.
La empresa ZeoSync (Florida-EE.UU.) anunciaba en su página cinco tecnologías relacionadas con la compresión de datos: codificador, compresor, secuenciador, transformador de dominio y el conjunto de todos, logrando una compresión de 100 a 1. Pegasus Technologies afirmaba que podía guardar 1.28 gigaoctetos en un disquete de 3.5 pulgadas (con capacidad de 1.44 Moctetos) mediante su tecnología, patentada en Estados Unidos, HyperDrive. Web Technologies propone su compresor Datafiles/16 que lograba comprimir cualquier archivo mayor de 64 KB a un dieciseisavo de su tamaño. Otra tecnología patentada en Estados Unidos fue HyperSpace, que comprimía datos aleatorios, al igual que otro compresor Minc. La empresa Pixelon se aprovechó de la burbuja tecnológica para dilapidar 35 millones de dólares de los inversores en un supuesto compresor de vídeo y audio de propiedades casi mágicas. La realidad es que ninguno de esos compresores fue comercializado y estas empresas han desaparecido.
Un método sencillo de compresión consiste en sustituir la repeticiones de una letra por el número de veces que se repite por ejemplo se podría comprimir la siguiente secuencia:
AAAAAAAAAAAAAAABAAACDEEEEEECCCCBBBFTTTTWCCAAAAAJJJLLL
como:
15AB3ACD6E4C3BF4TW2C5A3J5K
lo que antes ocupaba 55 caracteres ahora sólo ocupa 26 es decir se ha logrado una disminución del 53%.
El sistema anterior es un ejemplo sencillo de una algoritmo de codificación por longitud de recorrido (RLE), básicamente consiste en eliminar lo que se repite.
Teoría de la información
La teoría de información es una rama de la teoría matemática de la probabilidad y la estadística que estudia la información y todo lo relacionado con ella: canales, compresión de datos, criptografía y temas relacionados. Su origen se debe al artículo "Una teoría matemática de la comunicación" publicado en 1948 por Claude Shannon.
Los compresores de datos se pueden clasificar en dos tipos: sin pérdida (losless) y con pérdida (lossy). Por ejemplo al comprimir un fichero de ordenador se usa un compresor sin pérdida pues al descomprimirlo se recupera exactamente el mismo archivo original, no se producen pérdidas de información. Mientras que con un compresor con pérdidas no se recupera el fichero tal como era el origen, una ejemplo son los ficheros de voz e imágenes, al ser nuestro oído y nuestra vista imperfectos no se percibe que la información ha sufrido pérdidas. Son habituales los formatos MP3, MPEG, AVI, etc.
La compresión sin pérdida de información tiene un límite máximo de compresión mientras que la compresión con pérdida no tiene un límite, se puede comprimir tanto como deseemos. Cuanto más comprimamos la información será peor la calidad obtenida, si llegamos a comprimir al 100 por 100 no se tendrían nada de información. Los compresores citados anteriormente se anunciaban del tipo sin pérdidas que son los que interesan en informática y que siempre tienen un límite de compresión.
Sustitución de código
Además de los algoritmos RLE existen las algoritmos de sustitución de códigos, incluso se pueden utilizar los dos conjuntamente. La sustitución de códigos para comprimir una cadena formada por varios mensajes enlanzados uno a continuación del otro, consiste en cambiar la forma en que se representa esa cadena. Para efectuar el cambio se ha de considerar la probabilidad con que se presenta cada parte de la cadena (cada mensaje).
Por ejemplo, se dispone de una fuente que emite cinco mensajes, del M1 al M5, con probabilidades 35%, 25%, 20%, 12% y 8% respectivamente y longitudes de 10, 7, 6, 4 y 3 caracteres respectivamente. Como el mensaje M1 aparece mucho (35% de las veces) y es muy largo (10 caracteres) y el mensaje M5 aparece poco (8% de las veces) y es corto (3 caracteres), una forma sencilla de comprimir sería intercambiar las representaciones de los mensajes:
se pueda hacer lo mismo intercambiando la representaciones de los mensajes M2 y M4:
El código más conocido, Morse, es de este tipo. La letra más frecuente es la e que se representa por un punto (la letra más frecuente es la más corta de representar). Sin embargo en castellano la e no en la más habitual, sino la a, algo análogo sucede con la w.
Según el ejemplo previo, se observa que unos mensajes disminuyen el espacio que ocupan (M1 y M2), otros lo aumentan (M4 y M5) y algunos no varían (M3). Los mensajes que ocupan más aparecen poco y los que ocupan menos aparecen mucho, resultando que el espacio total ocupado es menor tras la compresión.
Si la información es completamente aleatoria es decir que todos los mensajes tienen exactamente la misma probabilidad de aparición, no es posible hacer cambios de representación es decir no se puede comprimir la cadena porque aunque hiciéramos los intercambios no se ganaría nada. Se llega al límite de compresión cuando se ha eliminado la redundancia (utilizando RLE) y no se pueden hacer intercambio de representaciones. Este límite viene dado por la entropía de la cadena de deseamos comprimir y cualquier intento no tendrá ningún resultado.
En física se suele recurrir a cambios de dominio para facilitar determinadas operaciones por ejemplo pasar del dominio tiempo al dominio frecuencia. Se podría pensar que mediante una transformada de Fourier o de Haar sobre la cadena sin comprimir o la cadena comprimida sería posible lograr una mayor compresión. Esto es imposible, la teoría de la información se basa en la probabilidad y el modelo probabilístico incluyendo a las posibles transformaciones que se puedan hacer, porque el cambiar de dominio significa cambiar el modelo probabilista que usamos.
Conclusión
En cualquier proceso de compresión siempre se llega a una situación en que no se logra disminuir el tamaño final, incluso puede aumentarse, entonces se ha llegado al límite de compresión. Aunque las tecnologías usadas actualmente no siempre son óptimas, la publicidad de tecnologías con límites muy superiores a los actuales es muy probable que sean falsas. Si una tecnología de comprensión sin pérdidas afirma superar el límite de Shannon, no hay duda de que es falsa.
Referencias:
Códigos de compresión de la información. Diego Marco López, Jorge González Maestro. Universidad Valladolid.
Endlesscompression
Incredible Claims DataCompression.info
La imposibilidad del compresor infinito. Garcia Quiles, Pau. El Escéptico, 18, primavera 2005.
There´s no magic. Charles Bloom.
Experts Question Compression Breakthrough. Sam Costello. PCWorld, 11, 2002.
Compresión de datos. Diego Sevilla (Universidad de Murcia).