Codificación Huffman

format_list_bulleted Contenido keyboard_arrow_down

ImprimirCitar

Técnica para comprimir datos

Árbol Huffman generado a partir de las frecuencias exactas del texto "este es un ejemplo de un árbol huffman". Las frecuencias y códigos de cada personaje están abajo. La codificación de la frase con este código requiere 135 (o 147) bits, en lugar de 288 (o 180) bits si se utilizaron 36 caracteres de 8 (o 5) bits. (Esto supone que la estructura del árbol de código es conocida por el decodificador y por lo tanto no necesita ser contado como parte de la información transmitida.)

Char	Freq	Código
espacio	7	111
a	4	010
e	4	000
f	3	1101
h	2	Graben 19, 1010
i	2	1000
m	2	0111
n	2	0010
s	2	1011
t	2	0110
l	1	11001
o	1	00110
p	1	10011
r	1	11000
u	1	00111
x	1	10010

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 mediante la codificación Huffman, un algoritmo desarrollado por David A. Huffman cuando era 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".

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. Sin embargo, aunque es óptimo entre los métodos que codifican símbolos por separado, la codificación Huffman no siempre es óptima entre todos los métodos de compresión: se reemplaza con codificación aritmética o sistemas numéricos asimétricos si se requiere una mejor relación de compresión.

Historia

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 parcial 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.

Al hacerlo, Huffman superó a Fano, quien había trabajado con 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.

Terminología

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 Huffman es un método tan extendido para crear códigos de prefijo que el término "código 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.

Definición del problema

Construyendo un Huffman Árbol

Descripción informal

Dado: Un conjunto de símbolos y sus pesos (generalmente proporcionales a las probabilidades).
Encontrar: Un código binario libre de prefijo (un conjunto de palabras clave) con la longitud mínima de la palabra clave esperada (equivalentemente, un árbol con la longitud mínima del camino ponderado de la raíz).

Descripción formalizada

Input.
Alfabeto ${displaystyle A=(a_{1},a_{2},dotsa_{n})}$ , que es el alfabeto símbolo del tamaño $n$ .
Tuple ${displaystyle W=(w_{1},w_{2},dotsw_{n})}$ , que es el tuple de los pesos del símbolo (positivo) (generalmente proporcional a las probabilidades), es decir. ${displaystyle w_{i}=operatorname {weight} left(a_{i}right),,iin {1,2,dotsn}}$ .

Producto.
Código ${displaystyle Cleft(Wright)=(c_{1},c_{2},dotsc_{n})}$ , que es el tuple de las palabras clave (binarias), donde $c_{i}$ es la palabra clave para ${displaystyle a_{i},,iin {1,2,dotsn}}$ .

Objetivo.
Vamos ${textstyle Lleft(Cleft(Wright)right)=sum _{i=1}^{n}{w_{i}operatorname {length} left(c_{i}right)}}$ ser la longitud de la ruta ponderada del código $C$ . Estado: ${displaystyle Lleft(Cleft(Wright)right)leq Lleft(Tleft(Wright)right)}$ para cualquier código ${displaystyle Tleft(Wright)}$ .

Ejemplo

Damos un ejemplo del resultado de la codificación de Huffman para un código con cinco caracteres y pesos dados. No verificaremos que minimiza L sobre todos los códigos, pero calcularemos L y lo compararemos con la entropía de Shannon H del conjunto dado de pesas; el resultado es casi óptimo.

Input (Input)A, W)	Signatura (continuación) $a i$ )	a	b	c	d	e	Sum
Input (Input)A, W)	Pesos ( $w i$ )	0.10	0.15	0.30	0.16	0.29	= 1
Producto C	Codewords ( $c i$ )	`010`	`011`	`11`	`00`	`10`
	Longitud del código (en bits) () $l i$ )	3	3	2	2	2
	Contribución a la longitud de la ruta ponderada () $l i$ $w i$ )	0.30	0.45	0.60	0.32	0,58	L()C) = 2.25
