Задание 3 Вариант 1 Самостоятельная работа 4 ГДЗ Рабочая тетрадь Босова 10 класс (Информатика)

1. Постройте дерево Хаффмана для фразы: «КОРОЛЕВА КАВАЛЕРУ ПОДАРИЛА КАРАВЕЛЛУ». Какие коды получат символы, образующие фразу? Сравните длину исходной фразы в кодировке КОИ-8 и представленную с помощью полученного вами кода. При исходной кодировке каждый символ в КОИ-8 кодируется 8 битами.

При кодировании по Хаффману длина кода каждого символа равна глубине его листа в дереве. Для данной фразы получаем такие длины кодов:

Тогда общая длина фразы после сжатия:

$$2\cdot 7+3\cdot 5+3\cdot 4+3\cdot 3+4\cdot 3+4\cdot 3+4\cdot 3+4\cdot 3+4\cdot 2+5\cdot 1+6\cdot 1+6\cdot 1$$

$$=14+15+12+9+12+12+12+12+8+5+6+6=123\ \text{бит}$$

В исходной кодировке КОИ-8 каждый символ занимает 8 бит, значит:

$$36\cdot 8=288\ \text{бит}$$

Разница составляет:

$$288-123=165\ \text{бит}$$

Ответ: после сжатия код фразы меньше на 165 бит.