Codificación Huffman

La teoría de la información nos otorga límites sobre la compresibilidad de mensajes mediante el Teorema de codificación de fuentes de Shannon, este dice que un mensaje \(X\) de largo \(n\) puede ser codificado en más de \(nH(X)\) bits con una pérdida despreciable de información, pero si se codifica en menos bits es prácticamente seguro que habrá pérdida de información.

Así que es importante encontrar un código que logre codificar mensajes con el límite teórico de compresibilidad que es \(\lceil nH(X) \rceil\). Esto lo logra el código de Huffman.

Fue introducido en 1952 por David Huffman cuando estaba estudiando su doctorado en el MIT como desafío de su profesor Robert Fano, el que habría trabajado con el mismo Shannon para intentar producir este tipo de códigos.

Descripción

La codificación Huffman genera un código libre de prefijos binario con longitud de palabra codificada mínima. Este código es de largo variable, es decir que los símbolos del mensaje a codificar pueden representarse con una longitud variable de ceros y unos. Para poder distinguir estas representaciones entre sí, es necesario saber cuándo empieza y termina una. Esto se logra haciendo que las codificaciones de cada símbolo sean libres de prefijo: ninguna representación es prefijo de otra, así que en una pasada se puede decodificar el mensaje simplemente teniendo una tabla con los códigos asociados a cada símbolo.

Esto se logra asociando a cada caracter del alfabeto de entrada un peso, que corresponde a un número entre cero y uno que representa la frecuencia de ocurrencia de cada caracter en un mensaje. Estos se pueden calcular en tiempo lineal sobre el largo del mensaje simplemente contando las ocurrencias de cada caracter. Lo que se generan son codificaciones de cada símbolo de tal manera que cualquier otra codificación genera códigos más largos.

Es decir, la entrada es un mensaje \(X = x_1 x_2 \dots x_n\) sobre un alfabeto \(\Sigma\) de tamaño \(\sigma\) y se buscan codificaciones binarias \(c_i\) de cada símbolo \(s_i \in \Sigma\) tales que si \(p_i\) es la frecuencia de ocurrencias de \(s_i\) en \(X\), luego la longitud del mensaje codificado es

\[\sum_{i = 1}^\sigma p_i |c_i|\]

y esta es menor o igual que cualquier otra codificación binaria sobre el alfabeto.

Funcionamiento

Antes de continuar, se asumirá que la entrada del algoritmo no es un mensaje, sino que la lista de símbolos del alfabeto, cada uno con su respectivo peso. Esto no genera mucho problema en la práctica porque si lo que se quiere es codificar un mensaje, simplemente se debe mantener una tabla hash y actualizar la frecuencia de cada símbolo en una pasada por \(X\) en tiempo promedio \(O(n)\).

Lo que se hace es construir un árbol binario en donde las hojas son los símbolos del alfabeto y un camino desde la raíz hasta una hoja describe la codificación del símbolo asociado a esta hoja con la convención de ir por el hijo izquierdo representa un 0 e ir por el hijo derecho un 1. La idea es que los símbolos con pesos mayores estén más cerca de la raíz para que sean codificados con menos bits, mientras que los que tienen pesos menores están más alejados de la raíz.

A continuación, presentamos un algoritmo que corre en tiempo \(O(\sigma \lg \sigma)\) que obtiene la codificación.

1. Crear una hoja para cada símbolo con peso no nulo, agregarlas a una cola de prioridad.
2. Mientras haya más de un nodo en la cola, tomar los dos nodos con los menores pesos y crear un nodo que tenga a estos dos de hijos y su peso sea la suma de los pesos de sus hijos; luego agregar este nodo a la cola de prioridad.
3. El nodo restante es la raíz del árbol y con esto terminamos el algoritmo.

En efecto la complejidad de este algoritmo es \(O(\sigma \lg \sigma)\) pues las colas de prioridad toman tiempo logarítmico en insertar o eliminar la raíz y en total habrán \(2\sigma - 1\) nodos en el árbol, pues es binario y tiene \(\sigma\) hojas.

Ahora, descomprimir un mensaje es simple pues como el código es libre de prefijos simplemente hay que ir recorriendo el árbol a medida que se va leyendo el mensaje codificado y anotar un símbolo una vez que se llegue a una hoja, esto es lineal en el largo del mensaje codificado. Así que es crucial mantener almacenado el árbol para poder descomprimir.

La manera de hacer esto, sin mucha sobrecarga es colocar el árbol como prefijo del mensaje que se quiere enviar para así tener acceso a él.

También existe la técnica de codificación canónica en donde la forma del árbol es siempre la misma, y por eso se almacena implícitamente, esto hace que la sobrecarga de espacio sea mínima manteniendo la misma complejidad en decodificar un mensaje.

Implementación

A continuación una implementación en Python3 del algoritmo descrito anteriormente, no está diseñada para eficiencia, sino para que sea lo más pedagógica posible.

from collections import Counter
import heapq

