huffman-octave

´
Instituto Tecnologico y de Estudios Superiores de Occidente
Departamento de Electr´nica, Inform´tica y Sistemas
o
a

C´mo implementar el algoritmo de Huffman en
o
Octave
L. M. Bazdresch

Noviembre 2009

Huffman en Octave
L. M. Bazdresch

1.

Introducci´n: el Algoritmo de Huffman
o

El algoritmo de Huffman genera un c´digo para los s´
o
ımbolos de una
fuente X . El c´digogenerado por este algoritmo tiene la propiedad de ser el
o
c´digo instant´neo con longitud promedio m´s cercana posible a la entrop´
o
a
a
ıa
de X . En este sentido el algoritmo es ´ptimo.
o
El algoritmo tiene como entrada un vector de probabilides PX correspondientes a los s´
ımbolos de la fuente X . La salida del algoritmo consiste
en las palabras de c´digo para cada s´
o
ımbolo.
Amanera de ejemplo, digamos que PX = [0.25 0.25 0.2 0.15 0.15]. El
algoritmo une los s´
ımbolos como se muestra en la figura (1). Las palabras
de c´digo resultantes son 00, 01, 10, 110, y 111.
o
0.200
0
0.250

1

2
0.450

0
1
3
0.550

0

0.250

4
1.000

1
0.150

0
1

1
0.300

0.150

Figura 1: Ejecuci´n del algoritmo de Huffman. Los c´
o
ırculos de la columnaizquierda son las probabilidades iniciales. Los dem´s c´
a ırculos tienen indicado,
arriba, el paso del algoritmo, y abajo, la probabilidad de cada s´
ımbolo
compuesto.
Este algoritmo es sencillo de correr en papel, para fuentes con pocos
s´
ımbolos. Sin embargo, cualquier aplicaci´n pr´ctica requiere programar el
o
a
algoritmo en una computadora. Esta tarea no es tan sencilla como pudieraparecer a primera vista. En este documento se ofrecen algunas ideas y c´digo
o
para arrancar con m´s certidumbre una implementaci´n en Octave/Matlab.
a
o
1

hoja

hoja

rama

hoja

rama

raíz

hoja

Figura 2: Relaci´n entre nodos de un ´rbol binario.
o
a

2.

´
Estructuras de Datos y Arboles

Una estructura de datos es una forma de organizar y relacionar datos enla memoria de una computadora, de manera que puedan ser usados eficientemente. Generalmente, el problema mismo que se quiere resolver sugiere una
forma de organizar los datos. Por ejemplo, para operaciones de ´lgebra lineal
a
conviene usar vectores y matrices. Una tabla hash est´ dise˜ada para asociar
a
n
identificadores (por ejemplo un nombre de una persona) con un valor (por
ejemplo unn´mero de tel´fono). Un grafo puede representar una regi´n, con
u
e
o
ciudades en los v´rtices y carreteras en las aristas, para calcular distancias
e
entre ellas, o las mejores rutas entre ellas.
La figura (1) sugiere tambi´n una forma de organizar los datos que el
e
algoritmo de Huffman va generando. Esta organizaci´n se conoce como ´rbol
o
a
binario. Un ´rbol binario contiene tres tipos denodos: hojas, ramas y ra´
a
ıces.
Cada nodo contiene informaci´n, y est´ relacionado con otros nodos (ver
o
a
figura (2)). Adem´s, se dice que una ra´ es padre de dos ramas, cada una
a
ız
de las cuales es padre de otras dos ramas o dos hojas. Cada rama y cada hoja
es hija de otra rama o de una ra´ El ´rbol se llama binario precisamente
ız.
a
porque cada nodo rama o ra´ tieneexactamente dos hijos.
ız
Es clara la similitud entre el diagrama obtenido ejecutando el algoritmo
de Huffman y un ´rbol binario. Esto nos sugiere que necesitamos implemena
tar esta estructura de datos en Octave.

3.

´
Arboles Binarios en Octave
Una implementaci´n de ´rboles binarios requiere lo siguiente:
o
a
Definir los nodos y una forma de crearlos
2

Definir una forma de almacenar losnodos
Crear funciones auxiliares:
• Guardar informaci´n en un nodo
o
• Determinar si un nodo es ra´ rama u hoja
ız,
• Insertar un nuevo nodo en un ´rbol
a

3.1.

Definici´n de nodos
o

Podemos determinar qu´ informaci´n hay que guardar en un nodo a
e
o
partir de la figura (1):
Un identificador
La probabilidad del nodo
Apuntador al nodo padre
Apuntador a un hijo a trav´s de una...