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 una manera muy compacta. En lugar de almacenar la estructura del árbol de códigos explícitamente, los códigos Huffman canónicos se ordenan de tal manera que basta con almacenar solo las longitudes de las palabras de código, lo que reduce la sobrecarga del libro de códigos.

Los compresores de datos generalmente funcionan de una de dos maneras. El descompresor puede inferir qué libro de códigos ha utilizado el compresor a partir del contexto anterior, o el compresor debe decirle al descompresor cuál es el libro de códigos. Dado que un libro de códigos Huffman canónico se puede almacenar de manera especialmente eficiente, la mayoría de los compresores comienzan generando un libro de códigos Huffman "normal" y luego lo convierten a Huffman canónico antes de usarlo.

Para que un esquema de código de símbolos como el código de Huffman pueda descomprimirse, el mismo modelo que el algoritmo de codificación utilizó para comprimir los datos de origen debe proporcionarse al algoritmo de decodificación para que pueda usarlo para descomprimir los datos codificados. En la codificación estándar de Huffman, este modelo adopta la forma de un árbol de códigos de longitud variable, con los símbolos más frecuentes ubicados en la parte superior de la estructura y representados por la menor cantidad 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 secundarios o al símbolo que representa. Esto es costoso en términos de uso de memoria y, si hay una gran 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 en general. En segundo lugar, recorrer el árbol es costoso en términos computacionales, ya que requiere que el algoritmo salte aleatoriamente a través de la estructura en la 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 claro; a todos los códigos para una longitud dada se les asignan sus valores de manera secuencial. 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 para que sea computacionalmente eficiente.

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 a la D 3 bits. Para que el código sea un código Huffman canónico, se vuelven a numerar los códigos. Las longitudes de bits permanecen iguales y el libro de códigos se ordena primero por la longitud de la palabra de código y segundo 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:

• El primero símbolo en la lista se asigna una palabra clave que es la misma longitud que la palabra clave original del símbolo pero todos los ceros. Esto a menudo será un solo cero ('0').
• Cada símbolo posterior se asigna el siguiente número binario en secuencia, asegurando que los siguientes códigos siempre sean más altos en valor.
• Cuando llegues a una palabra clave más larga, entonces después aumento, Apéndice ceros hasta que la longitud de la nueva palabra clave sea igual a la longitud de la antigua palabra clave. Esto se puede pensar como un turno izquierdo.

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

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

Otra perspectiva sobre las palabras clave canónicas es que son los dígitos después del punto de la base (punto binario) en una representación binaria de una serie determinada. En concreto, supongamos que las longitudes de las palabras clave son l₁... l_n. Entonces, la palabra clave canónica para el símbolo i son los primeros l_i dígitos binarios después del punto de la base en la representación binaria de

${\displaystyle \sum _{j=1}{i-1}2^{-l_{j}}$

Esta perspectiva es particularmente útil a la luz de la desigualdad de Kraft, que dice que la suma anterior siempre será menor o igual a 1 (ya que las longitudes provienen de un código sin prefijo). Esto demuestra que agregar uno en el algoritmo anterior nunca se desborda y crea una palabra de código que es más larga de lo previsto.

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

Tomemos nuestro libro de códigos original de Huffman:

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

Existen varias formas de 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 enumeramos los símbolos en orden alfabético secuencial, podemos omitir los símbolos en sí y enumerar solo la cantidad de bits y el código:

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

Con nuestra versión canónica tenemos el conocimiento de 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. Las únicas partes que quedan por transmitir son las longitudes de bits (número de bits) para cada símbolo. Tenga en cuenta que nuestro árbol de Huffman canónico siempre tiene valores más altos para longitudes de bits más largas y que cualquier símbolo de la misma longitud de bits (C y D) tiene valores de código más altos para símbolos más altos:

A = 10 (valor de código: 2 decimales, bits: 2)
B = 0 (valor de código: 0 decimal, bits: 1)
C = 110 (valor de código: 6 decimales, bits: 3)
D = 111 (valor de código: 7 decimales, 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

Con el conocimiento del algoritmo canónico de Huffman, es posible recrear la tabla completa (valores de símbolos y códigos) a partir de las longitudes de bits únicamente. Los símbolos no utilizados normalmente se transmiten como si tuvieran una longitud de bits cero.

Otra forma eficiente de representar el libro de códigos es enumerar todos los símbolos en orden creciente según su longitud de bits y registrar la cantidad de símbolos para cada longitud de bit. Para el ejemplo mencionado anteriormente, la codificación se convierte en:

(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 otros dos símbolos (C y D) tienen una longitud de 3. Como los símbolos están ordenados por longitud de bits, podemos reconstruir el libro 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 se comprimen solo 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 utilizando el método anterior, necesitamos agregar muchos ceros (Método 1):

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

o registre las 4 letras que hemos usado. Cada método 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 más símbolos dosímbolo de impresión, código código:=código + 1) se realizó (longitud del bit del siguiente símbolo) - (longitud del bit corriente)

algoritmo Código de Huffman es entrada: conjunto de mensajes (conjunto de (mensaje, probabilidad)).
base D.
 Producto: code ensemble (set of (message, code)).

1- ordenar el mensaje conjunto disminuyendo la probabilidad.
2- N es el cardenal del conjunto del mensaje (número de diferente
mensajes).
3- computar el entero ⁠${\displaystyle No.$⁠ tales como ⁠${\displaystyle 2\leq n_{0}\leq D}$⁠ y ⁠${\displaystyle (N-n_{0})/(D-1)}$⁠ es entero.
4- seleccionar el ⁠${\displaystyle No.$⁠ mensajes menos probables, y asignar cada uno a
Código digital.
5- sustituir los mensajes seleccionados por un mensaje compuesto resumiendo
su probabilidad, y reordenarlo.
6- mientras que queda más de un mensaje, haga pasos a través de 8.
7- select D mensajes menos probables, y asignar cada uno a
Código digital.
8- sustituir los mensajes seleccionados por un mensaje compuesto
resumiendo su probabilidad, y reordenarlo.
9- el código de cada mensaje es dado por la concatenación del
dígitos de código del agregado que han sido puestos.