Министерство науки и высшего образования Российской Федерации Федеральное государственное бюджетное образовательное учреждение высшего образования «Иркутский Национальный Исследовательский Технический Университет» (ИрНИТУ) Институт информационных технологий и анализа данных Практическая работа №8 по дисциплине «Теория информации» Вариант №1 Тема: Методы эффективного кодирования Выполнил: Студент гр. ИБб-23-1 Н.А.Кудрявцев Принял: Преподаватель: Ю.И. Огородников Иркутск, 2025 Дано текстовое сообщение: ВООБРАЖЕНИЕ ВАЖНЕЕ, ЧЕМ ЗНАНИЕ 1) Определить, сколько бит занимает исходное текстовое сообщение; 2) Построить эффективный код сообщения методом Шеннона-Фано, определить объем закодированного сообщения и эффективность кода; 3) Построить эффективный код сообщения методом Хаффмана и определить объем закодированного сообщения. Задание 1. ВООБРАЖЕНИЕ ВАЖНЕЕ, ЧЕМ ЗНАНИЕ В — 2, О — 2, Б — 1, Р — 1, А — 3 ,Ж — 2, Е — 6, Н — 4, И — 2, «Пробел» — 3, З — 1, М — 1; , — 1, Ч — 1 Всего символов: 30 Всего различных символов – 14; для кодирования 14 символов, 4 бита будет достаточно. Тогда объем сообщения = 4*30 = 120 бит Ответ: объем сообщения = 120 бит Задание 2. ВООБРАЖЕНИЕ ВАЖНЕЕ, ЧЕМ ЗНАНИЕ Расположим символы в порядке убывания: Символы по убыванию частот: Е (6), Н (4), А (3), Пробел (3), В (2), О (2), Ж (2), И (2), Б (1), Р (1), З (1), М (1); , (1), Ч (1). Теперь нужно разделить символы на две группы, так, чтобы сумма «частот» была примерна одна и та же (разделяем «сверху вниз», т. е. в первую группу попадут символы с максимальной частотой появления. Символы первой группы получают первый бит равный 1, вторая группа бит равный 0): 1 группа: Е (6), Н (4), А (3), Пробел (3). Сумма = 16. 2 группа: В (2), О (2), Ж (2), И (2), Б (1), Р (1), З (1), М (1), , (1), Ч (1). Сумма = 1. Теперь работаем отдельно с 1-ой и 2-ой группой, разбивая каждую из них снова на две группы: Разобьем 1 группу на две группы: Подгруппа 1: Е (6), Н (4) → Код: 11 o Е: 111 o Н: 110 Подгруппа 2: А (3), Пробел (3) → Код: 10 o А: 101 o Пробел: 100 Код для символов из 1 группы сформирован. Тот же алгоритм для 2 группы: Подгруппа 1: В (2), О (2), Ж (2), И (2) → Код: 01 o В: 0111 o О: 0110 o Ж: 0101 o И: 0100 Подгруппа 2: Б (1), Р (1), З (1), М (1), , (1), Ч (1) → Код: 00 o Б: 00111 o Р: 00110 o З: 00101 o М: 00100 o , : 00011 o Ч: 00010 Итак, мы закодировали все символы, выпишем символы и их код в таблицу: Символ Е Н А Пробел В О Ж И Б Р Код 111 110 101 100 0111 0110 0101 0100 00111 00110 З М , Ч 00101 00100 00011 00010 Для расчета этого значения построил таблицу в Excel, затем с помощью формулы «=СУММПРОИЗВ()» рассчитал требуемое значение: Исходные символы Количество символов Частоты символов Кол-во двоичных разрядов Е Н 6 4 0,2 0,1333 3 3 А 3 0,1 3 Пробел 3 0,1 3 В 2 0,0667 4 О 2 0,0667 4 Ж 2 0,0667 4 И 2 0,0667 4 Б 1 0,0333 5 Р 1 0,0333 5 З 1 0,0333 5 М 1 0,0333 5 , Ч 1 1 0,0333 0,0333 5 5 Сумма символов 30 Эффективность кода 3,67 Объем закодированного сообщения 110 Эффективность кода = 3,67 бит/символ Теперь рассчитаем объем закодированного сообщения, с помощью того же СУММПРОИЗВ(): 110 (поэлементно умножали столбец «количество символов» и столбец «кол-во двоичных разрядов», а затем все сложили) Объем закодированного сообщения = 110 бит Ответ: 1) Коды символов: Символ Код Е 111 Н 110 А 101 Пробел 100 В 0111 О 0110 Ж 0101 И 0100 Б 00111 Р 00110 З 00101 М 00100 , 00011 Ч 00010 2) Объем закодированного сообщения = 110 бит 3) Эффективность кода = 4 бит/символ Задание 3. ВООБРАЖЕНИЕ ВАЖНЕЕ, ЧЕМ ЗНАНИЕ Подсчитаем вхождение каждого из символов в сообщении и сразу отсортируем по убыванию: Е (6), Н (4), А (3), Пробел (3), В (2), О (2), Ж (2), И (2), Б (1), Р (1), З (1), М (1); , (1), Ч (1). Затем строим дерево, следующим образом: Берем два узла, сумма которых минимальна, объединяем их в один узел. Продолжаем до тех пор, пока не останется один «главный» узел. Теперь, когда наше дерево создано можно кодировать сообщение. Мы должны всегда начинать из корня. Кодируя первый символ (лист дерева «Пробел») мы прослеживаем вверх по дереву все повороты ветвей и если делаем левый поворот, то запоминаем 0, а если правый поворот, то запоминаем 1. Выполняем для всех символов: Символ Код Е 00 Н 01 А 100 Пробел 101 В 1100 О 1101 Ж 1110 И 1111 Б 10000 Р 10001 З 10010 М 10011 , 10100 Ч 10101 Для вычисления объема текстового сообщения необходимы два столбца из таблицы: Исходные символы Количество символов Е Н А Пробел В О Ж И Б Р З М , Кол-во двоичных разрядов 6 4 3 3 2 2 2 2 1 1 1 1 1 3 3 3 3 4 4 4 4 5 5 5 5 5 Таблица полностью совпала с предыдущей для метода Шеннона-Фано, следовательно, объем закодированного сообщения = 100 бит. Ответ: 1) Символ Код Е 00 Н 01 А 100 Пробел 101 В 1100 О 1101 Ж 1110 И 1111 Б 10000 Р 10001 З 10010 М 10011 , 10100 Ч 10101 2) Объем закодированного сообщения = 100 бит