Лабораторная работа №3 Метод кодирования
Рахманова А.А.
МИНИСТЕРСТВО НАУКИ И ВЫСШЕГО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ
федеральное государственное автономное образовательное учреждение высшего образования
«САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ АЭРОКОСМИЧЕСКОГО ПРИБОРОСТРОЕНИЯ»
ИНСТИТУТ НЕПРЕРЫВНОГО И ДИСТАНЦИОННОГО ОБРАЗОВАНИЯ
КАФЕДРА ( ИФ ГУАП)
|
ОЦЕНКА
ПРЕПОДАВАТЕЛЬ
преподаватель |
|
|
|
Ярославцева Е.А. |
должность, уч. степень, звание |
|
подпись, дата |
|
инициалы, фамилия |
ОТЧЕТ О ЛАБОРАТОРНОЙ РАБОТЕ
|
(Метод кодирования)
|
по дисциплине: (Основы теории информации) |
РАБОТУ ВЫПОЛНИЛ
СТУДЕНТ ГР. № |
Z222K |
|
|
|
Рахманова А.А. |
|
номер группы |
|
подпись, дата |
|
инициалы, фамилия |
Студенческий билет № |
2022/4682 |
|
|
|
|
Ивангород 2022г.
Оглавление
Цель работы 3
Освоить метод эффективного кодирования информации, предложенный Д. А. Хаффманом. 3
Задание 3
– Подсчет частоты вхождения каждого символа. 4
– Построение дерева 4
Вывод 6
Цель работы
Освоить метод эффективного кодирования информации, предложенный Д. А. Хаффманом.
Задание
Дано текстовое сообщение:
ВООБРАЖЕНИЕ ВАЖНЕЕ, ЧЕМ ЗНАНИЕ
Построить эффективный код сообщения методом Хаффмана и
определить объем закодированного сообщения.
Название файла: Лабораторная работа №3 Метод кодирования
– Подсчет частоты вхождения каждого символа.
Подсчитаем частоту входа каждого символа для выражения Таблица 1:
ВООБРАЖЕНИЕ ВАЖНЕЕ, ЧЕМ ЗНАНИЕ
Таблица 1 – частота вхождения для каждого символа
Символ |
А |
Б |
В |
Е |
Ж |
З |
И |
М |
Н |
О |
Р |
Ч |
«,» |
« » |
Число вхождений |
3 |
1 |
2 |
6 |
2 |
1 |
2 |
1 |
4 |
2 |
1 |
1 |
1 |
3 |
После подсчета частоты, расставим по убыванию Таблица 2
Таблица 2 - компановка
Символ |
Е |
Н |
«_» |
А |
В |
Ж |
И |
О |
Б |
З |
М |
Р |
Ч |
«,» |
Число вхождений |
6 |
4 |
3 |
3 |
2 |
2 |
2 |
2 |
1 |
1 |
1 |
1 |
1 |
1 |
– Построение дерева
Сначала
соединяем наименьшую частоту для
получения новых узлов
Е |
Н |
«_» |
А |
В |
Ж |
И |
О |
Б |
|
М |
Р |
Ч |
«,» |
6 |
4 |
3 |
3 |
2 |
2 |
2 |
|
1 |
1 |
1 |
1 |
1 |
1 |
З
24 4 2 2 2
Далее
соединяем для получения ещё новых узлов
Е |
Н |
«_» |
А |
|
ИО |
|
МР |
Ч «,» |
6 |
4 |
3 |
3 |
4 |
4 |
2 |
2 |
2 |
ВЖ
ВЗ6 8 4
Е |
|
«_»А |
ВЖИО |
|
МР Ч «,» |
6 |
4 |
6 |
8 |
2 |
4 |
Н
ВЗ10 6
|
|
Е |
ВЗ МР Ч «,» |
10 |
8 |
6 |
6 |
Н«_»А
ВЖИО
18 12
30
Получив все необходимые узлы можем построить кодирование фразы, влево – 0, вправо – 1, из это следует Таблица 3:
Таблица 3 – кодированные символы
А |
Б |
В |
Е |
Ж |
З |
И |
М |
Н |
О |
Р |
Ч |
«,» |
« » |
1011
4 бита |
0100
4 бита |
1100
4 бита |
00
2 бита |
1101
4 бита |
0101
4 бита |
1110
4 бита |
01100
5 бит |
100
3 бита |
1111
4 бита |
01101
5 бит |
01110
5 бит |
01111
5 бит |
1010
4 бита |
Сжатие складывается следующим образом Таблица 4
Таблица 4 - вычисления
Символ |
Частота |
Первоначальный (бит) |
Уплотненные биты |
Уменьшено на |
А |
3 |
3*8=24 |
3*4=12 |
12 |
Б |
1 |
1*8=8 |
1*4=4 |
4 |
В |
2 |
2*8=16 |
2*4=8 |
8 |
Е |
6 |
6*8=48 |
6*2=12 |
12 |
Ж |
2 |
2*8=16 |
2*4=8 |
8 |
З |
1 |
1*8=8 |
1*4=4 |
4 |
И |
2 |
2*8=16 |
2*4=8 |
8 |
М |
1 |
1*8=8 |
1*5=5 |
3 |
Н |
4 |
4*8=32 |
4*3=12 |
20 |
О |
2 |
2*8=16 |
2*4=8 |
8 |
Р |
1 |
1*8=8 |
1*5=5 |
3 |
Ч |
1 |
1*8=8 |
1*5=5 |
3 |
«,» |
1 |
1*8=8 |
1*5=5 |
3 |
« » |
3 |
3*8=24 |
3*4=12 |
12 |
Всего: |
240 |
108 |
132 |
|
Следовательно, получаем полное не закодированное сообщение 30*8=240 бит, а закодированное 108 бит.
Сообщение сжато на 132 бита или на 45%.
Вывод
При использовании метода Хаффмана для сжатия данного в задаче сообщения, выяснили что за счёт кодирования символов и построения «дерева», удалось сжать почти половину веса сообщения, т.е. 45% от изначального, тем самым, доказывая, что метод Хаффмана замечательно подходит для сжатия информации.