Get Firefox

Member of The Internet Defense League

stopsoftwarepatents.eu petition banner Últimos cambios
Últimos Cambios
Blog personal: El hilo del laberinto Geocaching

Códigos Huffman y Shannon-Fano

Última Actualización: 13 de Mayo de 2004 - Jueves

El objetivo de estos códigos es generar una representación de la información de la fuente de forma tal que su tamaño se aproxime a la entropía teórica de esa fuente, produciendo una "compresión" de los datos. Son códigos prefijo.

Supongamos que tenemos una fuente produciendo datos X[i], cada uno con una probabilidad (independiente y sin memoria) P[i].

Códigos Shannon-Fano

Se ordenan los X[i] de mayor a menor probabilidad. Se divide el resultado en dos grupos, procurando que la probabilidad de cada grupo esté lo más próxima posible. Un grupo se codificará como cero ("0") y el otro como uno ("1"). Seguidamente se repite el proceso en cada grupo, de forma recursiva, mientras cada grupo tenga más de un dato X[i].

Códigos Huffman

Se toman los dos datos menos probables y se les asigna "0". Al resto de códigos se les asigna "1". Esos dos datos se "colapsan" en un nuevo dato, cuya probabilidad es la suma de las dos probabilidades anteriores, y se repite el proceso.

En el caso general, los códigos Huffman SIEMPRE generan códigos, al menos, igual de eficientes que los Shannon-Fano. Es decir, siempre es preferible optar por Huffman. De hecho se puede probar que si cada X[i] se codifica de forma separada, Huffman genera códigos óptimos.

Ejemplos

Supongamos una fuente que produce seis datos distintos, X[1..6], con probabilidades P[1..6]= (0'4, 0'2, 0'2, 0'1, 0'07, 0'03)

La entropía de la fuente es de 2'21 bits.

El código Huffman para esa fuente sería: (1, 00, 010, 0111, 01100, 01101). La longitud media de dicho código es de 2'3 bits.

Se calcula de la siguiente manera: Tomamos los dos casos más improbables (P5 y P6) y les damos el 0 y 1. Ahora tomamos esos dos valores y los sustituimos por uno nuevo, que llamamos P7. Las probabilidades quedan entonces como (0'4, 0'2, 0'2, 0'1, 0'1). Ahora es cuestion simplemente de repetir el proceso de forma iterativa hasta que no nos queden más valores que codificar. El árbol que se obtendría tendría la forma:

                  |
      +-----------+-------+
      |                   |
      | 0'6               | 0.4
+-----+------+            P1
|            |
|0'2         | 0'4
P2   +-------+-------+
     |               |
     |0'2            | 0'2
     P3       +------+-----+
              |            |
              | 0'1        | 0'1
          +---+---+        P4
          |       |
          | 0'07  | 0'03
          P5      P6

Para determinar la codificación de un dato basta con seguir su camino en el árbol e ir dando bits 0 o 1 según, por ejemplo, tomemos la rama de la izquierda o la de la derecha.

El código Shannon-Fano para esta fuente sería: (00, 01, 10, 110, 1110, 1111). La longitud media de dicho código es de 2'3 bits.

En este caso ambas codificaciones generan códigos de la misma longitud media, aunque sean distinto.


Historia

  • 13/May/04: Mejoro el ejemplo para que sea más claro y didáctico.

  • 30/Ago/03: Primera versión de este documento.



Donación BitCoin: 19niBN42ac2pqDQFx6GJZxry2JQSFvwAfS

Actualizar Python Zope ©2003-2004 jcea@jcea.es