Universidad Nacional Autónoma de México
Dirección General de Servicios de Cómputo Académico
Año 7 Núm. 74, Publicación Mensual, 27 de Noviembre de 2008

ARTÍCULOS

 

Año 5, Número 53, Octubre de 2006

Compresión de datos:
la importancia de no usar tantos bits

José Fabián Romo Zamudio

 

El nivel de compresión, es decir, qué tanto se reduce el tamaño de los archivos, depende de varios factores tales como el tamaño y tipo de archivo del que se trate, y el algoritmo o esquema de compresión.

Los discos duros con gigabytes de capacidad son comunes en las computadoras de escritorio. Lejanos están los días en los que sólo se usaba un disco flexible con poco más de un megabyte de espacio, o aquellos discos duros de pocas decenas de megabytes. Los discos externos y los internos de las computadoras de escritorio actuales cumplen con la difícil misión de almacenar, ya no sólo archivos de textos e imágenes simples, sino que han incrementado su tamaño en buena medida por las necesidades de almacenamiento de audio y video de alta calidad.

Sin embargo, aun con esas unidades tan densas, en ocasiones es necesario compactar los archivos. Más aún: la audioconferencia, videoconferencia, comunicación por celular, etcétera, son procesos que implican compresiones y descompresiones. Tomamos una foto con la cámara digital y no consideramos que un procesador y un programa, en fracciones de segundo, discriminan entre bits relevantes y otros que no lo son tanto. El proceso de compactación puede parecer “truco de magia”, pero tiene fundamento en algoritmos matemáticos que reducen la repetición de datos, pudiendo así el usuario almacenar más información en menos espacio o transmitirla en un ancho de banda reducido.

Fundamentos de la compresión

En un documento de 1948 titulado “Una teoría matemática de la comunicación”, Claude E. Shannon estableció las bases de la compresión de datos. Shannon definió que existe un límite, llamado nivel de entropía e identificado como H, cuyo valor depende de la información original, esto es: de la naturaleza estadística de los datos o mejor dicho de cómo están distribuidos estos datos. Shannon describió que toda fuente de información digital puede comprimirse sin pérdida de datos con un valor cercano al límite H, pero es matemáticamente imposible mejorar ese límite.

Para entender lo anterior, analicemos la siguiente frase, en donde se encuentran varias repeticiones de palabras:

“No preguntes qué puede hacer tu país por ti, sino qué puedes hacer tú por tu país”

En total, esta cita de John F. Kennedy consta de 17 palabras y 16 espacios. Si consideramos que cada carácter, letra o símbolo de puntuación equivale a una unidad de memoria en la computadora llamada byte, en suma, la frase incluyendo las comillas, consta de 83 bytes. Pero, también, es claro ver que existen muchas redundancias. Por ejemplo: “puede” aparecer dos veces, “país” dos veces, “tu” dos veces, “por” dos veces.

Una forma básica de comprimir la información consiste en el algoritmo LZ basado en un diccionario. LZ se refiere a Lempel y Ziv, los creadores del algoritmo –presente en el programa “compress”– del sistema operativo UNIX. Su funcionamiento consiste en identificar las repeticiones como una lista numerada. El diccionario de repeticiones podría verse así:

1 qué
2 puede
3 hacer
4 tu
5 país
6 por

La frase entonces se podría leer, de manera comprimida por el algoritmo LZ como:

“No preguntes 1 2 3 4 5 6 ti, sino 1 puedes 3 tú 6 4 5”

Este es uno de los métodos más sencillos de compresión de información. Claro está que no sólo se debe almacenar la “frase” con letras y números como se acaba de anotar, sino también el diccionario o catálogo de repeticiones, de tal forma que sea fácil reconstruir la información original. Si contamos los bytes del catálogo de repeticiones y la frase, tal vez no hayamos reducido mucho el tamaño, pero es fácil inferir que la reducción es considerable en conjuntos de datos más grandes, como un documento de varias páginas o todo un libro.

Cuando la computadora comprime un archivo con la ayuda de un programa, no lo hace como en el ejemplo anterior. Los programas para compresión buscan la repetición de patrones en el archivo original, no de palabras o frases en el sentido humano del término. Un algoritmo de compresión es más eficiente, en tanto sea más capaz de detectar esos patrones de repetición lo que, por supuesto, implica mayor procesamiento por parte de la computadora para analizar el archivo que se está comprimiendo.

