Codificación Huffman:
Es un método general de codificación y compresión diseñado para minimizar el número medio de bits necesarios para transmitir un símbolo cuando se debe transmitir varias copias independientes y estadísticamente equivalentes de dicho símbolo. Este método determina cómo los distintos valores del símbolo deben representarse como cadenas binarias.
Supongamos que tenemos que enviar el símbolo X que puede tomar valores {x1,...xn} con probabilidad {p1,...,pn}. La idea es reservar palabras cortas para los valores más frecuentes de X. Este método no requiere usar ningún tipo de separador entre los valores.
Ejemplo: | x1 (0.5) | x2 (0.3) | x3 (0.15) | x4 (0.05) |
- Si se usan 00, 01, 10 y 11 necesitaremos siempre 2 bits para el valor de X.
- Si se usan las palabras 0,10,110,111 necesitaremos como término medio 1.7 bits (menos de 2).
El código del ejemplo es de longitud variable, pero no se requiere usar ningún tipo de separador entre los valores.
- x3 x1 x4 x3 x3 x2 = 110011111011010 Sólo puede decodificarse correctamente.
La razón es que siempre puede reconocer el final de una palabra porque ninguna otra palabra es el principio de otra dada. Un código con esta propiedad se denomina código prefijo. El código Huffman es el código prefijo que requiere el mínimo número medio de bits por símbolo.
Para derivar el código Huffman se hacen las siguientes operaciones:
- Escoger los dos símbolos xi, xj con probabilidad más pequeña.
- Se las reemplaza por yi0 e yi1.
- Se borra xi y xj de la lista y se añadeyi con probabilidad pi+pj.
- Volver al paso 1 hasta terminar con todos los símbolos.
Árbol de Huffman
El código queda definido por el camino desde C a cada nodo. La conversión para describir el código de Huffman es:
Práctica
Calcular el árbol de Huffman de la siguiente frase: "Anita lava la tina" en Matlab.
Código para Matlab:
clc;
clear all;
close all;
my_str = 'Anita lava la tina'; %Cadena de caracteres
auto_prob = 1;
if (auto_prob == 1)
% Calcula automaticamente la probabilidad, si no le da valor a 0
% para hacerlo manual
% Con ASCII la version por cada caracter
% Cada valor de ASCII representa la probabilidad de encontrar el caracter
prob_dist = double(my_str);
else
prob_dist = [10 19 30 40 50]; %Se define la probabilidad manual de distribución
end
num_bits = ceil(log2(length(prob_dist))) %Se calcula el número de bits
disp('Character Probability:');
for i = 1:length(prob_dist)
display(strcat(my_str(i),' --> ',num2str(prob_dist(i))));
end
total = sum(prob_dist)
for i = 1:length(my_str)
clase_str{i} = my_str(i);
end
%mostramos la suma de la probabilidad
%guardamos la inicial de los simbolos y sus probabilidades para usarlos despues
init_str = clase_str;
init_prob = prob_dist;
sorted_prob = prob_dist;
rear = 1;
while (length(sorted_prob) > 1)
% Clase Probabilidad
[sorted_prob,indeces] = sort(sorted_prob,'ascend');
% Clase de la cadena basada en la incidencia
clase_str = clase_str(indeces);
% Crea nuevo simbolo
new_node = strcat(clase_str(2),clase_str(1));
new_prob = sum(sorted_prob(1:2));
% Se recorre el simbolo usado del viejo
clase_str = clase_str(3:length(clase_str));
sorted_prob = sorted_prob(3:length(sorted_prob));
% Agregamos un nuevo simbolo detras del viejo
clase_str = [clase_str, new_node];
sorted_prob = [sorted_prob, new_prob];
% Agregamos un nuevo simbolo
newq_str(rear) = new_node;
newq_prob(rear) = new_prob;
rear = rear + 1;
end
tree = [newq_str,init_str];
tree_prob = [newq_prob, init_prob];
% Usamos la clase de elementos de arbol completo
[sorted_tree_prob,indeces] = sort(tree_prob,'descend');
sorted_tree = tree(indeces);
parent(1) = 0;
num_children = 2;
for i = 2:length(sorted_tree)
% Extraemos el simbolo
me = sorted_tree{i};
% Buscamos un parecido de simbolo
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
treeplot(parent);
title(strcat('Arbol de Codigo de Huffman - "',my_str,'"'));
display(sorted_tree)
display(sorted_tree_prob)
[xs,ys,h,s] = treelayout(parent);
text(xs,ys,sorted_tree);
for i = 2:length(sorted_tree)
% Uso las coordenadas para acomodarlo
my_x = xs(i);
my_y = ys(i);
% Uso el parentesco de las coordenadas
parent_x = xs(parent(i));
parent_y = ys(parent(i));
% Calculo el ancho de las coordenadas (midpoint)
mid_x = (my_x + parent_x)/2;
mid_y = (my_y + parent_y)/2;
%Calculo el ancho (Positiva = 1, Negativa = 0)
slope = (parent_y - my_y)/(parent_x - my_x);
if (slope > 0)
weight(i) = 1;
else
weight(i) = 0;
end
text(mid_x,mid_y,num2str(weight(i)));
end
for i = 1:length(sorted_tree)
% Codigo de inicializar
code{i} = '';
% Crear un ciclo para encontra el parentesco
index = i;
p = parent(index);
while(p ~= 0)
w = num2str(weight(index));
code{i} = strcat(w,code{i});
index = parent(index);
p = parent(index);
end
end
codeBook = [sorted_tree', code']
Resultados
Ventana de comandos de Matlab:
num_bits =
5
Character Probability:
A -->65
n -->110
i -->105
t -->116
a -->97
-->32
l -->108
a -->97
v -->118
a -->97
-->32
l -->108
a -->97
-->32
t -->116
i -->105
n -->110
a -->97
total =
1642
sorted_tree =
Columns 1 through 9
'vttnnlliiaaaaa A' 'vttnnlli' 'iaaaaa A' 'vttn' 'nlli' 'iaaa' 'aa A' 'vt' 'tn'
Columns 10 through 24
'nl' 'li' 'ia' 'aa' 'aa' ' A' 'v' 't' 't' 'n' 'n' 'l' 'l' 'i' 'i'
Columns 25 through 35
'a' 'a' 'a' 'a' 'a' ' ' 'A' ' ' ' ' ' ' ' '
sorted_tree_prob =
Columns 1 through 9
1642 891 751 460 431 396 355 234 226
Columns 10 through 18
218 213 202 194 194 161 118 116 116
Columns 19 through 27
110 110 108 108 105 105 97 97 97
Columns 28 through 35
97 97 96 65 64 32 32 32
codeBook =
'vttnnlliiaaaaa A' ''
'vttnnlli' '1'
'iaaaaa A' '0'
'vttn' '11'
'nlli' '10'
'iaaa' '01'
'aa A' '00'
'vt' '111'
'tn' '110'
'nl' '101'
'li' '100'
'ia' '011'
'aa' '001'
'aa' '0011'
' A' '000'
'v' '1111'
't' '1101'
't' '11011'
'n' '1011'
'n' '10111'
'l' '1001'
'l' '10011'
'i' '0111'
'i' '01111'
'a' '00111'
'a' '001111'
'a' '0011111'
'a' '00111111'
'a' '001111111'
' ' '0001'
'A' '0000'
' ' '00011'
' ' '000111'
' ' '0001111'
' ' '00011111'
Archivo para Matlab:
http://www.mediafire.com/download/jj6m5mtr5b5dz4t/juanitobuenohuffman.rar
Fuente:
http://neo.lcc.uma.es/evirtual/cdd/tutorial/presentacion/huffman.html
No hay comentarios:
Publicar un comentario