Codificación de Huffman

Dado

Un conjunto de símbolos y, para cada símbolo , la frecuencia que representa la fracción de símbolos en el texto que son iguales a . ^{[ 5 ]}${\displaystyle S}$${\displaystyle x\in S}$${\displaystyle f_{x}}$${\displaystyle x}$

Encontrar

Un código binario sin prefijos (un conjunto de palabras clave) con una longitud mínima esperada de palabra clave (equivalentemente, un árbol con una longitud de ruta ponderada mínima desde la raíz ).

Entrada . Alfabeto , que es el alfabeto de símbolos de tamaño . Tupla , que es la tupla de los pesos de los símbolos (positivos) (generalmente proporcionales a las probabilidades), es decir . Salida . Código , que es la tupla de palabras clave (binarias), donde es la palabra clave para . Objetivo . Sea la longitud de ruta ponderada del código . Condición: para cualquier código .${\displaystyle A=(a_{1},a_{2},\dots ,a_{n})}$${\displaystyle n}$${\displaystyle W=(w_{1},w_{2},\dots,w_{n})}$${\displaystyle w_{i}=\operatorname {weight} \left(a_{i}\right),\,i\in \{1,2,\dots ,n\}}$${\displaystyle C\left(W\right)=(c_{1},c_{2},\dots ,c_{n})}$${\displaystyle c_{i}}$${\displaystyle a_{i},\,i\in \{1,2,\dots ,n\}}$${\textstyle L(C(W))=\sum _{i=1}^{n}w_{i}\operatorname {length} (c_{i})}$${\displaystyle C}$${\displaystyle L(C(W))\leq L(T(W))}$${\displaystyle T(W)}$

Presentamos un ejemplo del resultado de la codificación Huffman para un código de cinco caracteres con 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 biúnico , es decir, que se puede decodificar de forma única , la suma de las probabilidades de todos los símbolos siempre es menor o igual a uno. En este ejemplo, la suma es estrictamente igual a uno; por lo tanto, el código se denomina código completo . Si este no es el caso, siempre se puede derivar un código equivalente añadiendo símbolos adicionales (con probabilidades nulas asociadas) para que el código sea completo sin dejar de ser biúnico .

Según lo define Shannon (1948) , el contenido de información h (en bits) de cada símbolo a _i con probabilidad no nula es

${\displaystyle h(a_{i})=\log _{2}{1 \over w_{i}}.}$

La entropía H (en bits) es la suma ponderada, sobre todos los símbolos a _i con probabilidad no nula w _i , del contenido de información de cada símbolo:

$${\displaystyle H(A)=\sum _{w_{i}>0}w_{i}h(a_{i})=\sum _{w_{i}>0}w_{i}\log _{2}{1 \over w_{i}}=-\sum _{w_{i}>0}w_{i}\log _{2}w_{i}.}$$

(Nota: Un símbolo con probabilidad cero no contribuye a la entropía, ya que . Por lo tanto, para simplificar, los símbolos con probabilidad cero pueden omitirse de la fórmula anterior).${\displaystyle \lim _{w\to 0^{+}}w\log _{2}w=0}$

Como consecuencia del teorema de codificación de fuente de Shannon , la entropía es una medida de la longitud mínima de palabra clave teóricamente posible para el alfabeto dado, con sus ponderaciones asociadas. En este ejemplo, la longitud promedio ponderada de la palabra clave es de 2,25 bits por símbolo, solo ligeramente superior a 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 ofrece un mejor rendimiento, sino que además se aproxima mucho al límite teórico establecido por Shannon.

En general, un código de Huffman no tiene por qué 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 dicha distribución. (Sin embargo, para cada asignación de longitud de palabra clave que minimiza, existe al menos un código de Huffman con esa longitud).${\displaystyle L(C)}$

La técnica funciona creando un árbol binario de nodos. Estos se pueden almacenar en un array 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 padre que facilita la lectura del código (en orden inverso) a partir de un nodo hoja. Los nodos internos contienen un peso , enlaces a dos nodos hijos 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 Huffman que omite los símbolos no utilizados produce las longitudes de código más óptimas.${\displaystyle n}$${\displaystyle n}$${\displaystyle n-1}$

