Задание 3 Вариант 2 Самостоятельная работа 4 ГДЗ Рабочая тетрадь Босова 10 класс (Информатика)
Босова, Босова, Лобанов
10 класс
Класс
10
Предмет
Информатика
Автор
Босова, Босова, Лобанов
Задание 3 Вариант 2 Самостоятельная работа 4 ГДЗ Рабочая тетрадь Босова 10 класс (Информатика)
Задача
- Постройте дерево Хаффмана для фразы: «У_ПЕРЕПЕЛА_И_ПЕРЕПЕЛКИ_ПЯТЬ_ПЕРЕПЕЛЯТ». Какие коды получат символы, образующие фразу? Сравните длину исходной фразы в кодировке КОИ-8 и представленную с помощью полученного вами кода.
Подробный ответ
Для построения дерева Хаффмана подсчитаем частоты символов в фразе У_ПЕРЕПЕЛА_И_ПЕРЕПЕЛКИ_ПЯТЬ_ПЕРЕПЕЛЯТ:
| Символ | К-во |
|---|---|
| У | 1 |
| А | 1 |
| К | 1 |
| Ь | 1 |
| И | 2 |
| Я | 2 |
| Т | 2 |
| Р | 3 |
| Л | 3 |
| _ | 5 |
| П | 7 |
| Е | 9 |
При построении дерева Хаффмана объединяем символы с наименьшими частотами. В результате получаем один из возможных вариантов кодов:
| Символ | К-во | Код |
|---|---|---|
| У | 1 | 011110 |
| А | 1 | 011111 |
| К | 1 | 011100 |
| Ь | 1 | 011101 |
| И | 2 | 1110 |
| Я | 2 | 1111 |
| Т | 2 | 1100 |
| Р | 3 | 1101 |
| Л | 3 | 0110 |
| _ | 5 | 010 |
| П | 7 | 10 |
| Е | 9 | 00 |
Сравним длину исходной фразы и длину фразы после сжатия:
До сжатия:
$$37 \cdot 8 = 296$$
После сжатия:
$$2 \cdot 2 + 3 \cdot 1 + 4 \cdot 5 + 6 \cdot 4 = 4 + 3 + 20 + 24 = 51$$
Разница:
$$296 — 51 = 245$$
Ответ: после сжатия код фразы меньше на 245 бит.
Другие учебники
Другие предметы