Página principal

Introducción Historia de la compresión


Descargar 20.99 Kb.
Fecha de conversión18.07.2016
Tamaño20.99 Kb.

Introducción




Historia de la compresión

La historia de la compresión se remonta a los años 1960, en el que diversos estudios sobre la teoría de la información buscaban el codificar los símbolos de la manera más eficiente posible.


Todo y queAdemás de esto, hubieron unDel conjunto de trabajos previos que marcaron la diferencia que merece la pena destacardestaca un trabajo aparecido en los.
Sobre los años ’50 (1948) se produce uno de los evento muy importantes en la historia de la comunicación, que fue la aparición de un trabajo de Claude Shannon , sobre la “Teoría sobre la Comunicación” , donde se hace uninicia el desarrollo de la “Teoría de la Información”. Este trabajo sería el más relevante en el campo de las telecomunicaciones.
El estudio reflejaba un límite mínimo en la codificación de la información, apareciendo entonces el concepto de Entropía de la Información, en el cual quedaba reflejado que el coste mínimo en bits de la comunicación de una cadena de caracteres es

donde es la el número mínimo de bits necesario para que se utilizan en codificar un símbolo ( carácter ) y la frecuencia de apariciones en un texto.
La importancia de este enorme estudio reside en el hecho de que cuantificaba el número mínimo de bits necesario para codificar un mensaje (cadena de texto).
Inicialmente el planteamiento fue conseguir enviando los símbolos codificados en una tira de bits., surgeSurge a partir de éston entonces la aparición del el código ASCII que utilizamos hoy en día.

Aquí todos los símbolos ocupanban el mismo espacio (lo que entendemos por un carácter char en el lenguaje de programación C).


Desde éste momento, comienza Surgió entonces una carrera por desarrollar un algoritmo que consigaguiese el punto teórico punto de máxima eficiencia en la codificación de mensajes ( strings o cadenas de caracteres).

Un estudiante universitario del MIT llamado David Huffman en el año 1954 realizó un trabajo para su asignatura de “Tería de la Información” que marcó la diferencia. Este trabajo acabó siendo el conocido algoritmo sobre compresión de la Información, “Algoritmo de la Codificación de Huffman”.



Algoritmo de compresión de huffman

La base del algoritmo de Huffman es crear un árbol de símbolos basados en la probabilidad de los símbolos (caracteres).


Las fases a seguir consisten en:

  • Crear una tabla vertical de símbolos, ordenándolos por orden decreciente en función de la frecuencia de aparición de estos en el texto..

  • El objetivo es formar un árbol binario sobre la misma tabla. Un árbol binario es una estructura, similar a un árbol invertido, en la que cada nodo tiene dos ramas, y así sucesivamente, hasta llegar a las hojas, las cuales no tendrán ramas. . Se construye el árbol, desde las hojas hacia la raíz. Cada “hoja” que equivale a un símbolo, tiene asociada una probabilidad. Se calcula la probabilidad de cada nodo raíz de cada subárbol, sumando las probabilidades de sus dos nodos hijos. juntando los símbolos de probabilidad más baja en cada nivel, haciendo que la probabilidad de un nodo sea igual a la probabilidad de la suma de los nodos mezclados .



  • Cada rama tendrá asociado un 0 (rama izquierda) o un 1 (rama derecha). Cada Un camino camino de cada nodo se nombra entonces con un bit ( un camino tendrá o un 0 o un 1). Laes la secuencia de bits necesaria para moverse desde la raiz del arbol hasta una hoja (símbolo) al atravesar los diferentes nodos (caminado por las ramas) que la codifican. Dicho camino, será la codificación de Huffman.

En el ejemplo siguiente se ver un árbol de frecuencia de uso de cuatro símbolos ( un alfabeto reducido de cuatro símbolos). Como se puede ver la diferencia de frecuencias de uso de los diferentes bits da lugar a codificaciones con diferente número de bits. Mientras que con una codificación fija necesitaríamos dos bits por cada símbolo para simbolizar los cuatro símbolos, con esta forma de codificación necesitaremos 1,2 o 3 bits en función. La entropía o la cantidad necesaria para codificar una secuencia de símbolos con esa frecuencia de cada uno de los símbolos es 1,75 bits por símbolo.


Figura 1
Queda por resaltar entonces que este algoritmo tiene su base en una tabla estática de codificación estática de símbolos basada en la longitud variable.


Dicha tabla puede ser constrúida en forma estática, o bien será construida de forma estática para una secuencia de información a enviar o bien para una secuencia de información a enviar (semidinámica) o por último variando esta dinámicamente a medida que varía las probabilidades de los símbolos.
En todos los casos debe contemplarse que la tabla de compresión (codicación) deberá ser conocida por el descompresor, o bien incluida en la secuencia de información comprimida.
Por ejemplo:
Un fichero de texto de tamaño N caracteres tendrá en su origen 8*N bits se convertirá en:

  • k*8*N donde k será el ratio de compresión de la información

  • T , donde T será el tamaño de la tabla de codificación


