Siguiente: Códigos de Huffman terciarios, Arriba: Códigos de Huffman Anterior: Códigos de Huffman

Códigos de Huffman binarios

Para construir los códigos binarios se procede de una manera arbórea:

1. Sea ${\cal A}$ la lista de elementos de la forma $(a,f(a))$, donde $f(a)$ es el peso del carácter $a$. Acaso mediante un renombramiento de los caracteres se puede suponer que los pesos están ordenados de manera no-decreciente. En este momento, ${\cal A}$ consta del follaje de un árbol a construirse.
2. Inicialmente, sea ${\cal T}$, el árbol a construirse, un árbol binario vacío.
3. En tanto sea posible repítase el ciclo siguiente:
   1. Sáquese de ${\cal A}$ a sus primeras dos componentes. Estas son ``hojas'' o subárboles binarios, ${\cal T}_0$ y ${\cal T}_1$.
   2. Sean $f_0$ y $f_1$ las etiquetas de sus raices.
   3. Sea ${\cal T}= {\cal T}_0\bigtriangleup {\cal T}_1$ el árbol binario cuyo subárbol izquierdo es ${\cal T}_0$ y el derecho es ${\cal T}_1$. Etiquétese a su raíz con la suma $f:=f_{01}=f_0+f_1$, a su arista izquierda con $0$ y a su arista derecha con $1$.
   4. Insértese a ${\cal T}$ dentro de la lista ${\cal A}$ en el lugar que le corresponde según $f$, es decir, en la primera posición tal que todos los elementos de ${\cal A}$ hasta esa posición, tienen un peso estrictamente menor que $f$.
4. El código asociado a cada carácter es la lista dada por el camino desde la raíz hasta la hoja correspondiente al carácter.

Este algoritmo es de tipo voraz pues está codificando primeramente a los caracteres de mayor frecuencia.

Ejemplo 3.1   Consideremos el alfabeto $\mbox{\it Diez}$ con las frecuencias siguientes:

Carácter	0	1	2	3	4	5	6	7	8	9
Frecuencia $\cdot 10$	7	8	5	6	9	3	4	10	1	2

Constrúyase el correspondiente Código de Huffman

Puesto en orden no-decreciente, tenemos

${\cal A}$	[8]	[9]	[5]	[6]	[2]	[3]	[0]	[1]	[4]	[7]
$f$	1	2	3	4	5	6	7	8	9	10

Procediendo según los pasos descritos en el algoritmo, de manera consecutiva, obtenemos la computación mostrada en la tabla (2).

Recuadro 2: Computación del ejemplo.

${\cal A}$	[[8] [9]]	[5]	[6]	[2]	[3]	[0]	[1]	[4]	[7]
$f$	3	3	4	5	6	7	8	9	10

${\cal A}$	[6]	[2]	[[[8] [9]] [5]]	[3]	[0]	[1]	[4]	[7]
$f$	4	5	6	6	7	8	9	10

${\cal A}$	[[[8] [9]] [5]]	[3]	[0]	[1]	[[6] [2]]	[4]	[7]
$f$	6	6	7	8	9	9	10

${\cal A}$	[0]	[1]	[[6] [2]]	[4]	[7]	[[[[8] [9]] [5]] [3]]
$f$	7	8	9	9	10	12

${\cal A}$	[[6] [2]]	[4]	[7]	[[[[8] [9]] [5]] [3]]	[[0] [1]]
$f$	9	9	10	12	15

${\cal A}$	[7]	[[[[8] [9]] [5]] [3]]	[[0] [1]]	[[[6] [2]] [4]]
$f$	10	12	15	18

${\cal A}$	[[0] [1]]	[[[6] [2]] [4]]	[[7] [[[[8] [9]] [5]] [3]]]
$f$	15	18	22

${\cal A}$	[[7] [[[[8] [9]] [5]] [3]]]	[[[0] [1]] [[[6] [2]] [4]]]
$f$	22	33

${\cal A}$	[[[7] [[[[8] [9]] [5]] [3]]] [[[0] [1]] [[[6] [2]] [4]]]]
$f$	55

De lo cual resulta la codificación mostrada en la tabla (3). $\Box$

Recuadro 3: Codificación obtenida en el ejemplo.

Así pues, si originalmente se hubiese ocupado $4=\lceil \log_2(10)\rceil$ bits para representar cada símbolo de $\mbox{\it Diez}$, al sumar las frecuencias tendríamos que habría $\sum_{i=1}^{10} i=55$ caracteres en el corpus original $\sigma$, y el ``archivo'' que los contuviera tendría una longitud de 220 bits. Con la codificación de la tabla (3), el número total de bits será

$$10\cdot 2 + (9+8+7+6)\cdot 3 + (5+4+3)\cdot 4 + (2+1)\cdot 5=173,$$

por lo que la razón de compresión será $\frac{173}{220}\approx 78.64\%$. $\Box$

Siguiente: Códigos de Huffman terciarios, Arriba: Códigos de Huffman Anterior: Códigos de Huffman