Конспект урока по теме "Сжатие информации"

Конспект урока по информатике и ИКТ

Тип: Урок изучения нового материала

Тема: Архиваторы. Методы сжатия информации.

Цели:

1. Изучить методы сжатия информации (упаковки и Хаффмана)

2. Развить алгоритмическое мышление

3. Воспитание ответственного отношения к выполнению задания.

Метод: Объяснительно-иллюстративный

Ход урока:

1. Организационный момент (2 мин)

2. Актуализация знаний. (5 мин)

3. Объяснение материала и запись в тетрадь. (25 мин)

4. Первоначальное закрепление материала (10 мин)

5. Подведение итогов. (3 мин)

Вопросы по актуализации знаний:

1. Как вы понимаете понятие «сжатие информации»?

2. Каким образом сжимается цифровая информация?

3. Какие программы архиваторы вы знаете?

4. Информация в какой форм требует обязательного сжатия?

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

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

Архиваторы - это программы, позволяющие создавать, за счет специальных методов сжатия, копии файлов меньшего размера и объединять копии нескольких файлов в один архивный файл, а также распаковывать архивы (извлекать файлы из архива).

Существуют различные алгоритмы архивации данных без потери информации, т.е. при разархивации данные будут восстановлены в исходном виде. Для ОС Windows наиболее популярными являются архиваторы WinRAR, WinZIP,WinACE.

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

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

Метод упаковки

Входной текс «КОЛ_ОКОЛО_КОЛОКОЛА» содержит всего 5 различных символов (К, О, Л, А, _). Следовательно каждый символ может быть закодирован трем битами. Всего в исходном тесте 18 символов, так что потребуется 18Х3=54бита. Коэффициент сжатия равен 144/54=2,7

Метод Хаффмана.

Слабое место метода упаковки заключается в том, что символы кодируются битовыми последовательностями одинаковой длины. Например, любой текст, состоящий только из букв «А» и «В» , сжимается методом упаковки в восемь раз. Однако если к такому тексту добавить всего лишь одну букву, например «С», то степень сжатиясразу уменьшится вдвое, причем независимо от длины текста и количества добавленных символов «С»

Улучшения степени сжатия можно достичь, кодирую часто встречающиеся символы короткими кодами, а редко встречающиеся – более длинными. Именно такова идея метода, опубликованного Д.Хаффманом в 1952 г.

Алгоритм Хаффмана

1. Символы входного алфавита образуют список свободных узлов. Каждый узел имеет вес, равный количеству вхождений символа в исходное сообщение.

2. В списке выбираются два свободных узла с наименьшими весами.

3. Создается их узел- «родитель» с весом, равным сумме их весов, он соединяется с «детьми» дугами.

4. Одной дуге, выходящей из «родителя», ставится в соответствие бит 1, другой – бит 0.

5. «Родитель» добавляется в список свободных узлов, а двое его «детей» удаляются из этого списка.

6. Шаги, начиная со второго, повторяются до тех пор, пока в списке свободных узлов не останется только один свободный узел. Он и будет считаться корнем дерева.

Задания на закрепления

Упаковать сообщение 2 методами: Архип_осип._Осип_охрип.

Вопросы для подведения итога урока:

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

2. Основное назначение программ архиваторов.

3. Какие методы сжатия сегодня изучили.

4. Какой метод сжатия наиболее эффективный и почему?