Últimos Cambios
Blog personal: El hilo del laberinto
|
|
|
Últimos Cambios |
|
Blog personal: El hilo del laberinto
|
|
|
Ú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].
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].
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.
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.
Más información sobre los OpenBadges
Donación BitCoin: 19niBN42ac2pqDQFx6GJZxry2JQSFvwAfS
