En informática y teoría de la información , un código de Huffman es un tipo particular de código de prefijo óptimo que se utiliza habitualmente para la compresión de datos sin pérdidas . El proceso de búsqueda o uso de dicho código se denomina codificación de Huffman , un algoritmo desarrollado por David A. Huffman mientras era estudiante de doctorado en ciencias 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]
La salida 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 ocurrencia estimada ( peso ) para cada valor posible del símbolo fuente. Como en otros métodos de codificación de entropía , los símbolos más comunes generalmente se representan usando 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 clase de teoría de la información del MIT tuvieron que elegir entre un trabajo final o un examen final . El profesor, Robert M. Fano , les asignó un trabajo final sobre el problema de encontrar el código binario más eficiente. Huffman, incapaz de demostrar que algú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, quien había trabajado con Claude Shannon para desarrollar un código similar. La construcción del árbol desde abajo hacia arriba garantizaba la optimización, a diferencia del enfoque de arriba hacia abajo de la codificación de Shannon-Fano .
La codificación de 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 un 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.
Entrada .
Alfabeto , que es el alfabeto de símbolos de tamaño .
Tupla , que es la tupla de los pesos de símbolos (positivos) (normalmente proporcionales a las probabilidades), es decir . Salida .
Código , que es la tupla de palabras de código (binarias), donde es la palabra de código para . Objetivo .
Sea la longitud de ruta ponderada de 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 para 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 biunique , es decir, que se pueda decodificar de forma única , la suma de los presupuestos de probabilidad de todos los símbolos siempre es 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 que el código sea completo y al mismo tiempo se mantenga 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, entre todos los símbolos a i con probabilidad distinta de cero w i , 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 se pueden omitir de la fórmula anterior).
Como consecuencia del teorema de codificación de fuentes de Shannon , la entropía es una medida de la longitud de palabra de código más pequeña que es teóricamente posible para el alfabeto dado con pesos asociados. En este ejemplo, la longitud de palabra de código promedio ponderada es de 2,25 bits por símbolo, solo un poco más grande que la entropía calculada de 2,205 bits por símbolo. Por lo tanto, este código no solo 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 de Huffman no necesita ser único. Por lo 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 esa distribución de probabilidad. (Sin embargo, para cada asignación de longitud de palabra de código minimizadora, existe al menos un código de 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 de la cantidad 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 padre 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 padre . 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 hoja 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 la probabilidad más pequeña 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 máxima prioridad:
Dado que las estructuras de datos de cola de prioridad eficientes requieren un tiempo O(log n ) por inserción, y un árbol con n hojas tiene 2 n −1 nodos, este algoritmo opera en un tiempo O( n log n ), donde n es el número de símbolos.
Si los símbolos se ordenan por probabilidad, existe un método de tiempo lineal (O( n )) para crear un árbol de Huffman utilizando dos colas , la primera de las cuales contiene los pesos iniciales (junto con punteros a las hojas asociadas) y los pesos combinados (junto con punteros a los árboles) que se colocan al final de la segunda cola. Esto garantiza 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:
La codificación final de cualquier símbolo se lee luego mediante una concatenación de las etiquetas en los bordes a lo largo de la ruta desde el nodo raíz hasta el símbolo.
En muchos casos, la complejidad temporal 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 complejidad se refiere al comportamiento cuando n crece hasta ser muy grande.
En general, resulta beneficioso minimizar la varianza de la longitud de las palabras de código. Por ejemplo, un búfer de comunicación que recibe datos codificados con Huffman puede necesitar ser más grande para manejar símbolos especialmente largos si el árbol está especialmente desequilibrado. Para minimizar la varianza, simplemente rompa los empates entre colas eligiendo el elemento en la primera cola. Esta modificación conservará la optimalidad matemática de la codificación de Huffman mientras minimiza la varianza y minimiza la longitud del código de carácter 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 de ese valor de byte en particular). Sin embargo, antes de que esto pueda tener lugar, el árbol de Huffman debe reconstruirse de alguna manera. En el caso más simple, donde las frecuencias de los caracteres son bastante predecibles, el árbol se puede preconstruir (e incluso ajustar estadísticamente en cada ciclo de compresión) y, por lo tanto, reutilizar cada vez, a expensas de al menos alguna medida de eficiencia de compresión. De lo contrario, la información para reconstruir el árbol debe 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 poco uso práctico. 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 en anteponer el árbol de Huffman, bit a bit, 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 de carácter de esa hoja en particular. El proceso continúa recursivamente hasta que se llega al último nodo hoja; en ese punto, el árbol de Huffman se reconstruirá fielmente. La sobrecarga que se obtiene con este método varía de aproximadamente 2 a 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" sin usar, el descompresor debe poder determinar cuándo dejar de producir resultados. Esto se puede lograr ya sea 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 que se encuentran en el texto que se está comprimiendo. Esto requiere que se almacene una tabla de frecuencias junto con el texto comprimido. Consulte la sección Descompresión anterior para obtener más información sobre las distintas 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 se distribuyen de forma idéntica , un único código 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 ambos métodos mencionados pueden combinar una cantidad arbitraria de símbolos para lograr una codificación más eficiente y, en general, 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 más compleja que la codificación 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 Huffman suele ser más rápida y la codificación aritmética ha sido históricamente un tema de cierta preocupación por cuestiones de patentes . Por lo tanto, muchas tecnologías han evitado históricamente 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 Huffman han pasado al dominio público, ya que las primeras patentes han expirado.
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 una entrada de este tipo, 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 lo tanto la codificación de Huffman en particular, tienden a ser ineficientes en alfabetos pequeños, donde las probabilidades a menudo se encuentran 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 ampliamente 2 −1 = 0,5, lo que hace que el límite superior de ineficiencia sea ilimitado.
Existen dos enfoques relacionados para evitar esta ineficiencia particular mientras se sigue utilizando 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 Huffman se acerca teóricamente al límite de entropía, es decir, la compresión óptima. [6] Sin embargo, bloquear grupos arbitrariamente grandes de símbolos es poco 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 por longitud de serie . Esta técnica añade un paso más a la codificación por entropía, concretamente el recuento (de series) de símbolos repetidos, que luego se codifican. Para el caso simple de los procesos Bernoulli , la codificación Golomb es óptima entre los códigos de prefijo para codificar la longitud de serie, un hecho demostrado mediante las técnicas de codificación Huffman. [7] Las máquinas de fax adoptan un enfoque similar utilizando la codificación Huffman modificada . Sin embargo, la codificación por longitud de serie no es tan adaptable a tantos tipos de entrada como otras tecnologías de compresión.
Existen muchas variaciones de la codificación de Huffman, [8] algunas de las cuales utilizan un algoritmo similar al de Huffman y otras encuentran códigos de prefijo óptimos (mientras que, por ejemplo, imponen diferentes restricciones a la salida). Nótese que, en el último caso, el método no necesita ser similar al de Huffman y, de hecho, ni siquiera necesita ser de tiempo polinomial .
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 se toman juntos los n símbolos menos probables, 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 correctamente un árbol n -ario para la codificación de Huffman. En estos casos, se deben agregar marcadores de posición de probabilidad 0 adicionales. Esto se debe a que el árbol debe formar un contratista de n a 1; [ aclaración necesaria ] 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 Huffman adaptativa implica calcular las probabilidades dinámicamente en función de las frecuencias reales recientes en la secuencia de símbolos de origen y cambiar la estructura del árbol de codificación para que coincida con las estimaciones de probabilidad actualizadas. Se utiliza rara vez en la práctica, 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 una mejor compresión.
La mayoría de las veces, los pesos utilizados en las implementaciones de la codificación de Huffman representan probabilidades numéricas, pero el algoritmo dado anteriormente no requiere esto; solo requiere que los pesos formen un monoide conmutativo totalmente ordenado , es decir, una forma de ordenar los pesos y sumarlos. El algoritmo de plantilla de Huffman permite utilizar cualquier tipo de pesos (costos, frecuencias, pares de pesos, pesos no numéricos) 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 que se aplicó por primera vez al diseño de circuitos.
La codificación de Huffman de longitud limitada es una variante en la que el objetivo sigue siendo lograr una longitud de ruta ponderada mínima, pero hay una restricción adicional: la longitud de cada palabra de código debe ser menor que una constante dada. El algoritmo de fusión de paquetes resuelve este problema con un enfoque simple y voraz 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 o tiempo, a diferencia de los problemas de Huffman convencionales preclasificados y no clasificados, respectivamente.
En el problema de codificación estándar de Huffman, se supone que cada símbolo en el conjunto a partir del cual se construyen las palabras de código tiene un costo igual para transmitirse: una palabra de código cuya longitud es de N dígitos siempre tendrá un costo de N , sin importar cuántos de esos dígitos sean 0, cuántos sean 1, etc. Cuando se trabaja bajo este supuesto, minimizar el costo total del mensaje y minimizar el número total de dígitos son la misma cosa.
La codificación de Huffman con costes de letras desiguales es la 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 "rayón" tarda más en enviarse que un "punto" y, por lo tanto, el coste de un rayado en tiempo de transmisión es mayor. El objetivo sigue siendo minimizar la longitud media ponderada de la palabra de código, pero ya no es suficiente con minimizar la cantidad 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 de Huffman convencional, aunque ha sido resuelto por Richard M. Karp [9] cuya solución ha sido refinada para el caso de costes enteros por Mordecai J. Golin. [10]
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 las entradas y salidas debe ser idéntico. Así, por ejemplo, no se podría asignar el código , sino que se le debería asignar 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 presentó la primera solución de este problema alfabético binario óptimo, [11] 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 binarios de búsqueda . [12]
Si los pesos correspondientes a las entradas ordenadas alfabéticamente están en orden numérico, el código de 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 de Hu-Tucker. El código resultante de la entrada (re)ordenada numéricamente a veces se denomina código de Huffman canónico y, a menudo, es el código utilizado en la práctica, debido a la facilidad de codificación/descodificación. La técnica para encontrar este código a veces se denomina codificación de Huffman-Shannon-Fano , ya que es óptima como la codificación de Huffman, pero alfabética en probabilidad de peso, como la codificación de Shannon-Fano . El código de Huffman-Shannon-Fano correspondiente al ejemplo es , que, al tener las mismas longitudes de palabras de código que la solución original, también es óptimo. Pero en el código de Huffman canónico , el resultado es .
La codificación aritmética y la codificación de Huffman producen resultados equivalentes (logran la 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 de 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 solo coincide de manera óptima con un símbolo de probabilidad 1/2 k y otras probabilidades no se representan de manera óptima; mientras que la longitud de la palabra de código en la codificación aritmética se puede hacer que coincida exactamente con la probabilidad real del símbolo. Esta diferencia es especialmente sorprendente para tamaños de alfabeto pequeños. [ cita requerida ]
Sin embargo, los códigos de prefijo siguen siendo ampliamente utilizados debido a su simplicidad, alta velocidad y falta de cobertura de patentes . A menudo se utilizan como un "back-end" para otros métodos de compresión. Deflate ( algoritmo de PKZIP ) y los códecs multimedia como JPEG y MP3 tienen un modelo de front-end y cuantificación seguidos del uso de códigos de prefijo; estos a menudo se denominan "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 utilizando 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)