The process begins with the leaf nodes containing the probabilities of the symbol they represent. Then, the process takes the two nodes with smallest probability, and creates a new internal node having these two nodes as children. The weight of the new node is set to the sum of the weight of the children. We then apply the process again, on the new internal node and on the remaining nodes (i.e., we exclude the two leaf nodes), we repeat this process until only one node remains, which is the root of the Huffman tree.

The simplest construction algorithm uses a priority queue where the node with lowest probability is given highest priority:

1. Create a leaf node for each symbol and add it to the priority queue.
2. While there is more than one node in the queue:
   1. Remove the two nodes of highest priority (lowest probability) from the queue
   2. Create a new internal node with these two nodes as children and with probability equal to the sum of the two nodes' probabilities.
   3. Add the new node to the queue.
3. The remaining node is the root node and the tree is complete.

Since efficient priority queue data structures require O(log n) time per insertion, and a tree with n leaves has 2n−1 nodes, this algorithm operates in O(n log n) time, where n is the number of symbols.

If the symbols are sorted by probability, there is a linear-time (O(n)) method to create a Huffman tree using two queues, the first one containing the initial weights (along with pointers to the associated leaves), and combined weights (along with pointers to the trees) being put in the back of the second queue. This assures that the lowest weight is always kept at the front of one of the two queues:^[2]

1. Start with as many leaves as there are symbols.
2. Enqueue all leaf nodes into the first queue (by probability in increasing order so that the least likely item is in the head of the queue).
3. While there is more than one node in the queues:
   1. Dequeue the two nodes with the lowest weight by examining the fronts of both queues.
   2. Create a new internal node, with the two just-removed nodes as children (either node can be either child) and the sum of their weights as the new weight.
   3. Enqueue the new node into the rear of the second queue.
4. The remaining node is the root node; the tree has now been generated.

Once the Huffman tree has been generated, it is traversed to generate a dictionary which maps the symbols to binary codes as follows:

1. Start with current node set to the root.
2. If node is not a leaf node, label the edge to the left child as 0 and the edge to the right child as 1. Repeat the process at both the left child and the right child.

La codificación final de cualquier símbolo se obtiene mediante la concatenación de las etiquetas de las aristas a lo largo del camino 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, ya que n es el número de símbolos en el alfabeto, que suele ser 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.

Generalmente, es beneficioso minimizar la varianza de la longitud de las palabras clave. Por ejemplo, un búfer de comunicación que recibe datos codificados con Huffman podría necesitar ser más grande para procesar símbolos especialmente largos si el árbol está particularmente desequilibrado. Para minimizar la varianza, basta con resolver los empates entre colas seleccionando el elemento de la primera cola. Esta modificación conservará la optimalidad matemática de la codificación Huffman, a la vez que minimiza la varianza y la longitud del código de carácter más largo.

En términos generales, el proceso de descompresión consiste simplemente en traducir la secuencia de códigos de prefijo a valores de byte individuales, normalmente recorriendo el árbol de Huffman nodo por nodo a medida que se lee cada bit de la secuencia de entrada (llegar a un nodo hoja necesariamente finaliza la búsqueda de ese valor de byte en particular). Sin embargo, antes de que esto pueda ocurrir, 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 puede preconstruirse (e incluso ajustarse estadísticamente en cada ciclo de compresión) y, por lo tanto, reutilizarse cada vez, a costa de al menos cierta 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 a la secuencia 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 puede reconstruirse 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, bit a bit, al flujo de salida. Por ejemplo, suponiendo que el valor 0 representa un nodo padre y el 1 un nodo hoja, cada vez que se encuentra 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 punto, el árbol de Huffman se reconstruirá fielmente. La sobrecarga que supone 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 generar la salida. Esto se puede lograr transmitiendo la longitud de los datos comprimidos 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 a la optimalidad de la longitud del código).${\displaystyle B\cdot 2^{B}}$

