Algoritmos | Algoritmos codiciosos | Pregunta 3 – Part 1

Una empresa de redes utiliza una técnica de compresión para codificar el mensaje antes de transmitirlo por la red. Supongamos que el mensaje contiene los siguientes caracteres con su frecuencia:

character   Frequency
    a            5
    b           9
    c           12
    d           13
    e           16
    f           45

Nota: Cada carácter en el mensaje de entrada ocupa 1 byte.

Si la técnica de compresión utilizada es Huffman Coding, ¿cuántos bits se guardarán en el mensaje?
(A) 224
(B) 800
(C) 576
(D) 324

Respuesta: (C)
Explicación:

Total number of characters in the message = 100. 
Each character takes 1 byte. So total number of bits needed = 800.

After Huffman Coding, the characters can be represented with:
f: 0
c: 100
d: 101
a: 1100
b: 1101
e: 111
Total number of bits needed = 224
Hence, number of bits saved = 800 - 224 = 576
See here for complete explanation and algorithm.

Cuestionario de esta pregunta