Тест на жадные алгоритмы 3

Предположим, что буквы a, b, c, d, e, f имеют вероятности 1/2, 1/4, 1/8, 1/16, 1/32, 1/32 соответственно. Какова средняя длина кодов Хаффмана?

A. 3

B. 2.1875

C. 2.25

D. 1.9375

Решение :

Д) правильно.

Мы получаем следующее дерево Хаффмана после применения алгоритма кодирования Хаффмана. Идея состоит в том, чтобы как можно меньше использовать наименее вероятные символы, выбирая их первыми.

Буквы a, b, c, d, e, f имеют вероятности 1/2, 1/4, 1/8, 1/16, 1/32, 1/32 соответственно.

                 1
               /   \
              /     \
             1/2    a(1/2)
            /  \
           /    \
          1/4  b(1/4) 
         /   \
        /     \
       1/8   c(1/8) 
      /  \
     /    \
   1/16  d(1/16)
  /  \
 e    f

Средняя длина = (1*1/2 + 2*1/4 + 3*1/8 + 4*1/16 + 5*1/32 + 5*1/32) = 1,9375

Спасибо за чтение

Placewit воспитывает лучших инженеров, предоставляя интерактивные занятия в классе и помогая им развивать свои навыки и попадать в замечательные компании.

Узнайте больше на Placewit. Следите за нами в Instagram и Facebook для ежедневного обучения.