Постройте дерево Хаффмана для фразы «МАМА МЫЛА ЛАМУ».

§ 3. Сжатие данных ГДЗ по Информатике 11 класс. Углубленный уровень. В 2 ч. Поляков К.Ю.

*6. Постройте дерево Хаффмана для фразы «МАМА МЫЛА ЛАМУ». Найдите коды всех входящих в нее символов и закодируйте сообщение. Чему равен коэффициент сжатия в сравнении с равномерным кодом минимальной длины? С однобайтной кодировкой?

Ответ

Для построения дерева Хаффмана и нахождения кодов всех символов во фразе «МАМА МЫЛА ЛАМУ», нужно выполнить следующие шаги:

Шаг 1: Подсчет частот символов

Во фразе «МАМА МЫЛА ЛАМУ» встречаются следующие символы и их частоты:

• М: 4
• А: 4
• П: 2
• Л: 2
• Ы: 1
• У: 1

Шаг 2: Построение дерева Хаффмана

Создаем узлы для каждого символа с их частотами и строим дерево:

1. Сначала берем узлы с наименьшими частотами и объединяем их:
   • «Ы» (1) и «У» (1) объединяются в узел с частотой 2.
   • «Л» (2) и объединенный узел («Ы», «У») с частотой 2 объединяются в узел с частотой 4.
   • «М» (4) и «А» (4) объединяются в узел с частотой 8.
   • «П» (2) и объединенный узел с частотой 4 объединяются в узел с частотой 6.
   • Наконец, объединенные узлы с частотами 6 и 8 объединяются в узел с частотой 14.

Дерево Хаффмана:

Шаг 3: Назначение кодов

Теперь назначим коды каждому символу:

• П: 00
• Л: 010
• Ы: 0110
• У: 0111
• М: 10
• А: 11

Шаг 4: Кодирование сообщения

Кодируем сообщение «МАМА МЫЛА ЛАМУ» с использованием найденных кодов:

• М: 10
• А: 11
• М: 10
• А: 11
• Пробел: 00
• М: 10
• Ы: 0110
• Л: 010
• А: 11
• Пробел: 00
• Л: 010
• А: 11
• М: 10
• У: 0111

Закодированное сообщение: 10111011001001100100101100111110

Шаг 5: Коэффициент сжатия

1. Равномерный код минимальной длины:

• Во фразе 8 различных символов. Минимальная длина равномерного кода: 3 бита (так как 2³=8).
• Длина сообщения в равномерном коде: 14 символов×3 бита=42 бита

Однобайтная кодировка:

• Каждый символ кодируется 8 битами.
• Длина сообщения в однобайтной кодировке: 14 символов×8 битов=112 битов

Длина закодированного сообщения Хаффмана:

• Длина закодированного сообщения: 36 битов.

Коэффициент сжатия:

В сравнении с равномерным кодом: 42 битов/36 битов = 1.167

Коэффициент сжатия в сравнении с равномерным кодом: 1.167

В сравнении с однобайтной кодировкой: 112 битов/36 битов = 3.111

Коэффициент сжатия в сравнении с однобайтной кодировкой: 3.111

Заключение

• Построенное дерево Хаффмана и назначенные коды для символов позволили закодировать сообщение «МАМА МЫЛА ЛАМУ» в 36 битов.
• Коэффициент сжатия в сравнении с равномерным кодом минимальной длины составляет 1.167.
• Коэффициент сжатия в сравнении с однобайтной кодировкой составляет 3.111.