Сжатие двоичного кода
методическая разработка по информатике и икт (10 класс) на тему
Презентация к уроку информатики по учебнику И.Г. Семакин, Т. Ю. Шеина, Л. В. Шестакова, Информатика и ИКТ(профильный уровень) 10 класс
Скачать:
| Вложение | Размер |
|---|---|
 szhatie_dvoichnogo_koda.pptx | 2.35 МБ |
Предварительный просмотр:
Подписи к слайдам:
Сжатие данных – это процесс, обеспечивающий уменьшение объёма данных за счёт изменения способа их организации
Возможны две ситуации при сжатии: Потеря информации в результате сжатия недопустима . Допустима частичная потеря информации в результате сжатия.
Сжатие с частичной потерей информации Графика, видео, звук
Связано с субъективными возможностями зрения человека. Яркость важнее цвета. Объём сокращается за счёт того, что коды цвета хранятся не для каждой точки( через 1, через 2, …). Чем б ольше сжатие, тем хуже качество При кодировании видеофильмов – свойство инерционности зрения (быстро меняющиеся фрагмента можно кодировать менее подробно, чем статические изображения)
Исходное 419 КБ Для WEB – страниц 23,7 КБ Для электронной почты 4,78 КБ
Связано с субъективными возможностями слуха человека. Учитывается восприимчивость слуха. Слабо воспринимаемые гармоники отфильтровываются путём математической обработки.
Сжатие без потери информации
Использование неравномерного кода для сжатия текста В компьютере 1 символ – 8 бит (1 байт) Частота встречаемости символов различна. Чем чаще встречается символ, тем меньше его информационный вес. Часто встречающиеся символы кодируют более коротким кодом.
Алгоритм Дэвида Хаффмана WENEEDMORESNOWFORBETTERSKIING Закодируем строку: 011101100110010010011011000111110101110001101100111001110101001111010110111001000010011001011011011010001110101010110000001
Переведём в шестнадцатеричный код, разместив побайтно (по 8) 84218421 84218421 84218421 01110110 01100100 10011011 00011111 01011100 01101100 76 6 4 9 B 1F 5C 6C 11100111 01010011 11010110 11100100 00100110 01011011 E7 53 D6 E4 26 5B 01101000 11101010 10110000 001 00000 68 EA B0 20 Текст, занимающий в кодировке ASCII 29 байтов , в кодировке Хаффмана займёт 16 байтов.
Коэффициент сжатия= Раскодирование происходит при помощи двоичного дерева Хаффмана
Дерево (граф) – графическое представление структуры связей между элементами некоторой системы. Состоит из вершин и линий связи. Если линии связи имеют направление, они называются дугой. Двоичное дерево – любая вершина имеет не более двух потомков. Корень дерева – единственная вершина, не имеющая родителей. Листья – вершины, не имеющие потомков.
Дерево Хаффмана Z Q К
Раскодировать двоичный код 01010001 00100101 00100011 11111100 . Рассчитать коэффициент сжатия Z Q К
Сжатие путём учёта числа повторений. Алгоритм RLF . Выявляются группы идущих подряд одинаковых однобайтовых кодов. Группа заменяется на два байта: число повторений( Эффективен для графики с большими областями равномерной закраски.
RLE – метод сжатия без потерь (Строка 23: 2 нуля, 5 единиц, 25 нулей, 43 единицы и т. д.)
Сжатие путём учёта числа повторений. Алгоритм Лемпеля – Зива ( LZ77,LZ78). При обнаружении слова, которое уже встречалось, на него формируется ссылка в виде смещения назад относительно текущей позиции и длины слова в байтах.
Дома: §1.4.5, стр. 75 №3,4 в тетради