Codificación Huffman

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 usa comúnmente para la compresión de datos sin pérdidas . El proceso de encontrar o usar dicho código procede por medio de la codificación Huffman , un algoritmo desarrollado por David A. Huffman cuando era un Sc.D. estudiante del 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 se puede ver 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 de la probabilidad estimada o frecuencia de ocurrencia ( 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 se ordenan estos pesos. ^[2] Sin embargo, aunque es óptimo entre los métodos que codifican símbolos por separado, la codificación Huffman no siempre es óptimaentre 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, a David A. Huffman y sus compañeros de clase de teoría de la información del MIT se les dio a elegir entre un trabajo trimestral o un examen final . El profesor, Robert M. Fano , asignó un trabajo final sobre el problema de encontrar el código binario más eficiente. Huffman, incapaz de probar 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 usar 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 el inventor de la teoría de la información Claude Shannon para desarrollar un código similar. Construir el árbol de abajo hacia arriba garantizó 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 usa ampliamente como sinónimo de "código de prefijo", incluso cuando dicho código no es producido por el algoritmo de Huffman.

Árbol de Huffman generado a partir de las frecuencias exactas del texto "este es un ejemplo de un árbol de Huffman". Las frecuencias y códigos de cada carácter se encuentran a continuación. Codificar la oración con este código requiere 135 (o 147) bits, a diferencia de 288 (o 180) bits si se usaran 36 caracteres de 8 (o 5) bits. (Esto supone que el decodificador conoce la estructura del árbol de código y, por lo tanto, no necesita contarse como parte de la información transmitida).

Construyendo un árbol de Huffman

Visualización del uso de la codificación Huffman para codificar el mensaje "A_DEAD_DAD_CEDED_A_BAD_BABE_A_BEADED_ABACA_
BED". En los pasos 2 a 6, las letras se ordenan por frecuencia creciente, y las dos menos frecuentes en cada paso se combinan y reinsertan en la lista, y se construye un árbol parcial. El árbol final en el paso 6 se recorre para generar el diccionario en el paso 7. El paso 8 lo usa para codificar el mensaje.

Una fuente genera 4 símbolos diferentes con probabilidad . Se genera un árbol binario de izquierda a derecha tomando los dos símbolos menos probables y juntándolos para formar otro símbolo equivalente que tenga una probabilidad que sea igual a la suma de los dos símbolos. El proceso se repite hasta que solo quede un símbolo. Luego, el árbol se puede leer hacia atrás, de derecha a izquierda, asignando diferentes bits a diferentes ramas. El código final de Huffman es:${\ estilo de visualización \ {a_ {1}, a_ {2}, a_ {3}, a_ {4} \}}$${\displaystyle \{0.4;0.35;0.2;0.05\}}$

Símbolo	Código
a1	0
a2	10
a3	110
a4	111

La forma estándar de representar una señal compuesta por 4 símbolos es mediante el uso de 2 bits/símbolo, pero la entropía de la fuente es de 1,74 bits/símbolo. Si se utiliza este código de Huffman para representar la señal, la longitud media se reduce a 1,85 bits/símbolo; todavía está lejos del límite teórico porque las probabilidades de los símbolos son diferentes de las potencias negativas de dos.