El algoritmo original de Huffman es óptimo para la codificación símbolo por símbolo con una distribución de probabilidad de entrada conocida, es decir, codificando por separado símbolos no relacionados en un flujo de datos de este tipo. Sin embargo, no es óptimo cuando se elimina la restricción de codificación símbolo por símbolo o cuando se desconocen las funciones de probabilidad . Además, si los símbolos no son independientes ni tienen la misma distribución , un solo código puede resultar insuficiente para lograr la optimalidad. Otros métodos, como la codificación aritmética, suelen ofrecer una mejor capacidad de compresión.

Aunque ambos métodos mencionados pueden combinar 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, la codificación aritmética lo hace sin aumentar significativamente su complejidad computacional o algorítmica (si bien la versión más simple es más lenta y compleja que la codificación Huffman). Esta flexibilidad resulta especialmente útil cuando las probabilidades de entrada no se conocen con precisión o varían significativamente dentro del flujo de datos. Sin embargo, la codificación Huffman suele ser más rápida y la codificación aritmética fue históricamente objeto de cierta preocupación debido a problemas 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 pasaron a ser de dominio público al expirar las primeras patentes.

Para un conjunto de símbolos con una distribución de probabilidad uniforme y un número de elementos que es potencia de dos , la codificación Huffman es equivalente a la codificación binaria simple , por ejemplo, la codificación ASCII . Esto refleja que la compresión no es posible con dicha entrada, independientemente del método de compresión; es decir, no modificar los datos es la opción óptima.

La codificación Huffman es óptima entre todos los métodos en cualquier caso donde cada posición en el flujo de entrada sea una variable aleatoria conocida, independiente e idénticamente distribuida, con una probabilidad diádica . Los códigos de prefijo, y por lo tanto la codificación Huffman en particular, tienden a ser ineficientes en alfabetos pequeños, donde las probabilidades suelen caer entre estos puntos óptimos (diádicos). El peor caso para la codificación Huffman puede ocurrir cuando la probabilidad del símbolo más probable supera ampliamente 2 ⁻¹ = 0,5, lo que hace que el límite superior de ineficiencia sea ilimitado.

Existen dos enfoques relacionados para sortear esta ineficiencia particular sin dejar de utilizar la codificación Huffman. Combinar un número fijo de símbolos ("bloqueo") suele aumentar (y nunca disminuir) la compresión. A medida que el tamaño del bloque tiende a infinito, la codificación Huffman se aproxima teóricamente al límite de entropía, es decir, a la compresión óptima. ^{[ 6 ]} Sin embargo, bloquear grupos de símbolos arbitrariamente grandes resulta poco práctico, ya que la complejidad de un código Huffman es lineal con respecto al número de posibilidades a codificar, un número que es exponencial con respecto al 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 previo a la codificación de entropía, específicamente el conteo (secuencias) 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 codificar la longitud de ejecución, un hecho demostrado mediante las técnicas de codificación de Huffman. ^{[ 7 ]} Las máquinas de fax adoptan un enfoque similar utilizando una codificación de Huffman modificada . Sin embargo, la codificación de longitud de ejecución no es tan adaptable a tantos tipos de entrada como otras tecnologías de compresión.

El algoritmo de Huffman n -ario utiliza un alfabeto de tamaño n , típicamente {0, 1, ..., n-1}, para codificar mensajes y construir un árbol n -ario. Este enfoque fue considerado por Huffman en su artículo original. El mismo algoritmo se aplica que para los códigos binarios ( ), pero en lugar de combinar los dos símbolos menos probables, se agrupan los n símbolos menos probables.${\displaystyle n=2}$

Nótese que para n > 2, no todos los conjuntos de palabras fuente pueden formar correctamente un árbol n -ario completo para la codificación Huffman. En estos casos, puede ser necesario añadir símbolos de marcador de posición adicionales con probabilidad 0. Esto se debe a que la estructura del árbol necesita unir repetidamente n ramas en una, también conocida como combinación " n a 1". Para la codificación binaria, esta es una combinación "2 a 1", que funciona con cualquier número de símbolos. Para la codificación n -aria, un árbol completo solo es posible cuando el número total de símbolos (reales + marcadores de posición) deja un resto de 1 al dividirse por (n-1). ^{[ 1 ]}

