Планирование уроков на учебный год (по учебнику К.Ю. Полякова, Е.А. Еремина, сокращённый курс, по 2 часа в неделю)



Уроки 6 - 7
Сжатие данных без потерь
(§3. Сжатие данных)






Содержание урока

Основные понятия

Алгоритм RLE

Префиксные коды

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

Сжатие с потерями

Выводы

Вопросы и задания

Задачи


Выводы


Мы рассмотрели различные алгоритмы сжатия информации. Все они основаны на том, что в информации есть некоторая избыточность, закономерность, которую можно использовать для уменьшения объёма данных. Хорошо сжимается информация, в которой большая избыточность:

• тексты, в которых повторяются одинаковые слова и символы имеют разные частоты встречаемости (файлы с расширениями txt, doc, docx);
• документы — тексты с оформлением и, возможно, вставленными рисунками, таблицами и т. п.; электронные таблицы (файлы с расширениями doc, docx, xls);
• рисунки, имеющие большие области одного цвета и записанные без сжатия (файлы bmp);
• несжатый звук (файлы wav);
• несжатое видео (файлы avi) 1.

Плохо сжимаются данные, где избыточность маленькая или ее совсем нет:

• архивы, упакованные со сжатием (zip, гаг, 7z и др.);
• сжатые рисунки (файлы gif, jpg, png, tif и др.);
• сжатый звук (файлы mp3, wma);
• сжатое видео (файлы mpg, wmv, mp4);
• программы (файлы ехе).

Данные невозможно сжать, если в них нет никаких закономерностей. Поэтому хуже всего сжимаются случайные числа, например полученные на компьютере. Современным программам- упаковщикам иногда удаётся их немного сжать, но не более, чем на 1-2%. Это происходит потому, что в последовательности псевдослучайных чисел, которые выдает компьютерная программа- генератор, всё же можно выявить какие-то закономерности.

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


1 Файлы с расширением avi могут хранить как сжатое, так и несжатое видео.




Следующая страница Вопросы и задания



Cкачать материалы урока






Наверх