Algoritmo De Compresion De Huffman

PRÁCTICA 3

Algoritmo de
compresión
de
Huffman

1. Introducción
El algoritmo de Huffman es un algoritmo de compresión de datos que se utiliza para la compresión o encriptación de datos mediante el estudio de la frecuencia de aparición de caracteres. Fue desarrollado por el norteamericano David Albert Huffman en 1952 mientras hacía el doctorado en el MIT.
Este algoritmo toma unalfabeto de n símbolos, junto con sus frecuencias de aparición, y asigna un código de longitud variable a cada uno de los elementos de ese alfabeto en función de sus frecuencias.
Se trata de un codificador óptimo (no existe otro código instantáneo con una longitud media menor), por lo que puede ser utilizado para la compresión de ficheros.
La capacidad de compresión de la información se debe a queasigna los códigos de menor longitud a aquellos símbolos que aparecen con una probabilidad mayor, consiguiendo con ello la reducción de la longitud media de las palabras código asociadas a los mensajes.
2. Descripción
El algoritmo consiste en la creación de un árbol binario que tiene cada uno de los símbolos por hoja, y construido de tal forma que siguiéndolo desde la raíz hasta cada una desus hojas se obtiene el código Huffman asociado.
Los pasos a seguir para la creación del árbol son:
1. Se crean varios árboles, uno por cada uno de los símbolos del alfabeto a comprimir, consistiendo cada uno de los árboles en un nodo sin hijos, y etiquetando cada uno con su símbolo asociado y su frecuencia de aparición.
2. Se ordenan los árboles en orden decreciente de probabilidades.3. Se toman los dos últimos (los dos árboles con la menor probabilidad), asignándoles un 1 al de menor probabilidad y un cero al de mayor probabilidad, y se unen creando un nuevo árbol. La etiqueta de la raíz será la suma de las frecuencias de las raíces de los dos árboles, y cada uno de ellos será un hijo del nuevo árbol.
4. Se repite el paso 3 hasta que sólo quede un árbol.
Una vez quese ha terminado este proceso, podemos obtener el código asociado a un símbolo procediendo del siguiente modo:
1. Comenzar con un código vacío.
2. Iniciar el recorrido del árbol en la hoja asociada al símbolo.
3. Comenzar un recorrido del árbol hacia arriba.
4. Cada vez que se suba un nivel, añadir al código la etiqueta de la rama que se ha recorrido.
5. Tras llegar a la raíz,invertir el código.
El resultado es el código Huffman deseado.

Para obtener un símbolo a partir de un código se debe hacer así:
1. Comenzar el recorrido del árbol en la raíz de éste
2. Extraer el primer símbolo del código a descodificar
3. Descender por la rama etiquetada con ese símbolo
4. Volver al paso 2 hasta que se llegue a una hoja, que será el símbolo asociado al códigoEn la práctica, casi siempre se utiliza el árbol para obtener todos los códigos de una sola vez; luego se guardan en tablas y se descarta el árbol.
Para recuperar el fichero original es necesario conocer el código asignado a cada carácter, así como su longitud en bits. Si esta información se omite, y el receptor del fichero la conoce, podrá recuperar la información original. De este modo esposible utilizar el algoritmo para encriptar ficheros.
3. Objetivos
Se pretende codificar la información transmitida por una fuente que genera número hexadecimales (0 a F). Para ello, se deberá realizar un programa en MATLAB que realice las siguientes operaciones:
1. Entrada de datos a comprimir
2. Código asignado a cada dígito de entrada
3. Longitud media del código generado
4.Entropía de la fuente
5. Secuencia binaria a transmitir
6. Conversión de la secuencia binaria en octetos en comparación con secuencia original
Por lo tanto, a lo largo de la práctica iremos abordando cada uno de estos objetivos.
4. Desarrollo de la práctica
Lo primero que debemos hacer es pedir por pantalla la cadena de elementos que el usuario desea codificar.
Una vez que tenemos...