center|thumb|350px|Árbol de Huffman generado para las frecuencias de apariciones exactas del texto "ESTO ES UN EJEMPLO DE UN ARBOL DE HUFFMAN". Las frecuencias y códigos de cada carácter se muestran abajo. Codificar esta frase de 41 caracteres usando este código requiere 156 bits (sin contar con el espacio para el árbol) cuando con bytes de 8 bits requiere 328 bits. CarácterFrecuenciaCódigoEspacio800E 6100N 31100O 31110U 30100A 20101D 21010F 21011L 20110M 20111S 211010B 1110110H 1110111J 1111100P 1111101R 1111110T 1111111
En ciencias de la computación y teoría de la información, la codificación Huffman es un algoritmo usado para compresión de datos. El término se refiere al uso de una tabla de códigos de longitud variable para codificar un determinado símbolo (como puede ser un carácter en un archivo), donde la tabla ha sido rellenada de una manera específica basándose en la probabilidad estimada de aparición de cada posible valor de dicho símbolo. Fue desarrollado por David A. Huffman mientras era estudiante de doctorado en el MIT, y publicado en "A Method for the Construction of Minimum-Redundancy Codes".
La codificación Huffman usa un método específico para elegir la representación de cada símbolo, que da lugar a un código prefijo (es decir, la cadena de bits que representa a un símbolo en particular nunca es prefijo de la cadena de bits de un símbolo distinto) que representa los caracteres más comunes usando las cadenas de bits más cortas, y viceversa. Huffman fue capaz de diseñar el método de compresión más eficiente de este tipo: ninguna representación alternativa de un conjunto de símbolos de entrada produce una salida media más pequeña cuando las frecuencias de los símbolos coinciden con las usadas para crear el código. Posteriormente se encontró un método para llevar esto a cabo en un tiempo lineal si las probabilidades de los símbolos de entrada (también conocidas como "pesos") están ordenadas.
Para un grupo de símbolos con una distribución de probabilidad uniforme y un número de miembros que es potencia de dos, la codificación Huffman es equivalente a una codificación en bloque binaria, por ejemplo, la codificación ASCII. La codificación Huffman es un método para crear códigos prefijo tan extendido que el término "codificación Huffman" es ampliamente usado como sinónimo de "código prefijo", incluso cuando dicho código no se ha producido con el algoritmo de Huffman.
Aunque la codificación de Huffman es óptima para una codificación símbolo a símbolo dada una distribución de probabilidad, su optimalidad a veces puede verse accidentalmente exagerada. Por ejemplo, la codificación aritmética y la codificación LZW normalmente ofrecen mayor capacidad de compresión. Estos dos métodos pueden agrupar un número arbitrario de símbolos para una codificación más eficiente, y en general se adaptan a las estadísticas de entrada reales. Este último es útil cuando las probabilidades no se conocen de forma precisa o varían significativamente dentro del flujo de datos.
Historia En 1951, a David Huffman y a sus compañeros de clase de la asignatura “Teoría de la Información” se les permitió optar entre la realización de un examen final o la presentación de un trabajo. El profesor Robert. M. Fano asignó las condiciones del trabajo bajo la premisa de encontrar el código binario más eficiente. Huffman, ante la imposibilidad de demostrar qué código era más eficiente, se rindió y empezó a estudiar para el examen final. Mientras estaba en este proceso vino a su mente la idea de usar árboles binarios de frecuencia ordenada y rápidamente probó que éste era el método más eficiente.
Con este estudio, Huffman superó a su profesor, quien había trabajado con el inventor de la teoría de la información Claude Shannon con el fin de desarrollar un código similar. Huffman solucionó la mayor parte de los errores en el algoritmo de codificación Shannon-Fano. La solución se basaba en el proceso de construir el árbol de abajo a arriba en vez de al contrario.
Definición del problema Descripción informal Dados Un conjunto de símbolos y sus pesos (normalmente proporcionales a probabilidades). Encontrar Un código binario prefijo (un conjunto de elementos del código) con longitud de palabra esperada mínima (de forma equivalente, un árbol con longitud del camino mínima).
Descripción formal Entradas
El alfabeto , que es el alfabeto de símbolos de tamaño . El conjunto , que es el conjunto de pesos (positivos) de los símbolos (normalmente proporcionales a probabilidades), es decir .
Salida El código , que es el conjunto de elementos del código (binario), donde es la palabra del código para .
Objetivo Sea la longitud del camino ponderado del código . Condición: para cualquier código .
Ejemplo Entrada (A, W) Símbolo (ai) a b c d e Suma Peso (wi) 0.10 0.15 0.30 0.16 0.29 = 1 Salida C Palabras del código (ci) 010 011 11 00 10 Longitud de la palabra (en bits)(li) 3 3 2 2 2 Longitud del camino ponderado(li wi ) 0.30 0.45 0.60 0.32 0.58 L(C) = 2.25 Optimalidad Probabilidad(2-li) 1/8 1/8 1/4 1/4 1/4 = 1.00 Cantidad de información (en bits)(−log2 wi) ≈ 3.32 2.74 1.74 2.64 1.79 Entropía(−wi log2 wi) 0.332 0.411 0.521 0.423 0.518 H(A) = 2.205
Para cualquier código biunívoco, aquel código decodificable de forma única, la suma de las probabilidades de todos los símbolos es siempre menor o igual que uno. En este ejemplo, es exactamente igual a uno; por lo que decimos que es un código completo. Si no es el caso, siempre se puede derivar un código equivalente añadiendo símbolos extra (con probabilidades nulas asociadas), para hacer el código completo a la vez que se mantiene biunívoco.
Tal como definió Shannon (1948), la cantidad de información h (en bits) de cada símbolo ai con probabilidad no nula wi es
La entropía H (en bits) es la suma ponderada, de todos los símbolos ai con probabilidad no nula wi, de la cantidad de información de cada símbolo:
(Nota: un símbolo con probabilidad cero tiene una contribución nula a la entropía. Cuando w = 0, es una indeterminación; aplicando la regla de L'Hôpital :
.
Por simplicidad, los símbolos con probabilidad nula han sido dejados fuera de la fórmula anterior).
Como consecuencia del teorema de codificación de fuente de Shannon, la entropía es una medida de la longitud de palabra más pequeña del código que es teóricamente posible para un alfabeto dado con unos pesos asociados. En este ejemplo, la longitud media de la palabra es 2,25 bits por símbolo, ligeramente mayor que la entropía calculada de 2,205 bits por símbolo. Así que no solo este código es óptimo en el sentido de que ningún otro código posible funciona mejor, sino que además está muy cercano al límite teórico establecido por Shannon.
Nótese que, en general, un código Huffman no necesita ser único, pero si lo es siempre es uno de los códigos que minimiza .
Técnica básica La técnica utilizada es el propio algoritmo de Huffman. Consiste en la creación de un árbol binario en el que se etiquetan los nodos hoja con los caracteres, junto a sus frecuencias, y de forma consecutiva se van uniendo cada pareja de nodos que menos frecuencia sumen, pasando a crear un nuevo nodo intermedio etiquetado con dicha suma. Se procede a realizar esta acción hasta que no quedan nodos hoja por unir a ningún nodo superior, y se ha formado el árbol binario.
Posteriormente se etiquetan las aristas que unen cada uno de los nodos con ceros y unos (hijo derecho e izquierdo, respectivamente, por ejemplo). El código resultante para cada carácter es la lectura, siguiendo la rama, desde la raíz hacia cada carácter (o viceversa) de cada una de las etiquetas de las aristas.
Construcción del árbol Para obtener los códigos de Huffman hay que construir un árbol binario de nodos, a partir de una lista de nodos, cuyo tamaño depende del número de símbolos, . Los nodos contienen dos campos, el símbolo y el peso (frecuencia de aparición).
Cada nodo del árbol, el cual, esto es una información que es muy repetitiva puede ser o bien un nodo hoja o un nodo interno. Inicialmente se considera que todos los nodos de la lista inicial son nodos hoja del árbol. Al ir construyendo el árbol, los nodos internos tendrán un peso y dos nodos hijos, y opcionalmente un enlace al nodo padre que puede servir para recorrer el árbol en ambas direcciones. Por convención el bit '0' se asocia a la rama izquierda y el bit '1' a la derecha. Una vez finalizado el árbol contendrá nodos hijo y nodos internos.
El proceso de construcción del árbol comienza formando un nodo intermedio que agrupa a los dos nodos hoja que tienen menor peso (frecuencia de aparición). El nuevo nodo intermedio tendrá como nodos hijos a estos dos nodos hoja y su campo peso será igual a la suma de los pesos de los nodos hijos. Los dos nodos hijos se eliminan de la lista de nodos, sustituyéndolos por el nuevo nodo intermedio. El proceso se repite hasta que solo quede un nodo en la lista. Este último nodo se convierte en el nodo raíz del árbol de Huffman.
El algoritmo de construcción del árbol puede resumirse así:
Crear un nodo hoja para cada símbolo, asociando un peso según su frecuencia de aparición e insertarlo en la lista ordenada ascendentemente. Mientras haya más de un nodo en la lista: Eliminar los dos nodos con menor probabilidad de la lista. Crear un nuevo nodo interno que enlace a los nodos anteriores, asignándole como peso la suma de los pesos de los nodos hijos. Insertar el nuevo nodo en la lista, (en el lugar que le corresponda según el peso). El nodo que quede es el nodo raíz del árbol.
Aquí hay un ejemplo de construcción del árbol a partir del texto en francés "j'aime aller sur le bord de l'eau les jeudis ou les jours impairs":
Propiedades principales Las probabilidades usadas pueden ser genéricas para el dominio de la aplicación, que están basadas en el caso promedio, o pueden ser las frecuencias reales encontradas en el texto que se está comprimiendo. (Esta variación requiere que la tabla de frecuencias u otra estructura utilizada para la codificación deben ser almacenadas con el texto comprimido; las implementaciones emplean varios mecanismos para almacenar tablas de manera eficiente).
La codificación Huffman es óptima cuando la probabilidad de cada símbolo de entrada es una potencia negativa de dos. Los códigos prefijos tienden a ser ligeramente ineficientes en alfabetos pequeños, donde las probabilidades normalmente se encuentran entre esos puntos óptimos. El "empaquetado", o expansión del tamaño del alfabeto concatenando múltiples símbolos en "palabras" de tamaño fijo o variable antes de la codificación Huffman, normalmente ayuda, especialmente cuando símbolos adyacentes están correlacionados (como en el caso de un texto en lenguaje natural). El peor caso para una codificación Huffman puede darse cuando la probabilidad de un símbolo excede 2-1 = 0.5, haciendo el límite superior de ineficiencia ilimitado. Estas situaciones a menudo responden bien a una forma de paquete llamada codificación run-length.
La codificación aritmética produce una ligera ganancia sobre la codificación Huffman, pero en la práctica esta ganancia raramente ha sido lo bastante grande como para utilizar la codificación aritmética que posee una complejidad computacional más elevada y además requiere el pago de royalties. (A julio de 2006, IBM posee patentes de muchos métodos de codificación aritmética en varias jurisdicciones).
Variación Existen muchas variaciones del código de Huffman, algunos que utilizan Huffman como algoritmo, y otros que encuentra el código prefijo óptimo. Tenga en cuenta que en este último caso el método no es necesariamente similar al de Huffmans y no tiene por qué terminar en tiempo polinómico.
Código Huffman n-ario El algoritmo n-ario de Huffman usa el alfabeto {0,1,….,n-1} para codificar el mensaje y construir un árbol n-ario. Este enfoque fue considerado por Huffman en su enfoque originario.
Código Huffman adaptable