La magia de la compresión - ALIPSO.COM: Monografías, resúmenes, biografias y tesis gratis.
Aprende sobre marketing online, desarrollo de sitios web gratis en Youtube
Suscribite para recibir notificaciones de nuevos videos:
Viernes 04 de Diciembre de 2020 |
 

La magia de la compresión

Imprimir Recomendar a un amigo Recordarme el recurso

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
Categoría: Apuntes y Monografías > Ciencia y tecnología >
Material educativo de Alipso relacionado con magia compresión
  • Biografia y vida de El gran Magiar conde de Sárvár István Széchenyi: Breve Biografia de El gran Magiar conde de Sárvár István Széchenyi
  • La magia de la 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)

    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.


    Votar

    Ingresar una calificación para del 1 al 10, siendo 10 el máximo puntaje.

    Para que la votación no tenga fraude, solo se podrá votar una vez este recurso.

    Comentarios de los usuarios


    Agregar un comentario:


    Nombre y apellido:

    E-Mail:

    Asunto:

    Opinión:



    Aún no hay comentarios para este recurso.
     
    Sobre ALIPSO.COM

    Monografias, Exámenes, Universidades, Terciarios, Carreras, Cursos, Donde Estudiar, Que Estudiar y más: Desde 1999 brindamos a los estudiantes y docentes un lugar para publicar contenido educativo y nutrirse del conocimiento.

    Contacto »
    Contacto

    Teléfono: +54 (011) 3535-7242
    Email:

    Formulario de Contacto Online »