Código canónico de Huffman

Un código canónico de Huffman es un tipo particular de codificación Huffman que tiene la propiedad de poder ser descrito de una forma muy compacta.

Los compresores de datos generalmente trabajan de una de dos formas posibles. O bien el descompresor puede inferir qué árbol de Huffman utilizó el compresor para un contexto anterior, o el compresor debe decirle al descompresor cuál es el árbol de Huffman que utilizó para construir el código. Dado que un código canónico de Huffman puede ser almacenado de manera más eficiente, muchos compresores comienzan generando un árbol de Huffman normal, y lo convierten a un árbol de Huffman canónico antes de utilizarlo.

Algoritmo

El algoritmo normal de codificación Huffman asigna un código de longitud variable a cada símbolo en el alfabeto. Los símbolos más frecuentemente usados tendrán asignados códigos más cortos. Por ejemplo, suponga que tenemos la siguiente codificación no-canónica:

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

Aquí a la letra A se le han asignado 2 bits, 1 bit a la B, y 3 bits tanto a la letra C como a la D. Para hacer un código canónico de Huffman, los códigos son re-enumerados. Las longitudes de bit que están en el diccionario de códigos se ordenan primero por la longitud del código y en segundo lugar por el valor alfabético:

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

Cada uno de los códigos existentes es reemplazado con uno nuevo de la misma longitud, usando el siguiente algoritmo:

• El primer símbolo de la lista toma un código que es de la misma longitud que el símbolo del código original, pero con todos ceros. Esto a veces sólo será un cero ('0').
• A cada uno de los siguientes símbolos se le asigna el próximo número binario de la secuencia, asegurándose que los siguientes códigos sean siempre superiores en valor.
• Cuando se alcanza el código más largo de la lista, luego de haber incrementado, agregar ceros hasta que la longitud del nuevo código sea igual que la longitud del código original. Esto puede se interpretado como un desplazamiento a la izquierda.

Siguiendo las tres reglas mencionadas anteriormente, la versión canónica del diccionario de códigos producida será:

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

Codificando el diccionario

La ventaja de un árbol canónico de Huffman es que uno puede codificar la descripción (el diccionario de códigos) en menos bits que en un árbol totalmente descrito.

Tomemos un diccionario de códigos de Huffman original:

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

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

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

Una vez que listamos los símbolos en orden alfabético secuencial, podemos omitir los símbolos propiamente dichos, listando solo el número 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ética secuencial y que posteriormente el código será siempre superior en valor que un código anterior. La único que queda transmitir son las longitudes de los bits (número de bits) para cada símbolo. Tenga en cuenta que nuestro árbol canónico de Huffman siempre tiene valores superiores para las longitudes más largas de bit y que cualquier símbolo de la misma longitud de bit (C y D) tiene valor de código superior para símbolos superiores:

A = 10    (code value: 2 decimal, bits: 2)
B = 0     (code value: 0 decimal, bits: 1)
C = 110   (code value: 6 decimal, bits: 3)
D = 111   (code value: 7 decimal, bits: 3)

Dado que las dos terceras partes de las limitaciones son conocidas, solo el número de bits para cada símbolo necesita ser transmitido.

2, 1, 3, 3

Con éste conocimiento del algoritmo canónico de Huffman, es entonces posible recrear la tabla entera (símbolo y valores de código) solo con la longitud de los bits. Los símbolos no usados son normalmente transmitidos como bits que tienen longitud cero.

Pseudo código

El pseudo código para la construcción de una tabla canónica de Huffman podría ser parecido al siguiente:

codigo = 0
while hay_mas_simbolos:
    imprimir simbolo, codigo
    codigo = codigo + (1 << (longitud_bit_actual -1))
    if longitud_bit_siguiente > longitud_bit_actual:
        codigo = codigo << (longitud_bit_siguiente - longitud_bit_actual)