En informática y teoría de la información , un código Huffman es un tipo particular de código de prefijo óptimo que se utiliza comúnmente para la compresión de datos sin pérdidas . El proceso de encontrar o utilizar dicho código es la codificación Huffman , un algoritmo desarrollado por David A. Huffman cuando era doctor en ciencias. estudiante en el MIT , y publicado en el artículo de 1952 "Un método para la construcción de códigos de redundancia mínima". [1]
El resultado del algoritmo de Huffman puede verse como una tabla de códigos de longitud variable para codificar un símbolo fuente (como un carácter en un archivo). El algoritmo deriva esta tabla a partir de la probabilidad o frecuencia de aparición estimada ( peso ) para cada valor posible del símbolo fuente. Como ocurre con otros métodos de codificación entrópica , los símbolos más comunes generalmente se representan utilizando menos bits que los símbolos menos comunes. El método de Huffman se puede implementar de manera eficiente, encontrando un código en el tiempo lineal al número de pesos de entrada si estos pesos están ordenados. [2] Sin embargo, aunque es óptima entre los métodos que codifican símbolos por separado, la codificación de Huffman no siempre es óptima entre todos los métodos de compresión: se reemplaza con codificación aritmética [3] o sistemas numéricos asimétricos [4] si se requiere una mejor relación de compresión.
En 1951, David A. Huffman y sus compañeros de teoría de la información del MIT tuvieron la opción de elegir entre un trabajo final o un examen final . El profesor Robert M. Fano asignó un trabajo final sobre el problema de encontrar el código binario más eficaz. Huffman, incapaz de demostrar que ningún código fuera el más eficiente, estaba a punto de darse por vencido y comenzar a estudiar para el examen final cuando se le ocurrió la idea de utilizar un árbol binario ordenado por frecuencia y rápidamente demostró que este método era el más eficiente. [5]
Al hacerlo, Huffman superó a Fano, que había trabajado con Claude Shannon para desarrollar un código similar. Construir el árbol de abajo hacia arriba garantiza la optimización, a diferencia del enfoque de arriba hacia abajo de la codificación de Shannon-Fano .
La codificación Huffman utiliza un método específico para elegir la representación de cada símbolo, lo que da como resultado un código de prefijo (a veces llamado "códigos sin prefijo", es decir, la cadena de bits que representa algún símbolo en particular nunca es un prefijo de la cadena de bits que representa cualquier otro). símbolo). La codificación de Huffman es un método tan extendido para crear códigos de prefijo que el término "código de Huffman" se utiliza ampliamente como sinónimo de "código de prefijo", incluso cuando dicho código no es producido por el algoritmo de Huffman.
Aporte .
Alfabeto , que es el alfabeto simbólico de tamaño .
Tupla , que es la tupla de los pesos de los símbolos (positivos) (normalmente proporcionales a las probabilidades), es decir . Producción .
Code , que es la tupla de palabras en código (binarias), donde está la palabra en código para . Meta .
Sea la longitud de ruta ponderada del código . Condición: para cualquier código .
Damos un ejemplo del resultado de la codificación de Huffman para un código con cinco caracteres y pesos dados. No verificaremos que minimice L en todos los códigos, pero calcularemos L y lo compararemos con la entropía de Shannon H del conjunto de pesos dado; el resultado es casi óptimo.
Para cualquier código que sea biúnico , lo que significa que el código es decodificable de forma única , la suma de los presupuestos de probabilidad de todos los símbolos es siempre menor o igual a uno. En este ejemplo, la suma es estrictamente igual a uno; como resultado, el código se denomina código completo . Si este no es el caso, siempre se puede derivar un código equivalente agregando símbolos adicionales (con probabilidades nulas asociadas), para completar el código y mantenerlo biunique .
Según lo definido por Shannon (1948) , el contenido de información h (en bits) de cada símbolo a i con probabilidad no nula es
La entropía H (en bits) es la suma ponderada, en todos los símbolos a i con probabilidad distinta de cero wi , del contenido de información de cada símbolo :
(Nota: un símbolo con probabilidad cero tiene una contribución cero a la entropía, ya que . Por lo tanto, para simplificar, los símbolos con probabilidad cero pueden omitirse de la fórmula anterior).
Como consecuencia del teorema de codificación fuente de Shannon , la entropía es una medida de la longitud de palabra en clave más pequeña que es teóricamente posible para un alfabeto dado con pesos asociados. En este ejemplo, la longitud promedio ponderada de la palabra de código es de 2,25 bits por símbolo, sólo ligeramente mayor que la entropía calculada de 2,205 bits por símbolo. Así que este código no sólo es óptimo en el sentido de que ningún otro código factible funciona mejor, sino que está muy cerca del límite teórico establecido por Shannon.
En general, un código Huffman no tiene por qué ser único. Por tanto, el conjunto de códigos de Huffman para una distribución de probabilidad dada es un subconjunto no vacío de los códigos que minimizan para esa distribución de probabilidad. (Sin embargo, para cada asignación de longitud de palabra de código de minimización, existe al menos un código Huffman con esas longitudes).
La técnica funciona creando un árbol binario de nodos. Estos se pueden almacenar en una matriz regular , cuyo tamaño depende del número de símbolos . Un nodo puede ser un nodo hoja o un nodo interno . Inicialmente, todos los nodos son nodos hoja, que contienen el símbolo en sí, el peso (frecuencia de aparición) del símbolo y, opcionalmente, un enlace a un nodo principal que facilita la lectura del código (a la inversa) a partir de un nodo hoja. . Los nodos internos contienen un peso , enlaces a dos nodos secundarios y un enlace opcional a un nodo principal . Como convención común, el bit '0' representa seguir al hijo izquierdo y el bit '1' representa seguir al hijo derecho. Un árbol terminado tiene hasta nodos foliares y nodos internos. Un árbol de Huffman que omite los símbolos no utilizados produce las longitudes de código más óptimas.
El proceso comienza con los nodos hoja que contienen las probabilidades del símbolo que representan. Luego, el proceso toma los dos nodos con menor probabilidad y crea un nuevo nodo interno que tiene estos dos nodos como hijos. El peso del nuevo nodo se establece en la suma del peso de los hijos. Luego aplicamos el proceso nuevamente, en el nuevo nodo interno y en los nodos restantes (es decir, excluimos los dos nodos hoja), repetimos este proceso hasta que solo quede un nodo, que es la raíz del árbol de Huffman.
El algoritmo de construcción más simple utiliza una cola de prioridad donde el nodo con menor probabilidad recibe la mayor prioridad:
Dado que las estructuras de datos de cola de prioridad eficientes requieren tiempo O (log n ) por inserción, y un árbol con n hojas tiene 2 n −1 nodos, este algoritmo opera en tiempo O ( n log n ), donde n es el número de símbolos.
Si los símbolos están ordenados por probabilidad, existe un método de tiempo lineal (O( n )) para crear un árbol de Huffman usando dos colas , la primera que contiene los pesos iniciales (junto con punteros a las hojas asociadas) y los pesos combinados. (junto con indicaciones a los árboles) se colocarán al final de la segunda cola. Esto asegura que el peso más bajo siempre se mantenga al frente de una de las dos colas:
Una vez generado el árbol de Huffman, se recorre para generar un diccionario que asigna los símbolos a códigos binarios de la siguiente manera:
Luego, la codificación final de cualquier símbolo se lee mediante una concatenación de las etiquetas en los bordes a lo largo del camino desde el nodo raíz hasta el símbolo.
En muchos casos, la complejidad del tiempo no es muy importante en la elección del algoritmo aquí, ya que n aquí es el número de símbolos en el alfabeto, que normalmente es un número muy pequeño (en comparación con la longitud del mensaje a codificar); mientras que el análisis de la complejidad se refiere al comportamiento cuando n crece hasta ser muy grande.
Generalmente es beneficioso minimizar la variación de la longitud de la palabra clave. Por ejemplo, un búfer de comunicación que recibe datos codificados en Huffman puede necesitar ser más grande para manejar símbolos especialmente largos si el árbol está especialmente desequilibrado. Para minimizar la variación, simplemente rompa los vínculos entre las colas eligiendo el elemento de la primera cola. Esta modificación conservará la optimización matemática de la codificación de Huffman y al mismo tiempo minimizará la variación y minimizará la longitud del código de caracteres más largo.
En términos generales, el proceso de descompresión es simplemente una cuestión de traducir el flujo de códigos de prefijo a valores de bytes individuales, generalmente atravesando el árbol de Huffman nodo por nodo a medida que se lee cada bit del flujo de entrada (alcanzar un nodo hoja necesariamente termina la búsqueda). para ese valor de byte en particular). Sin embargo, antes de que esto pueda ocurrir, el árbol de Huffman debe ser reconstruido de alguna manera. En el caso más simple, donde las frecuencias de los caracteres son bastante predecibles, el árbol puede preconstruirse (e incluso ajustarse estadísticamente en cada ciclo de compresión) y así reutilizarse cada vez, a expensas de al menos alguna medida de eficiencia de la compresión. En caso contrario, la información para reconstruir el árbol deberá enviarse a priori. Un enfoque ingenuo podría ser anteponer el recuento de frecuencia de cada carácter al flujo de compresión. Desafortunadamente, la sobrecarga en tal caso podría ascender a varios kilobytes, por lo que este método tiene poca utilidad práctica. Si los datos se comprimen utilizando codificación canónica , el modelo de compresión se puede reconstruir con precisión con solo bits de información (donde B es el número de bits por símbolo). Otro método consiste simplemente en anteponer el árbol de Huffman, poco a poco, al flujo de salida. Por ejemplo, suponiendo que el valor 0 representa un nodo padre y 1 un nodo hoja, siempre que se encuentre este último, la rutina de construcción del árbol simplemente lee los siguientes 8 bits para determinar el valor del carácter de esa hoja en particular. El proceso continúa recursivamente hasta llegar al último nodo hoja; en ese momento, el árbol de Huffman quedará fielmente reconstruido. La sobrecarga al utilizar este método oscila entre aproximadamente 2 y 320 bytes (suponiendo un alfabeto de 8 bits). También son posibles muchas otras técnicas. En cualquier caso, dado que los datos comprimidos pueden incluir "bits finales" no utilizados, el descompresor debe poder determinar cuándo dejar de producir resultados. Esto se puede lograr transmitiendo la longitud de los datos descomprimidos junto con el modelo de compresión o definiendo un símbolo de código especial para indicar el final de la entrada (sin embargo, este último método puede afectar negativamente la optimización de la longitud del código).
Las probabilidades utilizadas pueden ser genéricas para el dominio de la aplicación que se basan en la experiencia promedio, o pueden ser las frecuencias reales encontradas en el texto que se está comprimiendo. Esto requiere que se almacene una tabla de frecuencia con el texto comprimido. Consulte la sección Descompresión anterior para obtener más información sobre las diversas técnicas empleadas para este propósito.
El algoritmo original de Huffman es óptimo para una codificación símbolo por símbolo con una distribución de probabilidad de entrada conocida, es decir, codificar por separado símbolos no relacionados en dicho flujo de datos. Sin embargo, no es óptimo cuando se elimina la restricción símbolo por símbolo o cuando se desconocen las funciones de masa de probabilidad . Además, si los símbolos no son independientes ni están distribuidos de manera idéntica , un código único puede ser insuficiente para lograr la optimización. Otros métodos, como la codificación aritmética, suelen tener una mejor capacidad de compresión.
Aunque los dos métodos antes mencionados pueden combinar una cantidad arbitraria de símbolos para una codificación más eficiente y generalmente adaptarse a las estadísticas de entrada reales, la codificación aritmética lo hace sin aumentar significativamente sus complejidades computacionales o algorítmicas (aunque la versión más simple es más lenta y compleja que la codificación de Huffman). . Esta flexibilidad es especialmente útil cuando las probabilidades de entrada no se conocen con precisión o varían significativamente dentro del flujo. Sin embargo, la codificación de Huffman suele ser más rápida y la codificación aritmética fue históricamente un tema de cierta preocupación por cuestiones de patentes . Por lo tanto, históricamente muchas tecnologías han evitado la codificación aritmética en favor de Huffman y otras técnicas de codificación de prefijos. A mediados de 2010, las técnicas más utilizadas para esta alternativa a la codificación de Huffman pasaron al dominio público a medida que expiraron las primeras patentes.
Para un conjunto de símbolos con una distribución de probabilidad uniforme y un número de miembros que es una potencia de dos , la codificación de Huffman es equivalente a la codificación de bloques binarios simples , por ejemplo, la codificación ASCII . Esto refleja el hecho de que la compresión no es posible con dicha entrada, sin importar cuál sea el método de compresión, es decir, no hacer nada con los datos es lo óptimo.
La codificación de Huffman es óptima entre todos los métodos en cualquier caso en el que cada símbolo de entrada sea una variable aleatoria conocida, independiente e idénticamente distribuida, que tenga una probabilidad diádica . Los códigos de prefijo, y por tanto la codificación de Huffman en particular, tienden a ser ineficientes en alfabetos pequeños, donde las probabilidades a menudo caen entre estos puntos óptimos (diádicos). El peor caso para la codificación de Huffman puede ocurrir cuando la probabilidad del símbolo más probable excede con creces 2 −1 = 0,5, lo que hace que el límite superior de ineficiencia sea ilimitado.
Hay dos enfoques relacionados para solucionar esta ineficiencia particular sin dejar de utilizar la codificación Huffman. La combinación de un número fijo de símbolos ("bloqueo") a menudo aumenta (y nunca disminuye) la compresión. A medida que el tamaño del bloque se acerca al infinito, la codificación de Huffman teóricamente se acerca al límite de entropía, es decir, la compresión óptima. [6] Sin embargo, bloquear grupos arbitrariamente grandes de símbolos no es práctico, ya que la complejidad de un código Huffman es lineal en el número de posibilidades a codificar, un número que es exponencial en el tamaño de un bloque. Esto limita la cantidad de bloqueo que se realiza en la práctica.
Una alternativa práctica, de uso generalizado, es la codificación de longitud de ejecución . Esta técnica añade un paso antes de la codificación de entropía, específicamente el recuento (ejecuciones) de símbolos repetidos, que luego se codifican. Para el caso simple de los procesos de Bernoulli , la codificación de Golomb es óptima entre los códigos de prefijo para la longitud de ejecución de codificación, un hecho demostrado mediante las técnicas de codificación de Huffman. [7] Las máquinas de fax adoptan un enfoque similar que utiliza codificación Huffman modificada . Sin embargo, la codificación de longitud de ejecución no se adapta tanto a tantos tipos de entrada como otras tecnologías de compresión.
Existen muchas variaciones de la codificación Huffman, [8] algunas de las cuales utilizan un algoritmo similar a Huffman y otras encuentran códigos de prefijo óptimos (mientras, por ejemplo, imponen diferentes restricciones a la salida). Tenga en cuenta que, en el último caso, el método no necesita ser similar al de Huffman y, de hecho, ni siquiera necesita ser de tiempo polinómico .
El algoritmo n -ario de Huffman utiliza el alfabeto {0, 1,..., n − 1} para codificar el mensaje y construir un árbol n -ario. Huffman consideró este enfoque en su artículo original. Se aplica el mismo algoritmo que para los códigos binarios ( ), excepto que los n símbolos menos probables se toman juntos, en lugar de solo los 2 menos probables. Tenga en cuenta que para n mayor que 2, no todos los conjuntos de palabras fuente pueden formar adecuadamente un árbol n -ario para la codificación de Huffman. En estos casos, se deben agregar marcadores de posición adicionales con probabilidad 0. Esto se debe a que el árbol debe formar un contratista de n a 1; [ se necesita aclaración ] para la codificación binaria, este es un contratista de 2 a 1, y cualquier conjunto de tamaño puede formar dicho contratista. Si el número de palabras fuente es congruente con 1 módulo n −1, entonces el conjunto de palabras fuente formará un árbol de Huffman adecuado.
Una variación llamada codificación adaptativa de Huffman implica calcular las probabilidades dinámicamente basándose en frecuencias reales recientes en la secuencia de símbolos fuente y cambiar la estructura del árbol de codificación para que coincida con las estimaciones de probabilidad actualizadas. En la práctica, rara vez se usa, ya que el costo de actualizar el árbol lo hace más lento que la codificación aritmética adaptativa optimizada , que es más flexible y tiene mejor compresión.
Muy a menudo, los pesos utilizados en las implementaciones de la codificación de Huffman representan probabilidades numéricas, pero el algoritmo anterior no lo requiere; sólo requiere que los pesos formen un monoide conmutativo totalmente ordenado , es decir, una forma de ordenar pesos y sumarlos. El algoritmo de plantilla de Huffman permite utilizar cualquier tipo de ponderaciones (costos, frecuencias, pares de ponderaciones, ponderaciones no numéricas) y uno de los muchos métodos de combinación (no solo la suma). Dichos algoritmos pueden resolver otros problemas de minimización, como la minimización , un problema aplicado por primera vez al diseño de circuitos.
La codificación Huffman de longitud limitada es una variante en la que el objetivo sigue siendo lograr una longitud de ruta ponderada mínima, pero existe una restricción adicional de que la longitud de cada palabra de código debe ser menor que una constante determinada. El algoritmo de fusión de paquetes resuelve este problema con un enfoque simple y codicioso muy similar al utilizado por el algoritmo de Huffman. Su complejidad temporal es , donde es la longitud máxima de una palabra de código. No se conoce ningún algoritmo que resuelva este problema en tiempo , a diferencia de los problemas convencionales de Huffman preclasificados y no clasificados, respectivamente.
En el problema de codificación estándar de Huffman, se supone que cada símbolo del conjunto a partir del cual se construyen las palabras de código tiene el mismo costo de transmisión: una palabra de código cuya longitud es N dígitos siempre tendrá un costo de N , sin importar cuántas de esos dígitos son 0, cuántos son 1, etc. Cuando se trabaja bajo este supuesto, minimizar el costo total del mensaje y minimizar el número total de dígitos son lo mismo.
La codificación de Huffman con costos de letras desiguales es una generalización sin este supuesto: las letras del alfabeto de codificación pueden tener longitudes no uniformes, debido a las características del medio de transmisión. Un ejemplo es el alfabeto de codificación del código Morse , donde un 'guión' tarda más en enviarse que un 'punto' y, por tanto, el coste de un guión en tiempo de transmisión es mayor. El objetivo sigue siendo minimizar la longitud promedio ponderada de la palabra de código, pero ya no es suficiente simplemente minimizar el número de símbolos utilizados por el mensaje. No se conoce ningún algoritmo que resuelva esto de la misma manera o con la misma eficiencia que la codificación convencional de Huffman, aunque ha sido resuelto por Karp, cuya solución ha sido refinada por Golin para el caso de costos enteros.
En el problema de codificación estándar de Huffman, se supone que cualquier palabra de código puede corresponder a cualquier símbolo de entrada. En la versión alfabética, el orden alfabético de entradas y salidas debe ser idéntico. Así, por ejemplo, no se podría asignar el código , sino que se debería asignar o bien o . Esto también se conoce como el problema de Hu-Tucker , en honor a TC Hu y Alan Tucker , los autores del artículo que presentan la solución por primera vez a este problema alfabético binario óptimo, [9] que tiene algunas similitudes con el algoritmo de Huffman, pero no es una variación de este algoritmo. Un método posterior, el algoritmo Garsia-Wachs de Adriano Garsia y Michelle L. Wachs (1977), utiliza una lógica más simple para realizar las mismas comparaciones en el mismo límite de tiempo total. Estos árboles binarios alfabéticos óptimos se utilizan a menudo como árboles de búsqueda binaria . [10]
Si los pesos correspondientes a las entradas ordenadas alfabéticamente están en orden numérico, el código Huffman tiene las mismas longitudes que el código alfabético óptimo, que se puede encontrar calculando estas longitudes, lo que hace innecesaria la codificación Hu-Tucker. El código resultante de la entrada numéricamente (re)ordenada a veces se denomina código Huffman canónico y, a menudo, es el código utilizado en la práctica, debido a la facilidad de codificación/decodificación. La técnica para encontrar este código a veces se denomina codificación Huffman-Shannon-Fano , ya que es óptima como la codificación Huffman, pero alfabética en probabilidad de peso, como la codificación Shannon-Fano . El código Huffman-Shannon-Fano correspondiente al ejemplo es , que, al tener la misma longitud de palabra en código que la solución original, también es óptimo. Pero en el código canónico de Huffman , el resultado es .
La codificación aritmética y la codificación de Huffman producen resultados equivalentes (lograr entropía) cuando cada símbolo tiene una probabilidad de la forma 1/2 k . En otras circunstancias, la codificación aritmética puede ofrecer una mejor compresión que la codificación Huffman porque, intuitivamente, sus "palabras de código" pueden tener longitudes de bits no enteras, mientras que las palabras de código en códigos de prefijo como los códigos de Huffman solo pueden tener un número entero de bits. Por lo tanto, una palabra de código de longitud k sólo coincide de manera óptima con un símbolo de probabilidad 1/2 k y otras probabilidades no se representan de manera óptima; mientras que en la codificación aritmética se puede hacer que la longitud de la palabra clave coincida exactamente con la probabilidad real del símbolo. Esta diferencia es especialmente sorprendente para tamaños de alfabeto pequeños. [ cita necesaria ]
Sin embargo, los códigos de prefijo siguen siendo de uso generalizado debido a su simplicidad, alta velocidad y falta de cobertura de patentes . A menudo se utilizan como "back-end" de otros métodos de compresión. Deflate ( algoritmo PKZIP ) y los códecs multimedia como JPEG y MP3 tienen un modelo frontal y una cuantificación seguida del uso de códigos de prefijo; A menudo se les denomina "códigos de Huffman", aunque la mayoría de las aplicaciones utilizan códigos de longitud variable predefinidos en lugar de códigos diseñados con el algoritmo de Huffman.
![{\displaystyle \max _{i}\left[w_{i}+\mathrm {longitud} \left(c_{i}\right)\right]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1a80c0b460cf854976824c251037db43d7ed1810)
