Código Huffman

Octubre 2017

Código Huffman

En 1952, David Huffman propuso un método estadístico que permitía asignar un código binario a los diversos símbolos a comprimir (píxeles o caracteres, por ejemplo). La longitud de cada código no es idéntica para todos los símbolos: se asignan códigos cortos a los símbolos utilizados con más frecuencia (los que aparecen más a menudo), mientras que los símbolos menos frecuentes reciben códigos binarios más largos. La expresión Código de Longitud Variable (VLC) se utiliza para indicar este tipo de código porque ningún código es el prefijo de otro. De este modo, la sucesión final de códigos con longitudes variables será en promedio más pequeña que la obtenida con códigos de longitudes constantes.

El codificador Huffman crea una estructura arbórea ordenada con todos los símbolos y la frecuencia con que aparecen. Las ramas se construyen en forma recursiva comenzando con los símbolos menos frecuentes.

La construcción del árbol se realiza ordenando en primer lugar los símbolos según la frecuencia de aparición. Los dos símbolos con menor frecuencia de aparición se eliminan sucesivamente de la lista y se conectan a un nodo cuyo peso es igual a la suma de la frecuencia de los dos símbolos. El símbolo con menor peso es asignado a la rama 1, el otro a la rama 0 y así sucesivamente, considerando cada nodo formado como un símbolo nuevo, hasta que se obtiene un nodo principal llamado raíz.
El código de cada símbolo corresponde a la sucesión de códigos en el camino, comenzando desde este carácter hasta la raíz. De esta manera, cuanto más dentro del árbol esté el símbolo, más largo será el código.

Analicemos la siguiente oración: "COMMENT_CA_MARCHE". Las siguientes son las frecuencias de aparición de las letras:

MACE_HONTR
3222211111

Éste es el árbol correspondiente:

Árbol de Fuman

Los códigos correspondientes a cada carácter son tales que los códigos para los caracteres más frecuentes son cortos y los correspondientes a los símbolos menos frecuentes son largos:

MACE_HONTR
001001100100111110111110101011010111

Las compresiones basadas en este tipo de código producen buenas proporciones de compresión, en particular, para las imágenes monocromáticas (faxes, por ejemplo). Se utiliza especialmente en las recomendaciones T4 y T5 utilizadas en ITU-T

Consulta también


Huffman coding
Huffman coding
Codage de Huffman
Codage de Huffman
Codifica di Huffman
Codifica di Huffman
Codificação de Huffman
Codificação de Huffman
Última actualización: 16 de octubre de 2008 a las 15:43 por Jeff.
El documento «Código Huffman» se encuentra disponible bajo una licencia Creative Commons. Puedes copiarlo o modificarlo libremente. No olvides citar a CCM (es.ccm.net) como tu fuente de información.