La magia de la compresión
La informática tiene muchos temas interesantes. Desarrollos muy ingeniosos soportados por una fuerte base matemática nos permiten tareas muy diversas. Uno de los temas más intersantes de esta disciplina es la compresión.
La compresión es la operación por la que se representa una conjunto de datos con menos cantidad de datos. Esto suena poco lógico y hasta en cierto sentido, “mágico”
Este apunte fue enviado por su autor en formato DOC (Word).
Para poder visualizarlo correctamente (con imágenes, tablas, etc) haga click aquí o aquí si desea abrirla en ventana nueva.
Técnicas
de compresión
En esta secciones plantearemos
las principales ideas que posibilitan desarrollar algoritmos de compresión. No
es exactamente la clasificación que usan los textos de compresión, pero
intentamos clasificarlas de acuerdo a su enfoque.
Basadas en repeticiones de información (RLE)
Posiblemente esta sea la técnica más primitiva, porque se basa en
codificar un código repetido varias veces con una forma similar a “X veces Y
código”. Constituye un algoritmo simple pero que en ciertos archivos puede
ofrecer altos ratios de compresión. Por desgracia, en la mayoría de los
formatos son muy raras tantas repeticiones de un mismo código.
Un ejemplo de esta técnica es el algoritmo RLE (Run length encoding)
que significa “Codificación de longitud de recorrido”.
Codificación de Huffman
Una técnica muy poderosa que consiste en asignarles códigos de bits
más cortos a los datos que mayor frecuencia de aparición tienen y códigos más
largos a los que aparecen con menos regularidad. Es una técnica muy creativa y
ofrece altos ratios de compresión. Para realizar sus procesos se emplean
árboles binarios. Se comienza tenienndo todos los símbolos del archivo junto
con sus frecuencias. Se escojen los 2 datos con menor frecuencia y se los une.
El padre de ambos datos será la suma de sus frecuencias. Luego se toma este
árbol con 2 hijos y se le agrega la menor frecuencia siguiente. Repetimos el
proceso hasta que llegamos al dato con mayor frecuencia. Para obtener el código
de Huffman (serie de bits que representan un dato) se recorre el árbol desde el
nodo hijo hasta la raíz del árbol. Dependiendo de la rama que tomemos agregamos
un 0 o un 1 al código de Huffman. Si es rama derecha asignamos un 1 y para la
rama izquierda un 0. Una característica partícular de estos códigos es que dada
una serie de bits es posible determinar si debemos continuar leyendo código o
nos debemos detener. Es un conepto difícil, veámoslo con un ejemplo: no habrá
un código 001 y otro 00101, porque los 3 primeros bits se repiten. Tendremos
uno u otro, de forma que no se repitan los primeros bits.
Los códidos de bits se almacenan
en forma de diccionario, junto con sus frecuencias.
Con diccionarios
Esta técnica es útil en archivos con contienen gran redundancia de
datos.
A medida que se leen se carga el
diccionario. Luego, si un código en una posición P se presenta nuevamente se
almacena esta posición dentro del diccionario.
Veamos
un ejemplo: si tenemos un diccionario con 16536
entradas
(16 bits) el promedio de longitud de los datos
que
almacene debe ser mayor a 16 bits (2 bytes), porque
de
lo contrario no habrá compresión.
Cuando
hay mucha entropía en el archivo a comprimir (los
datos
están muy desordenados) esta técnica reduce su
performance
de compresión.
Una
alternativa a los diccionarios es la codificación LZ
(Lempel-Ziv),
que no los usa y en vez de éstos almacena
un
código con la cantidad de retrocesos que se deben
efectuar
para encontrar el mismo código y la cantidad de
datos
a tomar en consideración. Podríamos decir que es
una
técnica perfeccionada basada en repeticiones de
Hay
varias versiones del algoritmo LZ, como LZW, que es
usada
en el formato PDF.
Codificación aritmética
La codificación aritmética es un
algoritmo muy eficiente en términos de ratio de compresión logrado. En teoría
está casi en el umbral de Shannon, por lo que casi no podría ser mejor. Debemos
remarcar que es una técnica patentada, y para utilizarla se deben pagar los
royalties a sus propietarios.
En la codificación aritmética comenzamos con un intervalo continuo de
0 a 1. No se usan diccionarios. En vez de ello se seleccionan los códigos según
su frecuencia de aparición. Para el primer código vamos a tener una frecuencia
asociada. Luego multiplicamos esta frecuencia por 1 (el intervalo va de 0 a 1).
Nos queda un número más pequeño, de 0 a f1. Luego obtenemos x1=(f1-0)*f1. A ese
número le sumamos f1*f2. Y repetimos el proceso con las frecuencias restantes.
En otras palabras, vamos reduciendo el rango 0..1 al multiplicar sucesivas
veces por las frecuencias, siempre comenzando desde el último límite inferior
(no desde 0) para tomar el rango. Una vez hecho este proceso nos queda un
límite inferior y una tamaño de rango. En general lo podemos representar con
enteros pequeños. Por ejemplo, tomamos los dígitos del límite inferior
fraccionario y del incremento. Otra alternativa es multiplicar por un valor
entero grando pero que ocupe menos bits que el código original.
Técnicas predictivas
Las técnicas de compresión predictivas constituyen un
concepto avanzado dentro del ambiente de la compresión.
Predecir significa estimar
qué valores serán
los
próximos en base a análisis del conjunto de datos a
comprimir.
Existen múltiples enfoques en esta técnica, nosotros
harémos hincapié sólo en uno de ellos. De más está decir
que el desarrollo de nuevas opciones está abierto a
quien lo desee, no hace falta trabajar para una gran
empresa para ser investigador.
La predicción consiste en que, dado un conjunto de
datos, se estima cuáles son los valores más probables
que estarán luego de cada uno de éstos.
Nuestro enfoque produce compresión sin pérdidas.
Si hay X datos posibles que le sigan a un dato dado,
sólo se necesitarán unos pocos bits para indicar qué
opción se elige.
No hay seguridades, sólo
probabilidades. Esta técnica funciona bien cuando hay
redundancia en los datos y niveles bajos de entropía. El
tamaño de los datos se elige de la mejor manera para que
la predicción sea la mejor posible.
No desesperen, aquí va un ejemplo: Supongamos que
tenemos los bytes
100_30_25_180_100_100_30_180_25_100_30_180_100
Al 100 le siguen: 30, 100, 30, 30
Al 30 le siguen: 25, 180, 180
Al 25 le siguen: 180, 100
Al 180 le siguen: 100, 25, 100
De estas opciones los únicos que presentan varias veces
el mismo dato son el 100, el 30 y el 180.
El 25 no se le almacena en el “diccionario”, pero los
otros sí.
Cuando tenemos el valor 100, luego de éste sólo
almacenamos
un valor binario 0 o 1. El 0 representa al
30
y el 1 al 100.
Cuando
tenemos el 30, luego de éste almacenamos un 0 o
un
1. El 0 es 25 y el 1 es 180.
Además
de estas codificaciones debemos tener un vector
binario
que nos indique si el dato de cada posición se
predice
o se toma como está almacenado.
Si eres de esas personas que disfrutan de una sintética
enunciación
matemática, dejando de lado las palabras,
podemos
entender la compresión por predicción explicada
arriba
de la siguiente manera:
Sea
un conjunto de datos D, tal que Di denota el i-esimo
dato, y cada Di tiene una longitud L(Di).
Ei
es el conjunto de datos que le siguen a Di en todo el
archivo.
L(Ei) es la longitud en bits del conjunto Ei.
Definimos una función contadora C(), tal que
c() = 1 si Eij = Eik
c() = 0 si Eij ≠ Eik para todos j>=0,
k>=1, j≠k y j>k. Di se elige de tal manera que C() sea
lo mayor posible. De esta forma nos aseguramos que se repitan la mayor cantidad
de veces los datos de Ei.
Transformadas
Dentro de esta categoría
encontramos las series de Fourier y la “Transformada discreta del coseno”
(DCT). Es posible representar la secuencia de datos con ondas periódicas,
aunque en general debemos tolerar cierta pérdida de información. Esto ocurre ya
que es poco probable que las ondas se adapten exactamente a la “forma” de
nuestros datos. Sin embargo, se logran muy buenos resultados en imágenes,
videos y sonidos. Una vez que aplicamos nuestra transformadas obtenemos un
conjunto reducido de datos que representan con pérdida los originales. A su
vez, pueden ser comprimidos con Huffman, compresión aritmética, etc. logrando
aún mejores resultados.
En transformadas no sólo tenemos
las ondas: hay muchos tipos de transformaciones, como ser lógicas, aritméticas,
conjuntistas, etc. Muchas se pueden combinar entre sí para lograr ciertos
niveles de redundancia y ordenes específicos.
Por wavelets
Se ha descubierto que es posible
representar una secuencia numérica combinando distintas ondas, cada una con una
amplitud (tamaño vertical de la onda), frecuencia (ciclos por x) y fase
(corrimiento en x) diferentes. Esta idea es ampliamente usada con
transformaciones de Fourier, transformada discreta del coseno, etc... La
compresión en estos casos será con pérdida, dependiendo de cuanta información
almacenemos sobre las ondas que representan el conjunto de datos a comprimir.
Sin embargo, para secuencias de video, sonido o imágenes no siempre es
necesaria un representación exacta de los datos.
Extendiendo la idea de las ondas
sinoidales, podemos empezar a buscar otras ondas más “exóticas”, que sean o no
simétricas con respecto a un punto x. Las ondas se las puede definir
analíticamente o en un “diccionario”. Luego podremos representar una serie de
datos con una de estas ondas o combinaciones específicas de ellas. Hay muchas
combinaciones posibles que se logran de realizar operaciones aritméticas con
estas, desplazamientos en las coordenadas, o transformaciones arbitrarias. Un
ejemplo de formato que usa tecnología de wavelets es JPG2000, la evolución del
JPG estándar que permite grandes ratios de compresión con calidades muy buenas
(evitando muchas veces el artifact de cuadriculado debido a la transformada
discreta del coseno).
Basada en contexto
La compresión basada en contexto,
al igual que las técnicas predictivas, forma parte de un aspecto avanzado en
algoritmos de compresión.
Un algoritmo de compresión basada
en contexto comprimirá los datos de diferente manera según el entorno en el que
se encuentren estos. Los datos comprimidos dependen del ambiente en el que se
encuentran, o dicho en otras palabras, de los datos que tienen alrededor.
Haciendo uso de parámetros adecuados según el entorno se pueden lograr
compresiones buenas; y en caso de no lograrlas, se podrían obtener
transformaciones aptas para aplicar otro algoritmo de compresión.
Algunos formatos con compresión
De datos (sin pérdidas): ZIP, RAR, 7zip, CAB,
Gzip, KGB De
imágenes: GIF, JPG, JPG2000, PNG, GIF, TIFF. De video: DivX, H.264, DivX, Xvid,
AVI, MPG, WMV. De sonido: MP3, WMA, OGG, FLAC.
Compresión recursiva
La compresión recursiva es un
concepto teórico. Aún no hay algoritmos conocidos que la logren.
La compresión recursiva significa
poder comprimir un conjunto de datos reiteradas veces por medio de
transformaciones que permitan generar redundancia y un cierto órden a partir de
datos ya comprimidos. Recordemos que esta clase de archivos presentan un alto
nivel de entropía y poca reduncia; todos los bytes tienen aproximadamente la misma frecuencia de aparición. Se
desconoce si existen dichos algoritmos, pero es un tema en constante
investigación.
Aunque se pueda lograr esta
técnica de compresión, siempre existirá un límite desde el que el archivo no
podrá ser nuevamente comprimido. Pero lograr 3 o 4 iteraciones de compresión sería un logro importantísimo. Recordemos
también que existe el umbral de Shannon. Sin embargo, puede que el “truco” de
la compresión recursiva no esté en el algoritmo de compresión propiamente
dicho, sino en las operaciones de transformación de los datos. Con estas
operaciones sería posible transformar un conjunto de datos no redundantes y
alta entropía en datos con cierta redundancia y un órden particular. Otro
aspecto que debemos considerar es que estos algorimtos requerirían mucha
memoria y procesamiento ya que quizás también se basen en FUERZA BRUTA y
técnicas de inteligencia artificial.
Como ven, hay un mundo en la
compresión y aunque esta última técnica quizás sea una utopía lejana, siempre
existe la posibilidad de desarrollar algoritmos de compresión más potentes y
eficaces.
Actualmente existe un algoritmo llamado PAQ6 que logra
comprimir algunos archivos MP3, JPG, etc. Y aclaramos
que estos ya se encuentran comprimidos. Por desgracia
consume mucha memoria y tiempo de procesamiento.
Según pudimos observar en su código fuente (es de código
abierto) es un algoritmo MUY COMPLEJO, basado en
“codificación aritmética predictiva” y dependiente del
contexto.
Un programa que lo implementa es “KGB Archiver”.
Con esto finaliza nuestra breve
síntesis de compresión. Hemos visto las diferentes técnicas con un enfoque algo
distinto al de los libros especializados en la materia. Nos concentramos en
destacar las ideas “base”. Pero el campo está abierto a combinarlas de la mejor
manera para lograr que un circo entero quepa en una diminuta cajita musical.
Autor:
Ramix (Ramiro A. Gómez)
Este apunte fue enviado por su autor en formato DOC (Word).
Para poder visualizarlo correctamente (con imágenes, tablas, etc) haga click aquí o aquí si desea abrirla en ventana nueva.
Monografías
Este apunte fue enviado por su autor en formato DOC (Word).
Para poder visualizarlo correctamente (con imágenes, tablas, etc) 