El nivel de compresión, es decir, qué tanto se reduce el tamaño de los archivos, depende de varios factores tales como el tamaño y tipo de archivo del que se trate, y el algoritmo o esquema de compresión. Por ejemplo, los archivos con mejores niveles de compresión son los de tipo texto, fundamentalmente porque los idiomas humanos poseen altos índices de repetición de patrones o palabras, construcciones gramaticales y conjugaciones. Por el contrario, otro tipo de archivos que contienen información que rara vez se repite, como imágenes o archivos de audio, son menos propicios para la compresión, ya sea por los pocos patrones repetidos o porque su formato ya incluye una cierta compresión, como es el caso de los archivos gráficos JPEG y los de audio MP3. Todos estos formatos son más eficientes conforme el algoritmo de compresión es más sofisticado.

En términos de la teoría de Shannon existen dos grupos principales de algoritmos de compresión, tales como:

1. Compresión sin pérdida (lossless). Estos algoritmos tienen por objetivo reconstruir la información original fielmente al descomprimir el archivo, sin una sola pérdida de datos. La reducción del tamaño del archivo es menor si se compara con otros esquemas de compresión, siendo el nivel de compresión muy cercano al valor H definido por Shannon, quien también estableció cinco órdenes de H, caracterizadas por la naturaleza de la información y la probabilidad de ocurrencia de un carácter en función de los demás. De esta forma, en el Modelo de Orden Cero en la teoría de Shannon, los caracteres son estadísticamente independientes unos de otros, y cada símbolo o letra es igualmente probable de aparecer en un archivo. Para idiomas como el castellano, los archivos de texto que se compriman en un Orden Cero de la variable H tendrán el siguiente valor:

H = log2 m bits/caracter

Siendo m el total de caracteres y o símbolos posibles. Por ejemplo: para m=27, H tiene un valor de 4.75 bits por cada carácter. Las compresiones de Orden Cinco llegan a niveles H de 2.33 bits por carácter, como es el caso de los archivos de texto.

2. Compresión con poca pérdida (lossy). Con estos programas se elimina lo que se consideran bits innecesarios, creando una aproximación matemáticamente suficiente. Se usan en la compresión de imágenes, donde una excesiva cantidad de datos que representen colores y tonalidades no siempre es necesaria para una buena visualización. Estos esquemas de compresión se apoyan en el análisis de la distorsión, una entidad matemática que define puntualmente qué tan cercana es la aproximación al original. La videoconferencia y la audioconferencia, así como los archivos MP3 de audio o los MPEG-4 de video son buenos ejemplos de compresiones con pérdida, ya que al momento de descomprimir la información no se tienen todos los datos originales, lo que explica imágenes “cuadriculadas” y pistas de audio con menos fidelidad.

Archivos compactados

Además del método de compresión, existen diversos formatos de archivos, dependiendo del tipo de dato que se esté compactando. Las principales clasificaciones son los formatos de aplicación general, los orientados a imágenes, los de audio y los de video.

En el caso de la compresión de archivos de cualquier tipo existe el formato BZIP2, de uso libre y que emplea la transformación Burrows-Wheeler, donde un bloque de datos se convierte en otro que refleja la repetición de ciertas combinaciones. Por su parte, el formato GZIP, también de uso libre, se apoya en el algoritmo LZ y el llamado Huffman, donde se considera el número de ocurrencias de un símbolo en una estructura jerárquica. Una versión similar corresponde al formato ZIP, desarrollado por la empresa PKWARE e implementado en los programas PKzip y PKunzip. Algunos otros programas que realizan este tipo de compresión son:

Programa
Extensión de archivo
Sistema operativo
WinZIP
.zip
Windows
WinRAR
.rar
Windows
PKzip
.zip
Windows
ARJ
.arj
Windows
Gzip
.gz
Linux
Stuffit
.sit
Mac OS

Para el caso de los archivos de audio, el formato de compresión más popular es MP3, que incluye también una codificación de la información original que se registra como modulación de pulsos. Para las imágenes se emplean los formatos GIF –compresión sin pérdida pero reducidos colores– y JPEG –compresión por transformaciones y Huffman–. Y en el video, los más extendidos son los formatos MPEG-1, MPEG-2 y MPEG-4.

Junto con el proceso de compresión, todo programa o algoritmo debe considerar la descompresión, es decir: regresar a la versión original de los datos, o al menos, a lo más cercano posible. Un archivo compactado no se puede editar directamente por la aplicación de origen, por ejemplo, un documento realizado en Microsoft Word que se ha compactado, no puede abrirse directamente en la aplicación original sin antes descompactarse. Ese es el precio a pagar por la compresión: se obtiene más espacio de almacenamiento, pero se pierde rapidez para la modificación de los archivos. Por ello, se recomienda compactar sólo aquellos archivos que no sean de uso constante o bien, los que se deban transferir a través de Internet u otro tipo de redes.

Para mayor información

Shannon, C.E. “A mathematical theory of communication”. Bell System Technical Journal, 1948.
http://www.binaryessence.com

Inicio | Contacto |