2019-gate-computer-science-and-it-practice.pdf/Q17-alg4 — различия между версиями

Текущая версия на 14:28, 25 декабря 2024

Вопрос: Q17-alg4-31d68c

Предположим, что символы a,b,c,d,e встречаются с частотами .

Какие получатся коды Хаффмана для букв a,b,c соответственно?

Ответы

• 1101, 111, 1101
• Правильный ответ: 1100, 1101, 111
• 1100, 10, 0
• 1101, 1100, 111

Объяснение

Необходимо построить дерево Хаффмана и получить коды Хаффмана.

• Отсортируем по частотам:
• Собираем символы с меньшими частотами, узел с частотой
  • Список:
• Собираем символы с меньшими частотами, узел с частотой
  • Список:
• Собираем символы с меньшими частотами, узел с частотой
  • Список:
• Собираем остатки, меньшие частоты налево, узел с частотой

       Root
      /    \
     e      {d, {{a, b}, c}}
            /    \
           d      {{a, b}, c}
                 /    \
               {a, b}  c
              /    \
             a      b

Осталось назначить коды.

a

• Right → Right → Left → Left
• 1100

b

• Right → Right → Left → Right
• 1101

c

• Right → Right → Right
• 111

Исходники — вопрос 17 на 238 странице книги «2019-gate-computer-science-and-it-practice.pdf»