Código canónico de Huffman

En informática y teoría de la información , un código Huffman canónico es un tipo particular de código Huffman con propiedades únicas que permiten describirlo de forma muy compacta. En lugar de almacenar explícitamente la estructura del árbol de código, los códigos Huffman canónicos se ordenan de tal manera que basta con almacenar la longitud de las palabras clave, lo que reduce la complejidad del diccionario de códigos.

Los compresores de datos generalmente funcionan de dos maneras. O bien el descompresor puede inferir el diccionario de códigos que el compresor ha utilizado a partir del contexto previo, o bien el compresor debe indicarle al descompresor cuál es dicho diccionario. Dado que un diccionario de códigos Huffman canónico se puede almacenar de forma especialmente eficiente, la mayoría de los compresores comienzan generando un diccionario de códigos Huffman "normal" y luego lo convierten a Huffman canónico antes de utilizarlo.

Para descomprimir un esquema de codificación de símbolos como el código Huffman , el algoritmo de decodificación debe proporcionar el mismo modelo que utilizó el algoritmo de codificación para comprimir los datos originales, de modo que pueda usarlo para descomprimir los datos codificados. En la codificación Huffman estándar, este modelo adopta la forma de un árbol de códigos de longitud variable, donde los símbolos más frecuentes se ubican en la parte superior de la estructura y se representan con el menor número de bits.

Sin embargo, este árbol de código introduce dos ineficiencias críticas en la implementación del esquema de codificación. En primer lugar, cada nodo del árbol debe almacenar referencias a sus nodos hijos o al símbolo que representa. Esto resulta costoso en términos de uso de memoria, y si existe una alta proporción de símbolos únicos en los datos de origen, el tamaño del árbol de código puede representar una cantidad significativa de los datos codificados totales. En segundo lugar, recorrer el árbol es computacionalmente costoso, ya que requiere que el algoritmo salte aleatoriamente a través de la estructura en memoria a medida que se lee cada bit de los datos codificados.

Los códigos Huffman canónicos resuelven estos dos problemas generando los códigos en un formato estandarizado y claro; a todos los códigos de una longitud dada se les asignan sus valores secuencialmente. Esto significa que, en lugar de almacenar la estructura del árbol de códigos para la descompresión, solo se requieren las longitudes de los códigos, lo que reduce el tamaño de los datos codificados. Además, debido a que los códigos son secuenciales, el algoritmo de decodificación se puede simplificar drásticamente, lo que lo hace computacionalmente eficiente.

El algoritmo canónico de Huffman convierte un diccionario de códigos Huffman estándar en una forma estandarizada o canónica. Esto se logra ordenando los símbolos según una convención clara: primero, se ordenan todos los símbolos según la longitud de su palabra clave, de menor a mayor. Segundo, para los símbolos que tienen la misma longitud de palabra clave, se ordenan según su valor alfabético o numérico. Esto crea una lista definitiva y ordenada de símbolos.

El algoritmo de codificación Huffman normal asigna un código de longitud variable a cada símbolo del alfabeto. A los símbolos más utilizados se les asignará un código más corto. Por ejemplo, supongamos que tenemos el siguiente libro de códigos no canónico:

A = 11 B = 0 C = 101 D = 100

Aquí, a la letra A se le han asignado 2 bits , a la B 1 bit, y a la C y la D 3 bits cada una. Para convertir el código en un código Huffman canónico , los códigos se renumeran. La longitud de los bits se mantiene igual, y el libro de códigos se ordena primero por la longitud de la palabra clave y, en segundo lugar, por el valor alfabético de la letra.

B = 0 A = 11 C = 101 D = 100

Cada uno de los códigos existentes se reemplaza por uno nuevo de la misma longitud, utilizando el siguiente algoritmo:

• Al primer símbolo de la lista se le asigna una palabra clave que tiene la misma longitud que la palabra clave original del símbolo, pero compuesta únicamente por ceros. A menudo, esta palabra clave será un solo cero ('0').
• A cada símbolo subsiguiente se le asigna el siguiente número binario en la secuencia, lo que garantiza que los códigos siguientes siempre tengan un valor mayor.
• Cuando se alcanza una palabra clave más larga, después de incrementarla, se añaden ceros hasta que la longitud de la nueva palabra clave sea igual a la longitud de la palabra clave anterior. Esto puede considerarse como un desplazamiento a la izquierda .

Siguiendo estas tres reglas, la versión canónica del libro de códigos resultante será:

B = 0 A = 10 C = 110 D = 111

La ventaja de un árbol de Huffman canónico es que se puede codificar con menos bits que un árbol arbitrario.