Optimality	Presupuesto de probabilidad () $2 - l i$ )	1/8	1/8	1/4	1/4	1/4	= 1.00
	Contenido de información (en bits) () $-log 2 w i$ )	3.32	2.74	1.74	2.64	1.79
	Contribución a la entropía () $- w i log 2 w i$ )	0.332	0.411	0.521	0.423	0.518	H()A) = 2.205

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 en 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 completar el código y mantenerlo biunico.

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

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

La entropía H (en bits) es la suma ponderada, en todos los símbolos $a i$ con probabilidad distinta de cero $w i$ , del contenido informativo de cada símbolo:

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}}.}" xmlns="http://www.w3.org/1998/Math/MathML">H()A)=.. wi■0wih()ai)=.. wi■0wilog2⁡ ⁡ 1wi=− − .. wi■0wilog2⁡ ⁡ wi.{displaystyle H(A)=sum ¿Qué? _{2}{1over ¿Qué? ¿Qué? ¿Qué?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}}." aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/1be32c5fb44ffa0961a0cf1d506e0bca05c7c3eb" style="vertical-align: -3.338ex; width:58.555ex; height:6.676ex;"/>

(Nota: Un símbolo con probabilidad cero tiene cero contribución a la entropía, ya que $lim _{wto 0^{+}}wlog _{2}w=0$ . Así que para la simplicidad, los símbolos con cero probabilidad se pueden dejar fuera 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 clave más pequeña que es teóricamente posible para el alfabeto dado con los pesos asociados. En este ejemplo, la longitud media ponderada de la palabra clave 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. Entonces, 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 Huffman no necesita ser único. Así, el conjunto de códigos Huffman para una distribución de probabilidad dada es un subconjunto no vacío de los códigos minimizando $L(C)$ para esa distribución de probabilidad. (Sin embargo, para cada asignación de longitud de la palabra clave minimizante, existe al menos un código Huffman con esas longitudes.)

Técnica básica

Compresión

Visualización del uso de 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 clasifican por frecuencia creciente, y los dos menos frecuentes a cada paso se combinan y se reinsertan en la lista, y se construye un árbol parcial. El árbol final en el paso 6 es atravesado para generar el diccionario en el paso 7. Paso 8 lo usa para codificar el mensaje.

Una fuente genera 4 símbolos diferentes

{a_{1},a_{2},a_{3},a_{4}}

con probabilidad

{0.4;0.35;0.2;0.05}

. Un árbol binario se genera de izquierda a derecha tomando los dos símbolos menos probables y juntarlos para formar otro símbolo equivalente con una probabilidad que equivale a la suma de los dos símbolos. El proceso se repite hasta que haya un solo símbolo. El árbol puede ser leído hacia atrás, de derecha a izquierda, asignando diferentes bits a diferentes ramas. El código final de Huffman es:

Signatura	Código
a1	0
a2	10
a3	110
a4	111

La forma estándar de representar una señal hecha de 4 símbolos es usando 2 bits/symbol, pero la entropía de la fuente es 1.74 bits/symbol. Si este código Huffman se utiliza para representar la señal, entonces la longitud promedio se reduce a 1,85 bits/symbol; todavía está lejos del límite teórico porque las probabilidades de los símbolos son diferentes de los poderes negativos de dos.

La técnica funciona creando un árbol binario de nodos. Estos pueden almacenarse en un array regular, cuyo tamaño depende del número de símbolos, $n$ . Un nodo puede ser un nodo de hoja o un nodo interno. Inicialmente, todos los nodos son nodos de hoja, que contienen símbolo en sí mismo, peso (frecuencia de la apariencia) del símbolo y opcionalmente, un enlace a un padre nodo que hace fácil leer el código (en reversa) a partir de un nodo de hoja. Los ganglios internos contienen peso, enlaces a dos nodos infantiles y un enlace opcional a padre Nodo. Como convención común, bit '0' representa siguiendo al niño izquierdo y bit '1' representa siguiendo al niño derecho. Un árbol acabado tiene hasta $n$ nodos de hoja y $n-1$ Nodos internos. Un árbol Huffman que omite 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 en la que el nodo con la probabilidad más baja recibe la prioridad más alta:

Crear un nodo de hoja para cada símbolo y añadirlo a la cola de prioridad.
Mientras hay más de un nodo en la cola:
1. Quitar los dos nodos de máxima prioridad (probabilidad más baja) de la cola
2. Cree un nuevo nodo interno con estos dos nodos como niños y con probabilidad igual a la suma de las probabilidades de los dos nodos.
3. Añadir el nuevo nodo a la cola.
El nodo restante es el nodo raíz y el árbol está completo.

Dado que las estructuras de datos de cola de prioridad eficientes requieren O(log n) tiempo por inserción, y un árbol con n hojas tiene 2n− 1 nodos, este algoritmo opera en tiempo O(n log n), donde n es el número de símbolos.

Si los símbolos se ordenan por probabilidad, hay 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 pesos combinados (junto con punteros a los árboles) que se colocan 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:

Comience con tantas hojas como hay símbolos.
Encargar todos los nodos de hoja en la primera cola (por probabilidad en orden creciente para que el elemento menos probable está en la cabeza de la cola).
Mientras hay más de un nodo en las colas:
1. Dequeue los dos nodos con el peso más bajo examinando los frentes de ambas colas.
2. Crear un nuevo nodo interno, con los dos nodos simplemente removidos como niños (ya el nodo puede ser niño) y la suma de sus pesos como el nuevo peso.
3. Adquirir el nuevo nodo en la parte trasera de la segunda cola.
El nodo restante es el nodo raíz; el árbol se ha generado ahora.

Una vez que se ha generado el árbol de Huffman, se recorre para generar un diccionario que asigna los símbolos a los códigos binarios de la siguiente manera:

Comience con el nodo actual fijado en la raíz.
Si el nodo no es un nodo de hoja, etiqueta el borde al niño izquierdo como 0 y el borde del niño derecho como 1. Repita el proceso tanto en el niño izquierdo como en el niño derecho.

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 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 suele ser un número muy pequeño (en comparación con el longitud del mensaje a codificar); mientras que el análisis de complejidad se refiere al comportamiento cuando n crece hasta ser muy grande.

Por lo general, 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 por 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 empates entre las colas eligiendo el artículo en la primera cola. Esta modificación conservará la optimización matemática de la codificación de Huffman mientras minimiza la varianza y minimiza la longitud del código de caracteres más largo.

Descompresión

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 individuales de byte, por lo general atravesando el nodo de árbol Huffman por nodo, ya que cada bit se lee en el flujo de entrada (realizar un nodo de hoja termina necesariamente la búsqueda de ese valor particular de byte). Sin embargo, antes de que esto ocurra, el árbol Huffman debe ser reconstruido de alguna manera. En el caso más simple, donde las frecuencias de carácter son bastante predecibles, el árbol puede ser preconstruido (y incluso ajustado estadísticamente en cada ciclo de compresión) y así reutilizado 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 ser enviada a priori. Un enfoque ingenuo podría ser prepensionar el recuento de frecuencia de cada personaje al flujo de compresión. Desafortunadamente, el sobrecabezamiento en tal caso podría ser de 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 puede ser reconstruido con solo ${displaystyle Bcdot 2^{B}}$ bits of information (where $B$ es el número de bits por símbolo). Otro método es simplemente prependir el árbol Huffman, poco a poco, a la corriente de salida. Por ejemplo, asumiendo que el valor de 0 representa un nodo padre y 1 un nodo de hoja, cada vez que éste se encuentra con la rutina de construcción de árboles 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 alcance el último nodo de hoja; en ese momento, el árbol Huffman será reconstruido fielmente. La parte superior que utiliza este método varía de aproximadamente 2 a 320 bytes (asumiendo un alfabeto de 8 bits). Muchas otras técnicas también son posibles. En cualquier caso, ya que los datos comprimidos pueden incluir " bits de navegación" no utilizados, el descompresor debe ser capaz de determinar cuándo dejar de producir la salida. Esto se puede lograr mediante la transmisión de la longitud de los datos descomprimidos junto con el modelo de compresión o la definición de un símbolo de código especial para significar el final de la entrada (este último método puede afectar negativamente la optimización de la longitud del código, sin embargo).

Propiedades principales

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 comprime. Esto requiere que se almacene una tabla de frecuencias 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.

Optimidad

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 un flujo de datos de este tipo. 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 y están distribuidos de manera idéntica, un solo código puede ser insuficiente para 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 mencionados anteriormente pueden combinar un número arbitrario de símbolos para 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 compleja que 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 ha sido históricamente un tema de 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 Huffman pasaron al dominio público debido a que las primeras patentes expiraron.

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 Huffman es equivalente a la codificación de bloque binario simple, por ejemplo, la codificación ASCII. Esto refleja el hecho de que la compresión no es posible con una entrada de este tipo, independientemente del método de compresión, es decir, lo óptimo es no hacer nada con los datos.

La codificación de Huffman es óptima entre todos los métodos en cualquier caso donde cada símbolo de entrada sea una variable aleatoria conocida independiente e idénticamente distribuida que tenga una probabilidad que sea 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 supera con creces 2⁻¹ = 0,5, lo que hace que el límite superior de ineficiencia sea ilimitado.

Hay dos enfoques relacionados para sortear 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 de Huffman teóricamente se acerca al límite de entropía, es decir, a la compresión óptima. Sin embargo, bloquear grupos de símbolos arbitrariamente grandes no es práctico, ya que la complejidad de un código Huffman es lineal en el número de posibilidades de codificación, 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 agrega un paso antes de la codificación de entropía, específicamente contando (ejecuciones) de símbolos repetidos, que luego se codifican. Para el caso simple de los procesos de Bernoulli, la codificación Golomb es óptima entre los códigos de prefijo para codificar la longitud de la ejecución, un hecho demostrado a través de las técnicas de codificación de Huffman. Las máquinas de fax adoptan un enfoque similar que utiliza la codificación 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.

Variaciones

Existen muchas variaciones de la codificación de Huffman, algunas de las cuales usan un algoritmo similar a Huffman y otras encuentran códigos de prefijo óptimos (mientras, por ejemplo, imponen diferentes restricciones en la salida). Tenga en cuenta que, en el último caso, el método no necesita ser como Huffman y, de hecho, ni siquiera necesita ser tiempo polinomial.

Codificación Huffman N-aria

El n-Huffman algoritmo utiliza el {0, 1,... n − 1} alfabeto para codificar el mensaje y construir un n- Árbol. Este enfoque fue considerado por Huffman en su documento original. El mismo algoritmo se aplica para binario ( $n=2$ ) códigos, excepto que los n los símbolos menos probables se toman juntos, en lugar de sólo los 2 menos probables. Tenga en cuenta que n más grande que 2, no todos los conjuntos de palabras fuente pueden formar correctamente n- Árbol diario para la codificación Huffman. En estos casos, deben añadirse otros titulares de puestos de 0 probabilidades. Esto es porque el árbol debe formar un árbol n a 1 contratista; para codificación binaria, éste es un contratista de 2 a 1 y cualquier conjunto de tamaño puede formar tal contratista. Si el número de palabras fuente es congruente con 1 modulo n−1, entonces el conjunto de palabras fuente formará un árbol Huffman adecuado.

Codificación adaptativa de Huffman

Una variación denominada codificación adaptativa de Huffman consiste en calcular las probabilidades dinámicamente en función de 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 una mejor compresión.

Algoritmo de plantilla de Huffman

La mayoría de las veces, los pesos utilizados en las implementaciones de codificación Huffman representan probabilidades numéricas, pero el algoritmo dado anteriormente no requiere esto; sólo requiere que los pesos forman un monoide totalmente ordenado, que significa una manera de ordenar pesos y agregarlos. El algoritmo de plantilla Huffman permite utilizar cualquier tipo de pesos (costos, frecuencias, pares de pesos, pesos no anuales) y uno de muchos métodos de combinación (no sólo adición). Tales algoritmos pueden resolver otros problemas de minimización, como minimizar $max _{i}left[w_{i}+mathrm {length} left(c_{i}right)right]$ , un problema primero aplicado al diseño de circuitos.

Codificación Huffman de longitud limitada/codificación Huffman de varianza mínima

Codificación Huffman limitada de longitud es una variante donde el objetivo todavía es alcanzar una longitud mínima ponderada, pero hay una restricción adicional que la longitud de cada palabra clave debe ser inferior a una constante dada. El algoritmo de combinación de paquetes resuelve este problema con un simple enfoque codicioso muy similar al utilizado por el algoritmo de Huffman. Su complejidad temporal es $O(nL)$ , donde $L$ es la longitud máxima de una palabra clave. Ningún algoritmo es conocido para resolver este problema en $O(n)$ o $O(nlog n)$ tiempo, a diferencia de los problemas de Huffman convencionales prescritos y no variados, respectivamente.

Codificación de Huffman con costos de letras desiguales

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 el mismo costo de transmisión: una palabra de código cuya longitud es N dígitos siempre tienen un costo de N, no importa cuántos de esos dígitos sean 0, cuántos sean 1, etc. Al trabajar bajo esta suposición, 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 costos de letra 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 un 'guion' tarda más en enviarse que un 'punto' y, por lo tanto, el costo de un guión en el tiempo de transmisión es mayor. El objetivo sigue siendo minimizar la longitud media 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 convencional de Huffman, aunque Karp lo resolvió, cuya solución ha sido refinada para el caso de costos enteros por Golin.

Árboles binarios alfabéticos óptimos (codificación Hu-Tucker)

En el problema estándar de codificación Huffman, 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 entrada y salidas debe ser idéntico. Así, por ejemplo, $A=left{a,b,cright}$ no se puede asignar código $Hleft(A,Cright)=left{00,1,01right}$ , pero en su lugar debe ser asignado $Hleft(A,Cright)=left{00,01,1right}$ o $Hleft(A,Cright)=left{0,10,11right}$ . Esto también se conoce como Hu-Tucker problema, después de T. C. Hu y Alan Tucker, los autores del periódico presentando el primer $O(nlog n)$ - Hora solución a este problema alfabético binario óptimo, que tiene algunas similitudes con el algoritmo 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 la lógica más simple para realizar las mismas comparaciones en el mismo tiempo total. Estos árboles binarios alfabético óptimos se utilizan a menudo como árboles de búsqueda binaria.

El código canónico de Huffman

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 al calcular estas longitudes, haciendo innecesaria la codificación Hu-Tucker. El código resultante de la entrada numérica (re-)ordenada a veces se llama el canónica Código Huffman y es a menudo 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 llama Codificación de Huffman–Shannon–Fano, ya que es óptima como la codificación Huffman, pero alfabética en la probabilidad de peso, como la codificación Shannon-Fano. El código Huffman–Shannon–Fano correspondiente al ejemplo es ${000,001,01,10,11}$ , que, teniendo las mismas longitudes de la palabra clave que la solución original, también es óptima. Pero... canónica Código Huffman, el resultado es ${110,111,00,01,10}$ .

Aplicaciones

La codificación aritmética y la codificación de Huffman producen resultados equivalentes, logrando 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 clave" puede tener efectivamente longitudes de bits no enteras, mientras que las palabras de código en códigos de prefijo como los códigos 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 para que coincida exactamente con la verdadera probabilidad del símbolo. Esta diferencia es especialmente llamativa para tamaños de alfabeto pequeños.

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 un "back-end" a otros métodos de compresión. Deflate (algoritmo PKZIP) y los códecs multimedia como JPEG y MP3 tienen un modelo de front-end y cuantificación seguida por el uso de códigos de prefijo; estos a menudo se denominan "códigos Huffman" aunque la mayoría de las aplicaciones utilizan códigos predefinidos de longitud variable en lugar de códigos diseñados con el algoritmo de Huffman.

Contenido relacionado

Más resultados...