PUERTA | PUERTA-CS-2007 | Pregunta 77

Supongamos que las letras a, b, c, d, e, f tienen probabilidades 1/2, 1/4, 1/8, 1/16, 1/32, 1/32 respectivamente. ¿Cuál es la longitud promedio de los códigos Huffman?
(A) 3
(B) 2,1875
(C) 2,25
(D) 1,9375

Respuesta: (D)
Explicación: Obtenemos el siguiente árbol de Huffman después de aplicar el algoritmo de codificación de Huffman . La idea es mantener los caracteres menos probables lo más bajo posible seleccionándolos primero.

The letters a, b, c, d, e, f have probabilities 
1/2, 1/4, 1/8, 1/16, 1/32, 1/32 respectively. 

                 1
               /   \
              /     \
             1/2    a(1/2)
            /  \
           /    \
          1/4  b(1/4) 
         /   \
        /     \
       1/8   c(1/8) 
      /  \
     /    \
   1/16  d(1/16)
  /  \
 e    f
The average length = (1*1/2 + 2*1/4 + 3*1/8 + 4*1/16 + 5*1/32 + 5*1/32)
                   = 1.9375 

Cuestionario de esta pregunta