Una variante denominada codificación Huffman adaptativa consiste en calcular las probabilidades dinámicamente a partir de las frecuencias reales recientes en la secuencia de símbolos fuente, y modificar la estructura del árbol de codificación para que coincida con las estimaciones de probabilidad actualizadas. En la práctica, se utiliza con poca frecuencia, ya que el coste de actualizar el árbol la hace más lenta que la codificación aritmética adaptativa optimizada , que es más flexible y ofrece una mejor compresión.

Por lo general, los pesos utilizados en las implementaciones de la codificación de Huffman representan probabilidades numéricas, pero el algoritmo descrito anteriormente no lo requiere; solo exige 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 de , un problema que se aplicó por primera vez al diseño de circuitos.${\displaystyle \max _{i}\left[w_{i}+\mathrm {length} \left(c_{i}\right)\right]}$

La codificación Huffman con longitud limitada es una variante donde el objetivo sigue siendo lograr una longitud de ruta ponderada mínima, pero existe la restricción adicional de que la longitud de cada palabra clave debe ser menor que una constante dada. El algoritmo package-merge resuelve este problema con un enfoque voraz simple muy similar al utilizado por el algoritmo de Huffman. Su complejidad temporal es , donde es la longitud máxima de una palabra clave. No se conoce ningún algoritmo que resuelva este problema en o tiempo, a diferencia de los problemas de Huffman convencionales preordenados y no ordenados, respectivamente.${\displaystyle O(nL)}$${\displaystyle L}$${\displaystyle O(n)}$${\displaystyle O(n\log n)}$

En el problema estándar de codificación de Huffman, se supone que cada símbolo del conjunto a partir del cual se construyen las palabras clave tiene el mismo coste de transmisión: una palabra clave de N dígitos siempre tendrá un coste de N , independientemente de cuántos de esos dígitos sean 0, cuántos sean 1, etc. Bajo esta suposición, minimizar el coste total del mensaje y minimizar el número total de dígitos equivalen a lo mismo.

La codificación Huffman con costos de letras desiguales es la generalización sin esta suposición: 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 una raya tarda más en enviarse que un punto, y por lo tanto, el costo de una raya en tiempo de transmisión es mayor. El objetivo sigue siendo minimizar la longitud promedio ponderada de la palabra clave, pero ya no basta con 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 Huffman convencional, aunque fue resuelto por Richard M. Karp ^{[ 9 ],} cuya solución fue refinada para el caso de costos enteros por Mordecai J. Golin ^{[ 10 ] .}

En el problema de codificación de Huffman estándar, se supone que cualquier palabra clave 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. Por lo tanto, por ejemplo, no se podría asignar el código , sino que se debería asignar o . Esto también se conoce como el problema de Hu-Tucker , en honor a TC Hu y Alan Tucker , autores del artículo que presenta la primera solución en tiempo a este problema binario alfabético ó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 de 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 . ^{[ 12 ]}${\displaystyle A=\left\{a,b,c\right\}}$${\displaystyle H\left(A,C\right)=\left\{00,1,01\right\}}$${\displaystyle H\left(A,C\right)=\left\{00,01,1\right\}}$${\displaystyle H\left(A,C\right)=\left\{0,10,11\right\}}$${\displaystyle O(n\log n)}$

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 (re)ordenada numéricamente a veces se llama código Huffman canónico y es a menudo el código que se usa en la práctica, debido a la facilidad de codificación/decodificación. La técnica para encontrar este código a veces se llama codificación Huffman-Shannon-Fano , ya que es óptimo como la codificación Huffman, pero alfabético en probabilidad de peso, como la codificación Shannon-Fano . El código Huffman-Shannon-Fano correspondiente al ejemplo es , que, al tener las mismas longitudes de palabra clave que la solución original, también es óptimo. Pero en el código Huffman canónico , el resultado es .${\displaystyle \{000,001,01,10,11\}}$${\displaystyle \{110,111,00,01,10\}}$