Huffman Encoding

Es un método general de codificación y compresión diseñado para minimizar el número medio de bits necesarios para transmitir un símbolo cuando se debe transmitir varias copias independientes y estadísticamente equivalentes de dicho símbolo. Este método determina cómo los distintos valores del símbolo deben representarse como cadenas binarias.

Supongamos que tenemos que enviar el símbolo X que puede tomar valores {x1,...xn} con probabilidad {p1,...,pn}. La idea es reservar palabras cortas para los valores más frecuentes de X. Este método no requiere usar ningún tipo de separador entre los valores.

Ejemplo: x1 (0.5) x2 (0.3) x3 (0.15) x4 (0.05)      
  • Si se usan 00, 01, 10 y 11 necesitaremos siempre 2 bits para el valor de X.
  • Si se usan las palabras 0,10,110,111 necesitaremos como término medio 1.7 bits (menos de 2).

El código del ejemplo es de longitud variable, pero no se requiere usar ningún tipo de separador entre los valores.

  • x3 x1 x4 x3 x3 x2 = 110011111011010 Sólo puede decodificarse correctamente.

La razón es que siempre puede reconocer el final de una palabra porque ninguna otra palabra es el principio de otra dada. Un código con esta propiedad se denomina código prefijo. El código Huffman es el código prefijo que requiere el mínimo número medio de bits por símbolo.

Para derivar el código Huffman se hacen las siguientes operaciones:

  1. Escoger los dos símbolos xi, xj con probabilidad más pequeña.
  2. Se las reemplaza por yi0 e yi1.
  3. Se borra xi y xj de la lista y se añade yi con probabilidad pi+pj.
  4. Volver al paso 1 hasta terminar con todos los símbolos.

 

El código queda definido por el camino desde C a cada nodo. La convención para escribir el código de Huffman final es:
../compresión de datos/Huffman Encoding