Algoritmo Huffman

Algoritmo de Huffman
El algoritmo de Huffman tiene como objetivo
construir los códigos de Huffman creados por
David A. Huffman basados en n-símbolos
junto con sus frecuencias asociadas.
Estoscódigos se basan en los números 0 y 1.

Descripción:
Este algoritmo consiste en la creación de un
árbol binario que tiene cada uno de los símbolos
por hoja, y construido de tal forma quesiguiéndolo desde la raíz a cada una de sus hojas
se obtiene el código Huffman asociado.
Ejemplo:
Estructura = 0100111101110010011000111101

Limitaciones:
• Para poder utilizar el algoritmo de Huffman esnecesario conocer de antemano las frecuencias de
aparición de cada símbolo, y su eficiencia depende de
lo próximas a las frecuencias reales que sean las
estimadas. Algunas implementaciones delalgoritmo de
Huffman son adaptativas, actualizando las frecuencias
de cada símbolo conforme recorre el texto.
• La eficiencia de la codificación de Huffman también
depende del balance que existaentre los hijos de cada
nodo del árbol, siendo más eficiente conforme menor
sea la diferencia de frecuencias entre los dos hijos de
cada nodo.

Aplicación:
Esta aplicación se realizara haciendo unseguimiento paso a paso para llegar al código de
Huffman.

Ejercicio:
Representar la palabra “INGENIERIA” en los
códigos de Huffman según el algoritmo de
Huffman.
I

N

G

E

N

IE

R

I

A

PASOS:
1.- Obtener la cantidad de letras repetidas y ponerlas de forma ascendente.
G

R

A

N

E

I

1

1

1

2

2

3

*Estos números indican lafrecuencia que se utilizaran en la
construcción del árbol.
2.-Tomaremos las dos primeras letras para pasar a construir un árbol.
G

R

A

N

E

I

1

1

1

2

2

3

null

2Nuevo nodo generado

G

1

R

1

3.-Pasamos ordenar nuevamente con el nuevo nodo generado

A

1

A

1

2

E

2

null

G

null

N

1

2

R

I

1

3
N

2...