La codificación de Huffman explicada

Los ordenadores suelen almacenar cada letra en el mismo número de bits, ocho en ASCII simple. Es sencillo pero derrochador, porque algunas letras son mucho más comunes que otras. En 1951 un estudiante encontró la mejor manera de dar a cada símbolo un código de longitud propia, corto para los símbolos frecuentes y largo para los raros, con una construcción tan sencilla que cabe en unas pocas líneas. Hoy la codificación de Huffman está dentro de casi todos los archivos comprimidos, imágenes y sonidos que abres.

Un árbol de Huffman con las letras de ABRACADABRA como hojas, las ramas marcadas con 0 y 1, y el código corto de A resaltado
Un árbol de Huffman con las letras de ABRACADABRA como hojas, las ramas marcadas con 0 y 1, y el código corto de A resaltado

Códigos cortos para los símbolos comunes

El código Morse ya usaba la idea en la década de 1830: la E, la letra más común en inglés, es un solo punto, mientras que la Q es raya raya punto raya. Un código así ahorra tiempo y espacio siempre que unos símbolos aparecen más a menudo que otros. Pero las longitudes variables plantean un problema que el Morse resolvía con pausas: ¿cómo se sabe dónde termina un código y dónde empieza el siguiente? ¿Y qué longitudes debe recibir cada símbolo para que el total sea lo más pequeño posible?

Códigos prefijo

El primer problema desaparece si ningún código es el comienzo de otro. Con los códigos A = 0, B = 10, C = 110 y D = 111, los bits 0101100 solo pueden leerse como A B C A: en cuanto los bits leídos hasta el momento forman un código, ese código está completo. Estos códigos prefijo corresponden exactamente a los árboles binarios con los símbolos en las hojas, donde cada rama izquierda representa 0 y cada rama derecha, 1. Elegir un código es elegir un árbol.

La construcción de Huffman

Empieza con una hoja por símbolo, con su frecuencia de aparición como peso. Toma los dos árboles más ligeros y únelos bajo un nuevo nodo cuyo peso es su suma, y repite hasta que quede un solo árbol. Ese es todo el algoritmo. Los símbolos raros se unen primero y acaban en lo profundo del árbol, con códigos largos; los comunes se unen al final y se quedan cerca de la cima, con códigos cortos. Con una cola de prioridad requiere un tiempo proporcional a n log n para n símbolos.

Por qué es óptimo

En un árbol óptimo, los dos símbolos más raros siempre pueden colocarse como hermanos en el nivel más profundo: intercambiarlos con lo que haya allí solo puede acortar el total. Únelos en un solo símbolo con su peso combinado y el resto es el mismo problema con un símbolo menos, así que el paso voraz nunca descarta la mejor respuesta. El número total de bits usados es igual a la suma de los pesos de todos los nodos internos, que las uniones mantienen lo más pequeña posible.

Un trabajo en lugar de un examen

En 1951, David Huffman, estudiante de posgrado en el MIT, cursaba la asignatura de teoría de la información de Robert Fano. Fano dio a sus alumnos a elegir: presentarse al examen final o escribir un trabajo sobre cómo encontrar el código binario más eficiente. Huffman estuvo a punto de abandonar el trabajo, pero entonces vio que construir el árbol de abajo arriba, en lugar de dividirlo de arriba abajo como en el método de Shannon–Fano, siempre da el mejor resultado. Lo publicó en 1952; el método del estudiante superó al que su profesor había desarrollado con Claude Shannon.

David Huffman, fotografiado como profesor de la Universidad de California en Santa Cruz. Como estudiante de posgrado en el MIT, en 1951 halló su código óptimo en un trabajo para el curso de Robert Fano.
David Huffman, fotografiado como profesor de la Universidad de California en Santa Cruz. Como estudiante de posgrado en el MIT, en 1951 halló su código óptimo en un trabajo para el curso de Robert Fano.
Claude Shannon, que en 1948, en Bell Labs, precisó cuánta información contiene un mensaje y la midió en bits.
Claude Shannon, que en 1948, en Bell Labs, precisó cuánta información contiene un mensaje y la midió en bits.

Cerca de la entropía

Claude Shannon demostró que ningún código puede usar, de media, menos bits por símbolo que la entropía de la fuente. Un código de Huffman alcanza exactamente la entropía cuando cada probabilidad es una potencia de un medio, y nunca la supera en un bit entero por símbolo. La diferencia importa cuando un símbolo es muy común: un símbolo con una proporción del 99 % sigue necesitando al menos un bit entero, aunque solo lleva unos 0,015 bits de información. La codificación aritmética y los sistemas numéricos asimétricos (ANS) de los compresores más recientes evitan ese límite.

Códigos de Huffman por todas partes

La codificación de Huffman rara vez se usa sola, pero forma la última etapa de muchos formatos. Deflate, dentro de ZIP, gzip y PNG, primero sustituye las repeticiones por referencias y después escribe el resultado con códigos de Huffman. JPEG los usa para los números que quedan tras su transformación de la imagen, MP3 para sus datos de audio y los faxes para las longitudes de las series de blanco y negro. Los formatos suelen enviar un código de Huffman canónico, en el que solo hay que almacenar las longitudes de los códigos, porque los propios códigos pueden reconstruirse a partir de ellas.

Explóralo

Abre el constructor de códigos de Huffman para construir, paso a paso, el árbol de ABRACADABRA, de MISSISSIPPI RIVER, de una frase tuya o de cualquier otro texto. Observa cómo se unen los dos árboles más ligeros en cada paso, haz clic en una hoja para ver su código, sigue un símbolo a través de los bits codificados y compara el total con un código de longitud fija, con UTF-8 y con la entropía.

Preguntas frecuentes

¿Qué diferencia hay entre la codificación de Huffman y la de Shannon–Fano?

La codificación de Shannon–Fano construye el árbol desde arriba, dividiendo los símbolos una y otra vez en dos grupos de peso casi igual. A menudo es buena, pero no siempre óptima. Huffman construye el árbol desde abajo uniendo los dos árboles más ligeros, y siempre da el código prefijo más corto posible.

¿Necesita el decodificador el árbol?

Sí, necesita el mismo código. Por eso los archivos comprimidos lo almacenan, normalmente como una lista de longitudes de código para un código canónico, que ocupa solo unas pocas decenas de bytes. En textos cortos esa sobrecarga puede superar el ahorro; el constructor solo cuenta los bits codificados.

¿Puede la codificación de Huffman hacer más grande un archivo?

Los símbolos codificados nunca ocupan más bits que un código de longitud fija para los mismos símbolos. Pero también hay que almacenar la tabla de códigos, así que con datos muy cortos o casi aleatorios el resultado puede ser algo más grande que el original.

¿Qué dice la desigualdad de Kraft?

Que existe un código prefijo con longitudes de código l₁, l₂, … exactamente cuando la suma de 2 elevado a −l sobre todos los símbolos es como máximo 1. Para un árbol completo, como todo árbol de Huffman con al menos dos símbolos, la suma es exactamente 1.

¿Listo para probarlo?

Abre PictorX en tu navegador: sin instalación ni tarjeta de crédito para empezar.

Abrir el constructor de códigos de Huffman