# Node that stores symbol-frequency pair
class Node:
    def __init__(self, s = None, f = None, l = None, r = None):
        self.symbol = s
        self.freq = f
        self.left = l
        self.right = r
        self.parent = None

    # Takes two nodes and creates their parent
    # with freq = sum of node freqs
    @staticmethod
    def combine(u, v):
        w = Node(f = u.freq + v.freq, l = u, r = v)
        u.parent = w
        v.parent = w
        return w

    # Checks if Node is a leaf
    def is_leaf(self):
        return self.left is None and self.right is None

    # Comparison function required for priority queue
    def __lt__(self, other):
        return self.freq < other.freq

# Huffman encodes message and returns coding tree
def huffman_encode(msg):
    # Priority queue with only leaves
    pq = [Node(s, f) for s, f in Counter(msg).items()]
    leaves = {leaf.symbol : leaf for leaf in pq}
    heapq.heapify(pq)

    # If msg has only one symbol code it as one zero bit
    if len(pq) == 1:
        return '0' * len(msg), pq[0]

    # Combine nodes until done
    while len(pq) > 1:
        u = heapq.heappop(pq)
        v = heapq.heappop(pq)
        heapq.heappush(pq, Node.combine(u, v))

    # Create dict of coded version of each symbol
    codewords = {}
    tree = pq[0]
    for s, leaf in leaves.items():
        c = ''
        u = leaf
        while u is not pq[0]:
            v = u.parent
            c += '0' if u is v.left else '1'
            u = v
        codewords[s] = c[::-1] # reverse so that path is root-leaf

    # Build coded msg
    coded_msg = ''
    for s in msg:
        coded_msg += codewords[s]

    return coded_msg, tree

# Decodes a Huffman decoded message, given Huffman coding tree
def huffman_decode(coded_msg, tree):
    # If tree only codes one symbol,
    # return decoded_msg right away
    if tree.is_leaf():
        return tree.symbol * len(coded_msg)

    decoded_msg = ''
    v = tree
    # Traverse tree to decode message
    for b in coded_msg:
        if b == '0': # valid since on first iteration tree is not leaf
            v = v.left
        else:
            v = v.right
        if v.is_leaf(): # means we've read a codeword
            decoded_msg += v.symbol
            v = tree # go back to root to read next codeword

    return decoded_msg

Algo interesante es notar que hay que tratar el caso en el que hay un solo símbolo en el mensaje o en la codificación de manera distinta, pues aquí ya está óptimamente representado y no se puede ejecutar el algoritmo directamente porque la única hoja que habrá en el árbol de Huffman, será precisamente la raíz.

La clase Node es un nodo en el árbol que tiene un símbolo, una frecuencia y punteros a hijos izquierdo y derecho y a su padre. Para simplificar, se usó collections.Counter de la biblioteca estándar para que automáticamente se obtenga el número de ocurrencias de cada símbolo en el mensaje. Esto es más eficiente y fácil de entender que colocar frecuencias relativas al largo del mensaje y funcionará de la misma manera el algoritmo sin complicaciones adicionales.

Ejemplo de ejecución

Ahora veremos cómo se realiza codificación Huffman sobre el mensaje alabar_a_la_alabarda.

Primero se debe calcular el número de ocurrencias de cada símbolo y crear un nodo para cada uno y se agregan a una cola de prioridad, así que el estado inicial es este:

Luego, se van tomando los dos que tengan menor frecuencia y se van combinando hasta haber procesado todos estos nodos y así obtener un árbol binario, el cual sería el siguiente:

Donde los nodos que no tienen símbolos son simplemente los nodos internos y el valor que almacenan es la suma de las frecuencias de sus hijos. Es evidente que el valor de la raíz siempre va a ser el largo del mensaje.

Luego, la codificación otorgada por el árbol es: si se baja por la izquierda, poner un 0, y si se baja por la derecha, un 1; así que el mensaje final resulta ser 010101111010011001101010110010101111010011100.

Y donde la codificación de cada caracter está dada en la siguiente tabla.

Símbolo	Codeword
a	0
r	100
l	101
_	110
d	1110
b	1111

Aplicaciones

Esta codificación es ubicua en algoritmos de compresión, como DEFLATE, gzip, bzip2 entre otros. De hecho, su optimalidad teórica los hace muy usados en la práctica cuando se quiere transmitir información y hay herramientas de archival, como tar que utilizan compresión basada en técnicas entrópicas para minimizar el largo de los mensajes transimitidos y lograr ahorrar espacio y tiempo de transimisión.

Algo interesante es que esta codificación tiene una limitación: las codificaciones de los símbolos es de largo entero y aunque logre representar mensajes de manera óptima, no siempre logra la razón de compresión más baja de todos los códigos que existen. Es por eso que se estudia la codificación aritmética que puede codificar símbolos con largos no enteros.

Referencias

• Feldspar, A. (1997). An Explanation of the Deflate Algorithm. Disponible en línea aquí.
• Huffman, D. (1952). A Method for the Construction of Minimum-Redundancy Codes. Procedings of the IRE. 40 (9): 1098-1101.
• Shannon, C. (1948). A Mathematical Theory of Communication. Bell System Technical Journal. 27: 379-423, 623-656.
• Van Leeuwen, J. (1976). On the construction of Huffman trees. ICALP: 382-410.