Задание 1 (20 баллов).

Дан фрагмент текста: «Гораздо легче простить людей за то, что они не правы, чем за правоту». Известно, что данный текст представлен с использованием кодировки, где для хранения каждого символа используется 8 бит. Сколько байт необходимо для хранения этого текста?

Выполнение Задания 1.

Для решения данной задачи необходимо посчитать общее количество символов во фрагменте текста, учитывая пробелы и знаки препинания. Всего таких символов во фрагменте 69. Так как для хранения каждого символа требуется 8 бит (1 байт), чтобы найти информационный объём текста, необходимо умножить количество символов на информационный объём одного символа.

69 символов * 1 байт = 69 байт.

 

Задание 2 (20 баллов).

Составьте таблицу двоичного кода для символов алфавита, который имеет мощность 10. Код должен быть равномерным. Сколько бит требуется для хранения каждого символа? Можно ли использовать такое же количество бит на символ, если мощность увеличится до 17 символов?

Выполнение Задания 2.

Для равномерного кодирования десяти символов потребуется 4 бита, так как =8, что означает, что 3 бита будет недостаточно, а  = 16, что хватает для кодирования десяти символов с запасом.

Если мы используем 4 бита для кодирования символов алфавита с мощностью 10, то каждому из этих символов будет соответствовать четырёхсимвольная двоичная последовательность.

1 символ	0000
2 символ	0001
3 символ	0010
4 символ	0011
5 символ	0100
6 символ	0101
7 символ	0110
8 символ	0111
9 символ	1000
10 символ	1001

Если мощность алфавита увеличится до 17 символов, то его нельзя будет закодировать, используя 4 бита, так как  = 16.

 

Задание 3 (20 баллов).

Перед вами алфавит: А, Б, В, Г, Д. Для него необходимо составить неравномерный двоичный код. Известно, что чаще всего используются буквы А и В, реже всего — Б и Д. Представьте этот код в виде таблицы с двумя столбцами: символ, двоичный код. Получившийся код должен соответствовать условию Фано.

Выполнение Задания 3.

Условие Фано гласит, что никакое кодовое слово не может быть началом другого кодового слова. Так как буквы А и В встречаются чаще всего, их код стоит сделать как можно короче. Б и Д используются реже остальных букв алфавита, значит, их код должен быть длиннее остальных.

Исходя из вышесказанного, можем построить следующее дерево:

Рис. 1

Представим коды букв алфавита в виде таблицы, как требуется по заданию.

Символ	Двоичный код
А	11
Б	010
В	10
Г	00
Д	011

Некоторые буквы можно поменять местами и получить другую таблицу кодов, которая также будет верной. Например, если поменять буквы А и В местами, то код уже будет другим, но всё ещё соответствующим условию задания.

 

Задание 4 (40 баллов).

Дана фраза: «У осы не усы». Необходимо сжать эту фразу с помощью кода Хаффмана. Таблица частот уже построена:

_	у	с	ы	о	н	е
3	2	2	2	1	1	1

Определите кодовые последовательности для каждого символа соответственно коду Хаффмана. Приведите полное решение.

Выполнение Задания 4.

Расположим веса, исходя из таблицы частот использования символов.

Рис. 2

Возьмём два первых символа с наименьшим весом — е и н. Сложим их веса в новой вершине.

Рис. 3

Найдём следующие вершины, которые позволят получить новую вершину с наименьшим весом.

Рис. 4

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

Рис. 5

В следующем шаге вершина с весом 2 перенесена для удобства вправо.

Рис. 6

Следующий шаг:

Рис. 7

Следующий шаг:

Рис. 8

Запишем полученные коды символов в таблицу. Записываем их сверху вниз.

_	у	с	ы	о	н	е
00	11	010	011	100	1010	1011

 

---

Список использованных источников:

Рис. 1–8. Иллюстратор Андреева А. С.