codigo huffman

Tema 3: Codificación
Huffman
Rafael Molina
Depto. Ciencias de la Computación
e Inteligencia Artificial
Universidad de Granada
Rafael Molina

Tema 3: Codificación Huffman

1

Contenidos• Objetivos del tema
• El algoritmo del código de Huffman
– Códigos de Huffman de mínima varianza
• Códigos de Huffman Adaptativos
– Procedimiento de codificación
– Procedimiento dedecodificación
– Procedimiento de actualización
• (*) Códigos de Golomb
• (*)Código Tunstall
• Aplicaciones del código de Huffman
• Resumen
• Bibliografía

• Apéndice: Longitud del código de Huffman ycódigo de
Huffman extendido (*) Estas secciones son ilustrativas, no entran en el examen
Rafael Molina

Tema 3: Codificación Huffman

2

III.1 Objetivos del tema
En este tema vamos adescribir un algoritmo de codificación
muy conocido: el código de Huffman. Primero supondremos
que es conocida la distribución de probabilidad de la fuente
y luego construiremos el código cuando dichasprobabilidades no son conocidas.
A continuación veremos algunos esquemas de codificación,
en algún sentido, similares al código de Huffman.
Finalmente veremos algunos ejemplos de aplicación acompresión de imágenes, sonido y texto.
Rafael Molina

Tema 3: Codificación Huffman

3

III.2 El algoritmo del código de
Huffman.
La codificación usando el método de Huffman (códigoHuffman) es un código prefijo óptimo para un conjunto
dado de probabilidades.
Puede alcanzar la entropía, aunque no lo hace siempre.
Sí es óptimo entre los códigos prefijo.

Rafael Molina

Tema 3:Codificación Huffman

4

El código de Huffman está basado en dos propiedades de los
códigos prefijo óptimos:
1. En un código prefijo óptimo, los símbolos más frecuentes
–los que tienen mayorprobabilidad- tienen palabras del
código más cortas que las palabras menos frecuentes.
2. En un código prefijo óptimo, los dos símbolos que ocurren
con menos frecuencia tendrán la misma longitud....