Greedy: Códigos de Huffman

Question 1

Explique la idea detrás de los Códigos de Huffman

Answer 1

La idea de los Códigos de Huffman es asignar códigos de bits más cortos a símbolos que ocurren con mayor frecuencia, y códigos de bits más largos a símbolos que ocurren con menor frecuencia.

Esto aprovecha el hecho de que, en muchos conjuntos de datos, algunos símbolos son más probables que otros, lo que permite comprimir los datos reduciendo la cantidad total de bits necesarios para representar la información.

Question 2

¿Qué es la comprensión de datos?

Answer 2

La comprensión de datos es la reducción del volumen de datos que se usan para representar una determinada información, empleando una menor cantidad de espacio.

Question 3

¿Qué es una fuente?

Answer 3

Se llama ‘fuente’ a todo aquello que emita ‘mensajes’. Existe un conjunto finito de posibles mensajes.

Question 4

¿Cómo se representan los emnsajes?

Answer 4

Los mensajes se representan mediante códigos (el objetivo es elegir códigos de tal forma de reducir al mínimo el tamaño de lo emitido por la fuente).

Question 5

¿Qué son los códigos?

Answer 5

• Son una convención que establece cómo representar cada mensaje utilizando una combinación de símbolos: ASCII, Morse, etc.
• Puede tener longitud fija o variable
• No deben ser ambiguos

Question 6

Explique qué son los códigos decodificables.

Answer 6

Los códigos decodificables son aquellos que para cualquier sucesión de códigos, sólo existe un único conjunto de mensajes válidos.

Los códigos de longitud fija son siempre decodificables.

Ejemplo:

10
00
11

Question 7

Explique cuándo un código es prefijo

Answer 7

Un código es prefijo si no existe ningún código que tenga un prefijo igual a otro código completo.

Los códigos prefijos son siempre decodificables.

Ejemplo:

0
10
110
111

Question 8

¿Qué son los Códigos de Huffman? ¿Es óptimo?

Answer 8

Son códigos de longitud variable y prefijos.
La longitud de cada código está basada en la frecuencia de cada mensaje en el emisor (fuente).

Es óptimo: no existen otros códigos prefijos para la misma fuente que la codifique en menor longitud.

Question 9

Explique el problema de los Códigos de Huffman. ¿A qué se le llama Longitud de C(W)? ¿Qué cumple la longitud de los códigos de Hoffman?

Answer 9

Sea el alfabeto A = (a1, a2, ..., an), llamaremos W=(w1, w2, ..., wn) al peso (o frecuencia) de cada ai.

Construiremos un C(W) = (c1, c2, ..., cn) con códigos prefijos y binarios.

Llamamos Longitud(C(W)) a la suma de todos los pesos multiplicados por el tamaño de su código asociado.

De esta forma, se cumple que la longitud de C(W) es menor o igual a la longitud de cualquier otro código prefijo T(W).

Question 10

Código prefijo: Árbol Binario
¿Cómo puede representarse un código prefijo mediante un árbol binario?

Answer 10

Podemos representar un código prefijo mediante un árbol binario: las hojas serán loscódigos y cada nodo tendrá 2 o ningún descendiente.

Question 11

Explique el Algoritmo Greedy para Códigos de Hoffman con Árboles Binarios.

Answer 11

Se genera un árbol de Huffman para armal el optimal prefix code.

1. Inicialmente, cada código ci es un nodo hoja con
   peso wi.
2. Mientras quede más de un nodo sin padre:
   2.a. Toma los dos nodos x,y de menor peso que no tengan padre.
   2.b. Crea un nuevo nodo z con wz= wx+ wy.
   2.c. Define a z como padre de x e y
3. El último nodo sin padre será la raíz del árbolI

Question 12

Indique una posible implementación de Códigos de Huffman. ¿Qué complejidad tiene?

Answer 12

• Se puede usar un heap de mínimos, donde el nodo del árbol será el elemento y la frecuencia será la clave.
• En cada iteración, se obtienen los 2 nodos de menor peso, y se ingresa uno nuevo creado.
• El último elemento en el heap es la raíz.

La complejidad algorítmica es O(n logn), por tener n inserciones en el heap.

Question 13

Explique el pseudocógio para la implementación de Códigos de Huffman con árboles binarios.

Answer 13

1. Para todos los nodos, crear una tupla con (clave, peso) e insertarlos al Heap.
2. Ir obteniendo los dos mínimos, y unirlos para crear un nuevo nodo. Se guarda cuál es el izquierdo, cuál el derecho, y el peso total es la suma de ambos. Se agrega luego este nuevo nodo al heap.
3. Se repite el paso 2 por todos los nodos menos el úlimo.
4. Se devuelve el heap (el árbol).

Question 14

Códigos de Huffman con árboles binarios: ¿Es óptimo? ¿Se puede probar?

Answer 14

Es óptimo, y se puede probar por dos caminos:

1. Prueba de selección greedy: mostrar que la heurística de elegir dos mensajes de menor peso nos acerca a la solución óptima global.
2. Prueba de los subproblemas: mostrar que el subproblema derivado de nuestra elección se puede solucionar mediante la misma selección greedy.

Question 15

Explique la prueba de Selección Greedy

Answer 15

• Sea A = (a1, ..., an) el alfabeto con peso W=(w1,...,wn)
• Sean a y b los dos mensajes de A con menor frecuencia

=> Existe un código prefijo óptimo tal que
1. El tamaño de (Ca) es igual al tamaño de C(b), y difieren en el último bit.
2. Además, el tamaño de ambos C es mayor o igual al tamaño de cualquier otro elemento de A.

Question 16

Explique la prueba de los subproblemas

Answer 16

• Sea A = (a1, ..., an) el alfabeto con peso W=(w1,...,wn)
• Sean a y b los dos mensajes de A con menor frecuencia

=> A' = A - {a,b} + {z}, tal que wz = wa + wb y el resto de los pesos iguales. Tengo entonces C y C'.

• Sea T' árbol que representa un código prefijo óptimo para C'.
• Sea T árbol que representa un código prefijo óptimo para C.

Entonces se puede ver que:
T se puede obtener de T', reemplazando el nodo hoja z' por un nodo con hijos a y b.

Question 17

Resuelva:

Arme el árbol binario para el siguiente código de Huffman:

A = 0000
B = 0001
C = 010
D = 011
E = 1

Fuente: ABEEE CCEEE DDEEEE

Answer 17

Sea la notación (x,y, v) -> z, tal que x, y son los nodos hijos de la raíz z, y v es el código asociado a la raiz.

El árbol resultante es:

└── 16
              ├── (0) - 6
              │               ├── (0) - 2
              │               │                ├── (0) - A
              │               │                └── (1) - B
              │               │
              │               └── (1) - 4
              │                                   ├── (0) - C
              │                                   └── (1) - D
              └── (1) - E