Tomemos como referencia nuestro libro de códigos original de Huffman:

A = 11 B = 0 C = 101 D = 100

Hay varias maneras en que podríamos codificar este árbol de Huffman. Por ejemplo, podríamos escribir cada símbolo seguido del número de bits y el código :

('A',2,11), ('B',1,0), ('C',3,101), ('D',3,100)

Dado que estamos enumerando los símbolos en orden alfabético secuencial, podemos omitir los símbolos en sí mismos, enumerando solo el número de bits y el código :

(2,11), (1,0), (3,101), (3,100)

Con nuestra versión canónica, sabemos que los símbolos están en orden alfabético secuencial y que un código posterior siempre tendrá un valor mayor que uno anterior. Lo único que queda por transmitir son las longitudes de bits ( número de bits ) de cada símbolo. Nótese que nuestro árbol de Huffman canónico siempre tiene valores más altos para longitudes de bits mayores y que cualquier símbolo con la misma longitud de bits ( C y D ) tiene valores de código más altos para símbolos superiores.

A = 10 (valor del código: 2 decimal, bits: 2 ) B = 0 (valor del código: 0 decimal, bits: 1 ) C = 110 (valor del código: 6 decimal, bits: 3 ) D = 111 (valor del código: 7 decimal, bits: 3 )

Dado que se conocen dos tercios de las restricciones, solo es necesario transmitir el número de bits para cada símbolo:

2, 1, 3, 3

Conociendo el algoritmo canónico de Huffman, es posible recrear la tabla completa (símbolos y valores de código) a partir únicamente de las longitudes de bits. Los símbolos no utilizados se transmiten normalmente con una longitud de bits de cero.

Otra forma eficiente de representar el libro de códigos es enumerar todos los símbolos en orden ascendente según su longitud en bits y registrar el número de símbolos para cada longitud en bits. Para el ejemplo mencionado anteriormente, la codificación quedaría así:

(1,1,2), ('B','A','C','D')

Esto significa que el primer símbolo B tiene una longitud de 1, luego el A tiene una longitud de 2, y los dos símbolos restantes (C y D) tienen una longitud de 3. Dado que los símbolos están ordenados por longitud de bits, podemos reconstruir el diccionario de códigos de manera eficiente. En la siguiente sección se presenta un pseudocódigo que describe la reconstrucción.

Este tipo de codificación es ventajoso cuando solo se comprimen unos pocos símbolos del alfabeto. Por ejemplo, supongamos que el libro de códigos contiene solo 4 letras C , O , D y E , cada una de longitud 2. Para representar la letra O usando el método anterior, necesitamos agregar muchos ceros (Método 1):

0, 0, 2, 2, 2, 0, ... , 2, ...

o registrar qué 4 letras hemos utilizado. Cada opción hace que la descripción sea más larga que la siguiente (Método 2):

(0,4), ('C','O','D','E')

El formato de intercambio de archivos JPEG utiliza el método 2 de codificación, ya que como máximo solo 162 símbolos del alfabeto de 8 bits , que tiene un tamaño de 256, estarán en el libro de códigos.

Dada una lista de símbolos ordenados por longitud de bits, el siguiente pseudocódigo imprimirá un libro de códigos Huffman canónico:

código := 0 mientras haya más símbolos imprimir símbolo, código código : = ( código + 1) << ((longitud de bits del siguiente símbolo) − (longitud de bits actual))

El algoritmo para calcular el código Huffman es la entrada: conjunto de mensajes (conjunto de (mensaje, probabilidad)). base D . salida: conjunto de códigos (conjunto de (mensaje, código)). 1- Ordenar el conjunto de mensajes por probabilidad decreciente. 2- N es el cardinal del conjunto de mensajes (número de diferentes mensajes). 3- Calcular el número entero${\displaystyle n_{0}}$como por ejemplo${\displaystyle 2\leq n_{0}\leq D}$y​​${\displaystyle (N-n_{0})/(D-1)}$es un número entero. 4- seleccione el ⁠${\displaystyle n_{0}}$mensajes menos probables y asignarles a cada uno un código de dígitos. 5- Sustituir los mensajes seleccionados por una suma de mensajes compuestos. su probabilidad, y reordenarla. 6- Mientras quede más de un mensaje, siga los pasos del 8 al 8. 7- seleccione D mensajes menos probables y asígneles a cada uno un código de dígitos. 8- Sustituya los mensajes seleccionados por un mensaje compuesto. sumando sus probabilidades y reordenándolas. 9- El código de cada mensaje viene dado por la concatenación de los dígitos de código del agregado en el que se han colocado.

^{[ 1 ] [ 2 ]}