|
|
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”
Agregado: 06 de JULIO de 2008 (Por Ramiro Gomez) | Palabras: 2811 | Votar |
1 voto 
| Promedio: 10
|
Sin comentarios | Agregar Comentario | Promedio: 10
Categoría: Apuntes y Monografías > Ciencia y tecnología >
Material educativo de Alipso relacionado con magia compresión
Enlaces externos relacionados con magia compresión
Autor: Ramiro Gomez (ramiagomez@yahoo.com.ar)
 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
información.
Ej: ADA012563ADAtt0125 -> ADA01256 (8,3) tt (11,4)
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)
