PUERTA | GATE-CS-2017 (Conjunto 2) | Pregunta 58

Un mensaje se compone enteramente de caracteres del conjunto X = {P,Q,R,S,T} . La tabla de probabilidades de cada carácter se muestra a continuación:

Un mensaje de 100 caracteres sobre X se codifica utilizando la codificación Huffman. Entonces la longitud exceptuada del mensaje codificado en bits es _____
(A) 225
(B) 226
(C) 227
(D) 228

Respuesta: (A)
Explicación:

In Huffman coding, we pick the least
two frequent (or probable) character, combine them and create
a new node.

    .08 (T)      0.17(R)    0.19(S)     0.22(P)
      \        /                 \       /
         0.25    0.34(Q)         0.47
           \      /               /
             0.59                /
               \                /
                         1

Mirando la estructura de árbol anterior, número de bits requeridos por cada uno:
P – 2
Q – 2
R – 3
S – 2
T – 3

Por lo tanto,  la longitud exceptuada del mensaje codificado

= 3*0,8 + 3*0,17 + 2*0,19 + 2*0,22 + 2*0,34

= 2,25

Para 100 caracteres, 2,25*100 = 225

Por lo tanto, la opción A es correcta.

 
Cuestionario de esta pregunta