Practica: teoría de Información y Codificación
(Codificación de Fuente y Códigos de Huffman)
DOCENTE: PhD. María Fernanda R. Sanclemente GRUPO: 9G
TITULO PRACTICA: Codificación de Fuente y Códigos de Huffman
Teoría de información y codificación Fecha:
INTEGRANTES:
OBJETIVO PRACTICA:
- Comprender las características del algoritmo de codificación y compresión
de Huffman
- Investigar ejemplos que simulen la aplicación de códigos Huffman usando
MATLAB
- Realizar un script que resuelva y ejecute el algoritmo de codificación y
compresión de Huffman de manera eficiene
MATERIALES Y EQUIPO: Computador con Matlab
INTRODUCCIÓN
En 1952, David Huffman propuso un método estadístico que permitía comprimir
códigos binarios para diferentes símbolos (como píxeles o caracteres). Cada código
no tiene la misma longitud para todos los símbolos: a los símbolos más comunes
(aquellos que aparecen con más frecuencia) se les asignan códigos cortos, mientras
que a los símbolos menos frecuentes se les asignan códigos binarios más largos.
El término código de longitud variable (VLC) se utiliza para referirse a dichos códigos
porque ningún código es un prefijo de otro código. De esta forma, las secuencias
finales de código de longitud variable serán de media más pequeñas que las
obtenidas utilizando códigos de longitud fija.
Funcionamiento del algoritmo
La codificación Huffman es uno de los métodos clásicos de codificación de fuente
de la familia de los métodos estadísticos, esto es, aquellos que necesitan conocer
la distribución probabilística de la fuente. El algoritmo básico consiste en, tras
ordenar los símbolos de mayor a menor en probabilidad, ir juntando parejas de
menor probabilidad formando un árbol. Cuando solamente haya dos raíces, se
asigna los símbolos 0 y 1 (o 1 y 0) a cada raíz, y se itera hacia atrás. Dada, por
ejemplo, una fuente F con 5 símbolos de probabilidades {1/2, 1/4, 1/8, 1/16, 1/16}
se podría construir el siguiente diagrama de árbol (ver figura 1).
Practica: teoría de Información y Codificación
(Codificación de Fuente y Códigos de Huffman)
Figura 1. Árbol binario, representación de código de Huffman
En cada etapa los dos elementos con menor probabilidad se unen y se obtiene un
elemento resultante cuya probabilidad es la suma de las dos anteriores. Cada vez
que se realiza una unión de dos elementos se asigna a cada uno de ellos un ‘1’ o
un ‘0’ (el resultado dependerá de que criterio de asignación se aplique. El proceso
termina cuando únicamente quedan dos elementos y también a cada uno de ellos
se le asigna un ‘1’ o un ‘0’. Finalmente para conocer el código asociado a cada
probabilidad se recorre el árbol en sentido inverso y se concatenan los unos o ceros
por los que se va pasando hasta llegar al principio de cada ramificación.
Otra forma de representar el árbol binario es por medio de una estructura en la cual
cada nodo puede tener un hijo izquierdo y un hijo derecho. No puede tener mas de
dos hijos (por eso se denomina binario). Si algún hijo tiene como referencia a null,
es decir, que no alcanza ningún dato, entonces se llama nodo externo, en el caso
contrario se llama nodo interno (como se puede ver en la figura 2), sus usos mas
comunes con árboles binarios de búsqueda, los montículos binarios y codificación
de Huffman.
Figura 2. Árbol binario
Practica: teoría de Información y Codificación
(Codificación de Fuente y Códigos de Huffman)
Terminología:
- Nodo: Cada elemento del árbol:
A,B,C,D,E,F,G,H,K
- Nodo raíz: Primer elemento agregado al árbol:
A
- Nodo padre: Se le llama asi al nodo predecesor de un elemento:
A es padre de B y C
- Nodo hijo: Es el nodo sucesor de un elemento:
F es hijo de C
- Hermanos: Nodos que tienen el mismo nodo padre
D y E son hermanos
- Nodo hoja: Aquel nodo que no tiene hijos
D, H, F, K
Algoritmo de Huffman
Es código de longitud variable, en el que la longitud de cada código depende de la
frecuencia (absoluta o relativa) de aparición de cada símbolo en un texto; cuanto
más frecuente sea un símbolo, su código asociado será más corto.
El algoritmo de construcción del árbol puede resumirse así:
1. Crear un nodo hoja para cada símbolo, asociando un peso según su
frecuencia de aparición e insertarlo en la lista ordenada ascendentemente.
2. Mientras haya más de un nodo en la lista:
a. Eliminar de la lista los dos nodos con menor frecuencia.
b. Crear un nuevo nodo interno que enlace a los nodos anteriores,
asignándole como peso la suma de los pesos de los nodos hijos y
etiquetamos la arista del nodo derecho con 1 y del nodo izquierdo con 0.
c. Insertar el nuevo nodo en la lista, (en el lugar que le corresponda según
el peso).
3. El nodo que quede es el nodo raíz del árbol.
Nota: Para la palabra MATEMATICA
CARACTER M A T E I C
Frecuencia Absoluta 2 3 2 1 1 1
Frecuencia relativa 0.2 0.3 0.2 0.1 0.1 0.1
Practica: teoría de Información y Codificación
(Codificación de Fuente y Códigos de Huffman)
La disminución de bits utilizados gracias al código de Huffman se puede ver de la
siguiente forma:
Carácter Frecuencia Código Numero
absoluta Huffman de bits
M 2 111 6
A 3 10 6
T 2 00 4
E 1 010 3
I 1 011 3
C 1 110 3
TOTAL 10 25
Número de bits utilizando ASCII tradicional: 10x8=80
Número de bits utilizando Huffman: 25
25
El número de bits utilizados se ha reducido al: 80 𝑥100 = 31.25%
Ejemplo: Se tiene cierta frase en la que los símbolos tienen las frecuencias relativas
siguiente
A B C D E F
0.08 0.10 0.12 0.15 0.20 0.35
Use el algoritmo de Huffman para codificar los símbolos con las frecuencias dadas
y calcule la cantidad de bits usados para la codificación de cada carácter.
Practica: teoría de Información y Codificación
(Codificación de Fuente y Códigos de Huffman)
Según el árbol la codificación sería:
A B C D E F
000 001 100 101 01 11
DESARROLLO
ACTIVIDAD 1: Obtenga el árbol binario para las siguientes frases y determine a que
porcentaje se reduce en número de bits.
Nota: Use el código ASCII (ver figura 3) para determinar el orden.
Figura 3. Código ASCII
Practica: teoría de Información y Codificación
(Codificación de Fuente y Códigos de Huffman)
1. El vino vino, el vino no vino vino, el vino vino vinagre.
2. Lado, ledo, lido, lodo, ludo, decirlo al revés lo dudo.
3. Alianza avanza con esperanza y confianza.
4. Una vida vivida con miedos es una vida medio vivida.
5. Compré pocas copas, pocas copas compré, como compré pocas copas,
pocas copas pagaré.
ACTIVIDAD 2: Grafique un árbol binario para detallar el funcionamiento del
algoritmo de codificación de Huffman de los ejercicios anteriores y compruebelos
con el siguiente código y en el mismo código muestre su longitud y su entropía.
Código inicial para obtener la probabilidad automática utilizando el código
ASCII como representación de la probabilidad de cada carácter
% ************************
% Codigo Hufmman Ejemplo
% ************************
clc;
clear all;
close all;
% Defina el string a codificar
my_str = 'jason';
auto_prob = 1;
%Funcion para calculo automatico de probabilidad de simbolos
if (auto_prob == 1)
% caluclo automatico de la distribucion de probabilidad
% obtiene el codigo ASCII de cada caracter
% cada codigo ASCII representa la probabilidad de encontrar el
caracter
prob_dist = double(my_str);
end
num_bits = ceil(log2(length(prob_dist)));
%Función para mostrar las probabilidades del caracter
disp('Probabilidad del caracter:');
for i = 1:length(prob_dist)
display(strcat(my_str(i),' --> ',num2str(prob_dist(i))));
end
total = sum(prob_dist);
Practica: teoría de Información y Codificación
(Codificación de Fuente y Códigos de Huffman)
Código para graficar árbol binario que detalle el proceso de codificación que
utiliza el algoritmo de Huffman
% Funcion para guardar el arreglo a codificar
for i = 1:length(my_str)
sorted_str{i} = my_str(i);
end
%Guarda las probabilidades y simbolos iniciales
init_str = sorted_str;
init_prob = prob_dist;
%Proceso de codificacion de huffman
sorted_prob = prob_dist;
rear = 1;
while (length(sorted_prob) > 1)
% Ordena las probabilidades
[sorted_prob,indeces] = sort(sorted_prob,'ascend');
% Ordena el string en orden alfabetico
sorted_str = sorted_str(indeces);
% Crea los nuevos simbolos
new_node = strcat(sorted_str(2),sorted_str(1));
new_prob = sum(sorted_prob(1:2));
% Desencola simbolos usados del antiguo nodo
sorted_str = sorted_str(3:length(sorted_str));
sorted_prob = sorted_prob(3:length(sorted_prob));
% Añade nuevo simbolo al antiguo nodo
sorted_str = [sorted_str, new_node];
sorted_prob = [sorted_prob, new_prob];
% Añade nuevo simbolo al nuevo nodo
newq_str(rear) = new_node;
newq_prob(rear) = new_prob;
rear = rear + 1;
end
%Arbol de datos de huffman
tree = [newq_str,init_str];
tree_prob = [newq_prob, init_prob];
% Ordena todos los nodos del arbol
[sorted_tree_prob,indeces] = sort(tree_prob,'descend');
sorted_tree = tree(indeces);
% calcular paramteros del arbol
parent(1) = 0;
num_children = 2;
for i = 2:length(sorted_tree)
% Extrae el simbolo
Practica: teoría de Información y Codificación
(Codificación de Fuente y Códigos de Huffman)
me = sorted_tree{i};
% Encuentra el simbolo padre (busca hasta que encuentra la pareja mas
corta)
count = 1;
parent_maybe = sorted_tree{i-count};
diff = strfind(parent_maybe,me);
while (isempty(diff))
count = count + 1;
parent_maybe = sorted_tree{i-count};
diff = strfind(parent_maybe,me);
end
parent(i) = i - count;
end
%dibujar el arbol de huffman
treeplot(parent);
title(strcat('Arbol del codigo Hufmman - "',my_str,'"'));
grid on
Nota:
1. Se debe presentar el informe de laboratorio en digital (Word ó pdf) con
portada y conclusiones.
2. Se debe enviar el informe antes de la clase indicada al classroom
3. Grupos de trabajo de 3 personas.
BIBLIOGRAFIA
OPPENHEIM, A. V. (2000)Tratamiento de señales en tiempo [Link]: Prentice-Hall.
2ed.
MARIÑO A., JOSE B.(1999) Tratamiento digital de la señal: una introducción experimental.
México: Alfaomega.2ed.
Proakis, J. G., & Manolakis, D. G. (2007). Tratamiento Digital de Señales. Madrid: Prentice
Hall.
Ingle, V. K., & Proakis, J. G. (2011). Digital Signal Processing using MATLAB. Cengage
Learning.
Hayes, M. H. (1999). Digital Signal Processing. McGraw Hill.
Haykin, S. (1996). Adaptive filter theory. Prentice Hall.
Gonzalez, R. C., & Woods, R. E. (2002). Digital Image Processing. Adison Wealey.
Burrus, C. S., McClellan, J. H., Oppenheim, A. V., Parks, T. W., Schafer, R. W., & Schuessler,
H. W. (1998). Ejercicios de tratamiento de la señal utilizando Matlab v. 4. Prentice Hall.
Soria, E., Martinez, M., Frances, J. V., & Camps, G. (2003). Tratamiento digital de señales.
Problemas y ejercicios resueltos. Prentice Hall.
Ballesteros, Dora (2009). “Compresión de señales ecg utilizando codificacion huffman”,
Universidad Militar de Nueva Granada.
Garces, R. (2016). “Códigos de huffman”, Pontificia Universidad Católica del Perú