Historia del uso del Algoritmo de compresión de Huffman

La aplicación propuesta en este laboratorio es la base actual de un gran número de aplicaciones basadas en la compresión y es fundamental como base para partes de los nuevos algoritmos de compresión más sofisticados.


Tras la aparición del trabajo de Huffman aparecieron dos optimizaciones a este algoritmo:

  • Codificación de Huffman Adaptativa basada en dinámicamente cambiar la codificación de las palabras de acuerdo con cambios en la frecuencia de aparición de los símbolos

  • Codificación de Huffman Extendida, que puede codificar grupos de símbolos más allá de simples símbolos.

Existen una gran cantidad de compresores comerciales basados en el algoritmo de Huffman de ahí la gran importancia de este algoritmo. Los podemos distinguir en dos tipos básicos:



  • Los algoritmos que no están sometidos a pérdidas de información o también llamados losslessy, cuyo uso habitual es en la compresión de datos. Tenemos como ejemplos de este grupo pkZIP,ZIP,lha,gz, zoo , arj, etc…

  • Los algoritmos sometidos a pérdidas o degradaciones o también llamados lossysless, cuyo ámbito de aplicación es el de la compresión en audio, video e imagen como por ejemplo son el caso de los formatos de compresión JPEG , MPEG , DIVx , MP3 , etc…

Proyecto




Descripción del proyecto


El proyecto que realizará en el laboratorio es una versión reducida del Compresor basado en la Codificación de Huffman.
Como se ha explicado en el punto anterior la base del algoritmo de Huffman se encuentra en la obtención de la tabla de codificación de los símbolos (caracteres) como en la Figura 1.

Para ello se realizarán las siguientes Fases :



  • Calculo de las frecuencias de una secuencia de información (sesión 1 del proyecto-Sesión 3 laboratorio)

  • Ordenación de la tabla de frecuencias y realización de grupos en función de dicho orden . Generación de tabla de codificación de grupos. Calcular tabla de compresión / descompresión ( Sesión 2 del proyecto)

  • Compresión de una secuencia de caracteres ( Sesión 3-4 proyecto)

  • Cálculo deGeneración de la tabla de frecuencias partiendo de fichero (Sesión 4 proyecto)

  • Guardar/Cargar tabla de frecuencias de fichero (Sesión 4 proyecto)



Detalle del algoritmo de compresión propuesto





  1. Obtención de la frecuencia de aparición de los caracteres

    1. Rellenaremos una tabla en la que tendremos un campo que nos indicará cuantas veces aparece un carácter en una secuencia de caracteres

    2. Otros campos servirán por ejemplo para nos indicará indicar que carácter se encuentra en esa posición. I, inicialmente la tabla está ordenada, como estará en ordencon lo que cada carácter estará en la posición que le corresponde. Tendremos entonces una tabla con tantas posiciones como caracteres tenemostengamos.

  2. Ordenación de la tabla de frecuencia de mayor a menor

    1. Una vez ordenada la tabla podremos encontrar en el campo se indica que carácter ocupa esa posición en el orden (según la frecuencia de aparición)

  3. Realización de grupos basados en la posición que ocupa en la tabla de frecuencias ordenada

    1. Se realizarán cuatro grupos. Cada grupo representará un grupo de codificación y por consiguiente un tamaño diferente para cada grupo

      1. Grupo4. Simboliza el grupo de los ocho caracteres más frecuentes que se codificará como 0xxx ( xxx simbolizan los tres bits que codificarán los 8 posibles caracteres de ese grupo). Un carácter de este grupo requerirán entonces 4 bits para ser codificado.

      2. Grupo6. Agrupa los 16 caracteres siguientes. Representado por 10xxxx (4 bits codifican cualquiera de los 16 caracteres pertenecientes al grupo). Tiene un tamaño efectivo de 6 bits

      3. Grupo78. Agrupa al grupo formado por 32 caracteres siguientes al grupo 6. Representado por 110xxxxx. Tiene un tamaño efectivo de 7 bits.

      4. RESTO. Agrupa a los valores que no quedan recogidos por los

    2. Se asignará entonces un prefijo de grupo de diferente tamaño en función del grupo al que se pertenezca :

      1. 0 Grupo4

      2. 10 Grupo6

      3. 110 Grupo8

      4. 1110Resto

  4. Codificación de cada carácter según el anterior esquema de grupos

    1. Cada carácter pertenecerá a un grupo ( prefijo)

    2. Dentro de cada grupo tendrá una posición que acabará de codificar el resto del número

  5. Se añadirá cada carácter a la tira de caracteres resultado



Referencias

Timothy C. Bell, John G. Cleary, and Ian H. Witten. Text Compression. Prentice Hall, 1990


James A. Storer. Data Compression: Methods and Theory. Computer Science Press, Rockville, MD., 1988.
Darrel Hankerson, Greg A. Harris, Peter D. Johnson :Introduction to Information Theory and Data Compression, Second Edition,CHAPMAN&HALL


La base de datos está protegida por derechos de autor ©espanito.com 2016
enviar mensaje