METODO DE HUFFMAN

 

CENTRO UNIVERSITARIO INTERAMERICANO DEL PACIFICO

ESPECIALIDAD EN REDES 

ALUMNO: L.S.C. STALIN VAZQUEZ VILLALOBOS

TERCER CUATRIMESTRE 

 _______________________________________________________________________________________________

 Código Huffman

La codificación usando el método de Huffman (código Huffman) es un código prefijo óptimo para un conjunto dado de probabilidades.

En 1952, David Huffman propuso un método estadístico que permitía asignar un código binario a los diversos símbolos a comprimir (píxeles o caracteres, por ejemplo). La longitud de cada código no es idéntica para todos los símbolos: se asignan códigos cortos a los símbolos utilizados con más frecuencia (los que aparecen más a menudo), mientras que los símbolos menos frecuentes reciben códigos binarios más largos. La expresión Código de Longitud Variable (VLC) se utiliza para indicar este tipo de código porque ningún código es el prefijo de otro. De este modo, la sucesión final de códigos con longitudes variables será en promedio más pequeña que la obtenida con códigos de longitudes constantes. 

El codificador Huffman crea una estructura arbórea ordenada con todos los símbolos y la
frecuencia con que aparecen. Las ramas se construyen en forma recursiva comenzando con los símbolos menos frecuentes.
La construcción del árbol se realiza ordenando en primer lugar los símbolos según la frecuencia de aparición. Los dos símbolos con menor frecuencia de aparición se eliminan sucesivamente de la lista y se conectan a un nodo cuyo peso es igual a la suma de la frecuencia de los dos símbolos. El símbolo con menor peso es asignado a la rama 1, el otro a la rama 0 y así sucesivamente, considerando cada nodo formado como un símbolo nuevo, hasta que se obtiene un nodo principal llamado raíz.
El código de cada símbolo corresponde a la sucesión de códigos en el camino, comenzando desde este carácter hasta la raíz. De esta manera, cuanto más dentro del árbol esté el símbolo,más largo será el código.

Este codigo se basa en asignar códigos de distinta longitud de bits a cada uno de los caracteres de un archivo. Si se asignan códigos más cortos a los caracteres que aparecen más a menudo se consigue una compresión del archivo.
La compresión es mayor cuando la variedad de caracteres diferentes que aparecen es menor. Por ejemplo: si el texto se compone únicamente de números o mayúsculas, se conseguirá una compresión mayor

Para recuperar el archivo original es necesario conocer el código asignado a cada carácter, así como su longitud en bits, si ésta información se emite, y el receptor del fichero la conoce, podrá recuperar la información original. De este modo es posible utilizar el algoritmo para encriptar archivos. De lo contrario no podrá descomprimir la información.

Para realizar el algoritmo de Huffman se siguen los pasos enumerados a continuación:
1. Calcular las frecuencias de aparición de los símbolos involucrados.
2. En un árbol binario alinear los símbolos por frecuencias descendentes en nodos.
3. Ligar 2 nodos de menor frecuencia en un nuevo nodo de tal manera que la frecuencia sea una suma de frecuencias de los 2 símbolos.
4. Ir al paso 2 hasta generar un solo nodo de tal manera que la frecuencia sea 1.
5. Trazar el árbol de la codificación desde una raíz (el nodo generado con la probabilidad 1) a los nodos del origen y asigna a cada rama derecha 1 y a cada rama
izquierda 0

Supongamos que tenemos la siguiente cadena de caracteres:

                         “badaaaaabaadaadaabacbcaaaaaababdbbcbcbcd”

Calculando las probabilidades de aparición tenemos que:
a =0.5 b =0.25 c =0.125 d =0.125

Se alinean los símbolos por frecuencias descendentes en nodos como se muestra en la figura 1(a). En un árbol procedemos a ligar los nodos de menor frecuencia en un nuevo nodo y sumar sus frecuencias, ya que esa suma será el valor del nuevo nodo. Observemos en la figura 1(a) que los nodos c, d son de frecuencia menor.
Sumando ambas frecuencias obtenemos una suma la cual representa el nodo padre, ver figura 1(b). En 1(c), el nodo generado en 1(b) se convierte en hijo al sumar el valor del nodo con el otro nodo que sigue en probabilidad menor, se obtiene otro nodo padre. En 1(c) se observa que se ha construido una ramificación en la cual unicamente falta por unir el nodo “a” y la ramificación formada anteriormente, que es realizado en 1(d). Se verifica que todos los nodos suman 1. Una vez terminado el procedimiento se tiene una ramificación completa y se procede a asignar 0 y 1 a las ramas izquierda y derecha respectivamente.

Figura 1: Unión de nodos con menor frecuencia
y generación del proceso de codificación de los
caracteres.