Un código de Huffman canónico es un tipo particular de código de Huffman con propiedades únicas que permiten describirlo de una manera muy compacta.
Los compresores de datos generalmente funcionan de dos maneras. O el descompresor puede inferir qué libro de códigos ha utilizado el compresor 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 de Huffman canónico se puede almacenar de manera especialmente eficiente, la mayoría de los compresores comienzan generando un libro de códigos de Huffman "normal" y luego lo convierten en Huffman canónico antes de usarlo.
Para que se descomprima un esquema de código de símbolo como el código de Huffman , 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 utilizarlo para descomprimir los datos codificados. En la codificación estándar de Huffman, este modelo toma 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 el uso de la memoria y si hay una alta proporción de símbolos únicos en los datos de origen, entonces el tamaño del árbol de código puede representar una cantidad significativa de los datos codificados en general. En segundo lugar, atravesar el árbol es computacionalmente costoso, 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 de Canonical Huffman abordan estos dos problemas al generar los códigos en un formato estandarizado claro; a todos los códigos para una longitud determinada se les asignan sus valores de forma 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.
Algoritmo
El algoritmo de codificación normal de Huffman asigna un código de longitud variable a cada símbolo del alfabeto. A los símbolos utilizados con más frecuencia se les asignará un código más corto. Por ejemplo, supongamos que tenemos el siguiente libro de códigos no canónico:
A = 11B = 0C = 101D = 100
Aquí a la letra A se le han asignado 2 bits , B tiene 1 bit y C y D tienen 3 bits. Para convertir el código en un código de Huffman canónico , los códigos se vuelven a numerar. Las longitudes de bits permanecen iguales con el libro de códigos ordenado primero por longitud de palabra de código y en segundo lugar por valor alfabético :
B = 0A = 11C = 101D = 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 de código que tiene la misma longitud que la palabra de código original del símbolo, pero todos ceros. A menudo, será un solo cero ('0').
- A cada símbolo subsiguiente se le asigna el siguiente número binario en secuencia, asegurando que los siguientes códigos sean siempre de mayor valor.
- Al llegar a una palabra de código de tiempo, a continuación, después incrementando, ceros anexados hasta que la longitud de la nueva palabra código es igual a la longitud de la palabra código de edad. Esto se puede considerar como un desplazamiento a la izquierda .
Siguiendo estas tres reglas, la versión canónica del libro de códigos producido será:
B = 0A = 10C = 110D = 111
Como un número binario fraccionario
Otra perspectiva sobre las palabras de código canónicas es que son los dígitos más allá del punto de base (punto decimal binario) en una representación binaria de una determinada serie. Específicamente, suponga que las longitudes de las palabras de código son l 1 ... l n . Entonces, la palabra de código 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
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 libre de prefijo). Esto muestra 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.
Codificación del libro de códigos
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 = 11B = 0C = 101D = 100
Hay 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í, 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 tenemos el conocimiento de que los símbolos están en orden alfabético secuencial y que un código posterior siempre será de mayor valor que uno anterior. Las únicas partes que quedan por transmitir son las longitudes de bits ( número de bits ) de 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 decimal, bits: 2 )B = 0 (valor de código: 0 decimal, bits: 1 )C = 110 (valor de código: 6 decimal, bits: 3 )D = 111 (valor de código: 7 decimal, bits: 3 )
Dado que se conocen dos tercios de las restricciones, solo es necesario transmitir el número de bits de cada símbolo:
2, 1, 3, 3
Con el conocimiento del algoritmo canónico de Huffman, es posible volver a crear la tabla completa (valores de símbolo y código) a partir de solo las longitudes de bits. Los símbolos no utilizados se transmiten normalmente como si tuvieran una longitud de bit cero.
Otra forma eficaz de representar el libro de códigos es enumerar todos los símbolos en orden creciente por sus longitudes de bits y registrar el número de símbolos para cada longitud de bits. 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 es de longitud 1, luego el A de longitud 2 y permanece de 3. Dado que los símbolos están ordenados por longitud de bits, podemos reconstruir eficientemente el libro de códigos. En la siguiente sección se introduce un pseudocódigo que describe la reconstrucción.
Este tipo de codificación es ventajoso cuando solo se comprimen unos pocos símbolos en el alfabeto. Por ejemplo, suponga 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:
0, 0, 2, 2, 2, 0, ..., 2, ...
o registre las 4 letras que hemos utilizado. Cada forma hace que la descripción sea más larga que:
(0,4), ('C', 'O', 'D', 'E')
El formato de intercambio de archivos JPEG utiliza este método de codificación, porque como máximo sólo 162 símbolos del alfabeto de 8 bits , que tiene un tamaño de 256, estarán en el libro de códigos.
Pseudocódigo
Dada una lista de símbolos ordenados por longitud de bits, el siguiente pseudocódigo imprimirá un libro de códigos de Huffman canónico:
código : = 0 , mientras que más símbolos hacen símbolo de impresión, código de código : = ( código + 1) << ((longitud de bits de la siguiente símbolo) - (longitud de bits actual))
Algoritmo
El algoritmo descrito en: "Un método para la construcción de códigos de redundancia mínima" David A. Huffman, Proceedings of the IRE es:
algoritmo calcular código huffman es entrada: conjunto de mensajes (conjunto de (mensaje, probabilidad)). basado. salida: conjunto de código (conjunto de (mensaje, código)). 1- ordena el conjunto de mensajes por probabilidad decreciente. 2- N es el cardinal del conjunto de mensajes (número de diferentes mensajes). 3- calcula el número entero n_0 como 2≤n_0≤D y (N − n_0) / (D − 1) es un número entero. 4- seleccionar los n_0 mensajes menos probables y asignarles a cada uno un código de dígitos. 5- sustituye los mensajes seleccionados por un mensaje compuesto sumando su probabilidad y reordenarla. 6- mientras quede más de un mensaje, siga los pasos al 8. 7- seleccionar D mensajes menos probables y asignarles a cada uno un código de dígitos. 8- sustituye los mensajes seleccionados por un mensaje compuesto sumar su probabilidad y reordenarla. 9- el código de cada mensaje viene dado por la concatenación del dígitos de código del agregado en el que se han introducido.
Referencias: 1. Manejo de Gigabytes : libro con implementación de códigos canónicos huffman para diccionarios de palabras.