Группа 11 Информатика 10.11.21 год
№23
Цель: Изучить методы сжатия информации (упаковки и Хаффмана)
Развить алгоритмическое мышление
Воспитание ответственного отношения к выполнению задания.
Учебник: Базовый уровень: учебник для 10 класса / И. Г. Семакин, Е. К. Хеннер, Т. Ю. Шеи- на. — 4-е изд. — М.: БИНОМ. Лаборатория знаний,. 2015. — 264 с.: ил.
265 страниц
https://informika-e.ru/S2/10_SEMAKIN.pdf
В жизни каждого пользователя ПК регулярно возникают ситуации, когда, например, нужно перенести один или несколько файлов на другой компьютер при помощи ограниченного по объему съемного носителя, переслать объемный файл по электронной почте и др. Как правило, возникает проблема разделения большого файла на несколько более мелких файлов с возможностью его дальнейшего воссоздания, групировки большого количества мелких файлов в более крупные, сжатия файлов для уменьшения их размера и т.д. Для решения подобных задач используют архиваторы.
Архиваторы - это программы, позволяющие создавать, за счет специальных методов сжатия, копии файлов меньшего размера и объединять копии нескольких файлов в один архивный файл, а также распаковывать архивы (извлекать файлы из архива).
Существуют различные алгоритмы архивации данных без потери информации, т.е. при разархивации данные будут восстановлены в исходном виде. Для ОС Windows наиболее популярными являются архиваторы WinRAR, WinZIP,WinACE.
Сжатие информации — это процесс преобразования информации, хранящейся в файле, в результате которого уменьшается ее избыточность, соответственно, требуется меньший объем Памяти для хранения.
Сжатие информации в файлах производится за счет устранения избыточности различными способами, например за счет упрощения кодов, исключения из них постоянных битов или представления повторяющихся символов или повторяющейся последовательности символов в виде коэффициента повторения и соответствующих символов. Применяются различные алгоритмы подобного сжатия информации.
|
|
Метод упаковки
Входной текс «КОЛ_ОКОЛО_КОЛОКОЛА» содержит всего 5 различных символов (К, О, Л, А, _). Следовательно каждый символ может быть закодирован трем битами. Всего в исходном тесте 18 символов, так что потребуется 18Х3=54бита. Коэффициент сжатия равен 144/54=2,7
Метод Хаффмана.
Слабое место метода упаковки заключается в том, что символы кодируются битовыми последовательностями одинаковой длины. Например, любой текст, состоящий только из букв «А» и «В», сжимается методом упаковки в восемь раз. Однако если к такому тексту добавить всего лишь одну букву, например «С», то степень сжатиясразу уменьшится вдвое, причем независимо от длины текста и количества добавленных символов «С»
Улучшения степени сжатия можно достичь, кодирую часто встречающиеся символы короткими кодами, а редко встречающиеся – более длинными. Именно такова идея метода, опубликованного Д.Хаффманом в 1952 г.
Алгоритм Хаффмана
1. Символы входного алфавита образуют список свободных узлов. Каждый узел имеет вес, равный количеству вхождений символа в исходное сообщение.
2. В списке выбираются два свободных узла с наименьшими весами.
3. Создается их узел- «родитель» с весом, равным сумме их весов, он соединяется с «детьми» дугами.
4. Одной дуге, выходящей из «родителя», ставится в соответствие бит 1, другой – бит 0.
|
|
5. «Родитель» добавляется в список свободных узлов, а двое его «детей» удаляются из этого списка.
6. Шаги, начиная со второго, повторяются до тех пор, пока в списке свободных узлов не останется только один свободный узел. Он и будет считаться корнем дерева.
Домашнее задание: проработать материал в домашних тетрадях, сфотографировать (скан.) отправить на электронную почту преподавателя m.kayuck@yandex.ua