октября 2020; Группа 99; Информатика

5 октября 2020; Группа 99; Информатика

Практическое занятие №5

Сжатие информации. Алгоритм Хаффмана

ЗАДАНИЕ:

1. Изучить теоретический материал.
2. Выполнить задания 1 и 2 .

Фотографии отчета прислать в личном сообщении ВК: https://vk.com/id578016066.

На фотографиях вверху должна быть фамилия, дата выдачи задания, группа, дисциплина. Например: "Иванов, 5.10, группа 99, Информатика".

Для максимальной оценки задание прислать до 6.10 включительно

Практическая работа №5

Тема: «Сжатие информации.Алгоритм Хаффмана»

Цель: Познакомиться с одним из способов сжатия информации - алгоритмом Хаффмана. Практически закрепить представление в компьютере текстовых данных.

Ход работы:

1. Ознакомление с теоретическим материалом.

2. Выполнение практических заданий.

3 Ответы на контрольные вопросы.

3. Написание отчета.

Теоретический материал.

Алгоритм Хаффмана.Сжатием информации в памяти компьютера называют такое ее преобразование, которое ведет к сокращению объема занимаемой памяти при сохранении закодированного содержания.

Рассмотрим один из способов сжатия текстовой информации — алгоритм Хаффмана. С помощью этого алгоритма строится двоичное дерево, которое позволяет однозначно декодировать двоичный код, состоящий из символьных кодов различной длины. Двоичным называется дерево, из каждой вершины которого выходят две ветви.

На рисунке приведен пример такого дерева, построенного для алфавита английского языка с учетом частоты встречаемости его букв.

Закодируем с помощью данного дерева слово «hello»:

0101 100 0111101111 1110

При размещении этого кода в памяти побитово он примет вид: 01011000 11110111 11110

Таким образом, текст, занимающий в кодировке АSCII 5 байтов, в кодировке Хаффмана займет только 3 байта, т.е. сжатие происходит на 40% (100%− )

Задание.

№ 1

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

а) ADMINISTRATOR

б) REVOLUTION

в) ECONOMY
г) DEPATMENT

№2

Используя дерево Хаффмана, декодировать следующие слова:
а) 01110011 11001001 10010110 10010111 100000
6) 00010110 01010110 10011001 01101101 01000100 000

Контрольные вопросы

1. Что такое сжатие информации?

2. Можно ли применить метод Хаффмана для русского языка? (полный ответ)

3. Приводит ли сжатие информации методом Хаффмана к ее изменению, с точки зрения естественного языка? (полный ответ)

4. Посчитайте для 1а) и в) – процент сжатия информации.