Материалы к уроку по теме Сжатие данных
методическая разработка по информатике и икт (11 класс) по теме
Предлагаемые материалы легли в основу зачетной работы по курсу "Математические основа информатики"(автор А. Гейн), который я успешно прошла в 2011 году в дистанционном университете "1Сентября". Материалы адаптированы для расширенного курса информатики в 11 классе.
Скачать:
| Вложение | Размер |
|---|---|
 Plan_i_konspekt_uroka.doc | 51 КБ |
 Algoritmy_szhatiya_simvolnoy_informacii.ppsx | 126.54 КБ |
Предварительный просмотр:
Cжатие данных лицей № 329
Андреева О.А.
План урока
11 класс
Тема урока: Cжатие данных.
Тип урока: изучение нового учебного материала с элементами фронтальной беседы.
Цели урока: расширение компетенций в создании собственного информационного пространства.
Задачи урока:
учебная — рассмотреть понятие сжатие данных и ознакомиться с алгоритмами сжатия символьных данных;
познавательная — ввести понятие избыточность данных;
воспитательная — создать условия для активной деятельности каждого ученика.
Программное
обеспечение урока: - презентация по теме “Сжатие данных”;
Техническое
обеспечение урока: - рабочее место ученика с ПК PentiumIII;
- фломастерная доска;
- проектор для демонстрации презентации.
ХОД УРОКА
I этап: выход на тему урока и мотивация изучения материала;
II этап : сообщение учебного материала;
III этап: актуализация полученных знаний — ответы на вопросы для закрепления;
IV этап: сообщение домашнего задания; подведение итогов урока.
Конспект урока
I этап:
Количество нужной человеку информации неуклонно растет. Возможности устройств для хранения данных и пропускная способность линий связи также растут. Однако количество информации растет быстрее.
У этой проблемы есть три пути решения:
первое - ограничение количества информации. К сожалению, оно не всегда приемлемо. Например, для изображений это означает уменьшение разрешения, что приведет к потере мелких деталей и может сделать изображения вообще бесполезными (например, для медицинских или космических изображений). Для программ и текстов этот путь не применим
второе — увеличение объема носителей информации и пропускной способности каналов связи. Это решение связано с материальными затратами, причем иногда весьма значительными.
третье — использование сжатия информации. Это решение позволяет в несколько раз сократить требования к объему устройств хранения данных и пропускной способности каналов связи без дополнительных издержек (за исключением издержек на реализацию алгоритмов сжатия). Условиями его применимости является избыточность информации и возможность установки специального программного обеспечения либо аппаратуры для выполнения этих процедур.
Характерной особенностью большинства типов цифровых данных является их избыточность. Степень избыточности данных зависит от типа данных. Например, для видеоданных степень избыточности в несколько раз больше, чем для графических данных, а степень избыточности графических данных, в свою очередь, больше чем степень избыточности текстовых данных. Другим фактором, влияющим на степень избыточности, является принятая система кодирования. Эффективность кодирования можно увеличить при работе с определенным набором данных.
Теоретически доказано, что избыточность литературного русского текста составляет 0,6. Другими словами, при передаче текста по каналу связи каждые шесть букв из десяти передаваемых не несут никакой информации и могут безо всяких потерь просто не передаваться.
Такой же, если не более высокой ( ρи= 0,9...0,95) избыточностью обладают и другие источники информации - речь, и особенно музыка, телевизионные изображения и т.д.
Сжатие данных применяется во многих информационных системах. Современные радиотехнические системы передачи информации и связи просто не смогли бы работать, если бы в них не производилось такого рода сжатие. Не было бы цифровой сотовой связи стандартов GSM и CDMA. Не работали бы системы цифрового спутникового телевидения, очень неэффективной была бы работа Internet, а уж о том, чтобы посмотреть видеофильм или послушать хорошую музыку с лазерного диска, не могло быть и речи. Все это обеспечивается эффективным или экономным кодированием информации в данных системах.
II этап:
Демонстрация презентации в нужном темпе с пояснениями материала на каждом слайде.
Слайд 5(дополнительные пояснения):
Выбор системы неразрушающего(без потерь) или разрушающего(с потерями) сжатия зависит от типа данных, подлежащих сжатию. При сжатии текстовых данных, компьютерных программ, документов, чертежей и т.п. совершенно очевидно, что нужно применять неразрушающие методы, поскольку необходимо абсолютно точное восстановление исходной информации после ее сжатия. При сжатии речи, музыкальных данных и изображений, наоборот, чаще используется разрушающее сжатие, поскольку при практически незаметных искажениях оно обеспечивает на порядок, а иногда и на два меньшую скорость R. В общем случае разрушающее сжатие обеспечивает, как правило, существенно более высокие коэффициенты сжатия, нежели неразрушающее.
Слайд 18(дополнительные пояснения):
Рассмотрим принцип сжатия на основе словаря. LZ - это способ сжатия данных, который извлекает преимущества при повторяющихся цепочках данных. Исходный словарь для сжатия содержит словарь используемых символов. Затем в словарь будут добавлены цепочки символов, отличающиеся одним символом. Цепочки будут удлиняться, в тексте все чаще будут находиться словарные цепочки, которые будут заменяться ссылками на словарь. В словарь будут добавлены слова, фразы, строки текста. Эффект сжатия достигается за счет кодирования повторяющихся цепочек символов.
Представим себе этот процесс на примере сжатия фразы. Словарь уже построен, и интересующие нас цепочки добавляются в словарь(они будут повторяться в фразе). Они имеют цифровые ссылки. При повторном вхождении в фразу они заменяются ссылками. Очевидно, что данные сжимаются.
Существует целое семейство алгоритмов LZ, эффективных для разных типов данных.
Заключение II этапа:
Таким образом, будущее за новыми алгоритмами с высокими требованиями к ресурсам и все более и более высокой степенью сжатия.
Устаревают не только алгоритмы, но и типы информации, на которые они ориентированы. Так, на смену графике с малым числом цветов и неформатированному тексту пришли высококачественные изображения и электронные документы в различных форматах. Известные алгоритмы не всегда эффективны на новых типах данных. Это делает крайне актуальной проблему синтеза новых алгоритмов.
Предварительный просмотр:
Подписи к слайдам:
Цели сжатия данных – экономия ресурсов при хранении или передаче данных Сжатие данных это процесс, обеспечивающий уменьшение объема данных. Способы сжатия Изменение содержания данных (уменьшение избыточности данных) Изменение структуры данных (эффективное кодирование) Изменение содержания и структуры данных Исходные данные Восстановленные данные Новый формат Исходный формат Сжатые данные Архивация данных – сжатие с возможностью полного восстановления данных
Коэффициент сжатия – это величина для обозначения эффективности метода сжатия, равная отношению количества информации до и после сжатия Исходные данные Сжатые данные Размер файла 2МБ Размер файла 512 КБ К сж = 2 МБ / 0,5 МБ = 4
Сжатие данных может происходить с потерями и без потерь Сжатие без потерь (полностью обратимое) – это методы сжатия данных, при которых данные восстанавливаются после их распаковки полностью без внесения изменений (используется для текстов , программ ) Ксж до 50% Сжатие с регулируемыми потерями – это методы сжатия данных, при которых часть данных отбрасывается и не подлежит восстановлению ( используется для видео , звука , изображений) Ксж до 99%
Сжатие с потерями Тип данных Тип файла после сжатия Степень сжатия Графика .JPG до 99% Видео .MPG Звук .MP3 Тип данных Тип файла после сжатия Степень сжатия Графика .GIF .TIF .PCX До 50% Видео .AVI Любой тип .ZIP .ARJ .RAR .LZH Сжатие без потерь
Алгоритмы сжатия символьных данных Статистические методы – это методы сжатия, основанные на статистической обработке текста . Словарное сжатие – это методы сжатия, основанные на построении внутреннего словаря .
Упаковка однородных данных 0 0000 1 0001 2 0010 3 0011 4 0100 5 0101 6 0110 7 0111 8 1000 9 1001 _ 1010 + 1011 - 1100 , 1101 Закодируем сообщение длиной 16 символов 0,258-23,5+18,01 В кодировке ASCII сообщение составляет 16 байт . Новая кодовая таблица для упаковки : Код сообщения после упаковки составляет 8 байт : 000011010 01010101 00011000 0100011 110101011 01100011 00011010 0000001 K сж = 16 / 8 = 2
+ коэффициент сжатия увеличивается с увеличением размера символьного сообщения ; необходимо указывать для распаковки новую кодовую таблицу ; эффективен только для однородных сообщений , использующих ограниченный набор символов исходного алфавита ; + - - Достоинства и недостатки метода
Статистический метод сжатия Алгоритм Хаффмана Разные символы встречаются в сообщении с разной частотой , например для русского алфавита в среднем на 1000 символов : символ пробел о а р к я г ю ф частота 175 90 62 40 28 18 13 6 2 Зададим коды символам согласно частоте их повторения : чем чаще встречается символ , тем короче его код ( неравномерное кодирование)
Хаффмановское кодирование (сжатие) – это метод сжатия, присваивающий символам алфавита коды переменной длины , основы-ваясь на частоте появления этих символов в сообщении. символ код символа пробел 00 о 01 р 101 к 110 ю 0110 ф 1001
Проблема декодирования Пример : пусть коды символов a -10, b -101, c -1010 Декодировать сообщение 10101011010 10 101 1010 10 10 101 10 10 1010 101 1010 a a b c a a b a a c b c Однозначное декодирование возможно при условии Фано : никакое кодовое слово не является началом (префиксом) другого кодового слова .
Префиксный код – это код, в котором никакое кодовое слово не является префиксом любого другого кодового слова. Пример префиксного кода : 00 10 010 110 0110 0111 1110 1111 0 0 0 0 0 0 0 1 1 1 1 1 1 1 Префиксный код задается орграфом с размеченными листьями
Пример : построить код Хаффмана для фразы ОТ_ТОПОТА_КОПЫТ_ПЫЛЬ_ПО_ПОЛЮ_ЛЕТИТ Определим частоту вхождения символов в фразу : Строим орграф Хаффмана : -символ задает вершину- лист орграфа ; -вес вершины равен частоте вхождения символа ; -соединяются пары вершин с наименьшим весом : -левые ветви обозначаем 0 ; -правые ветви обозначаем 1 ; -определяем код символа от корня к листу ; символ А Е И К Л О П Т Ы Ь Ю _ частота 1 1 1 1 3 6 5 6 2 1 1 6
КОРЕНЬ ДЕРЕВА Т- О- Ы- _ П- Л- Ю- Ь- Е- К- И- А- 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 00011 00010 11000 11001 11011 11010 001 010 011 111 10 0000 Каждая вершина обозначена стрелкой
Построены префиксные коды символов : Сообщение в новых кодах содержит 110 бит , в кодировке ASCII – 34 * 8 = 272 бита тогда К сж = 272 / 110 = 2 ,47 Символ А Е И К Л О П Т Ы Ь Ю _ Код 11011 11000 11010 11001 001 10 011 010 0000 00011 00010 111 Длина кода 5 5 5 5 3 2 3 3 4 5 5 3
Алгоритм Хаффмана универсальный, его можно применять для сжатия данных любых типов ; Классический алгоритм Хаффмана требует хранения кодового дерева, что увеличивает размер файла. + - Достоинства и недостатки метода
Метод словарей Алгоритм сжатия LZ Этот алгоритм был впервые описан в работах А. Лемпеля и Дж. Зива ( Abraham Lempel , Jacob Ziv ) в 1977-78 гг., поэтому этот метод часто называется Lempel-Ziv , или сокращенно LZ. В его основе лежит идея замены наиболее часто встречающихся цепочек символов (строк) в файле ссылками на «образцы» цепочек, хранящиеся в специально создаваемой таблице (словаре).
Алгоритм ра з ра ботан из ра ильскими мат е мат ика ми Яко бо м Зив ом и Аб ра х ам ом Л ем пе лем . Словарь содержит , кроме многих других , такие цепочки : 1-ра 2-аб 3-ат 4-мат 5-ми_ 6-ам 7-бо 8-ом_ 9-бом 10-ем 11-лем Алгоритм раз1ботан из1ильскими мате4ика5Яко7ом Зив821х68 Л10пе11 Чем длиннее цепочка , заменяемая ссылкой в словарь , тем больше эффект сжатия .
-применим для любых данных ; - очень высокая скорость сжатия ; - высок коэффициент сжатия ; + - Достоинства и недостатки метода - словарь настроен на тип текста ; - словарь может быть очень большим ;
Вопросы по теме : Что такое архивирование данных ? Для данных каких типов возможно применять архивирование ? Для каких данных допустимо сжатие с потерями ? При каких условиях метод упаковки неэффективен ? Что такое префиксный код ? Для каких данных метод Хаффмана эффективен ? На каких принципах основан метод словарного сжатия ? Назовите известные вам программы для сжатия данных . Есть ли эффект от архивирования сжатых данных ? Почему ? Изменилось ли количество информации в звукозаписи после сжатия с потерями ? Поясните свой ответ . Изменилось ли количество информации в изображении после его архивирования ? Поясните свой ответ .
Домашнее задание : используя любые данные указанного типа , проведите эксперименты по архивированию . Результаты занесите в таблицу и поясните полученный эффект сжатия . Тип данных Исходный формат Исходный размер Формат архива Размер архива Абсолютная величина сжатия( вМБ ) Коэффициент сжатия Пояснение эффекта сжатия Текст .doc . pdf Видео . avi .mpg Изображение .bmp .jpeg Звук .mp3 .midi К сж= ( исходный размер файла – размер файла архива) / исходный размер файла
По теме: методические разработки, презентации и конспекты
Открытый урок по теме "Сжатое изложение"
Урок-практикум "Подготовка к написанию сжатого изложения" предназначен для работы в классах с средними и низкими учебными возможностями....
Конспект урока по теме "Экспериментальные данные и вероятности событий"
Комбинированный урок с применением технологии проблемного обучения. На уроке используется виртуальная лаборатория "Вероятностные модели". Расписаны цели и формируемые УУД к каждому этапу урока....
Урок по теме: «Базы данных Microsoft Access»
Познакомить учащихся с понятиями: информационно-поисковая система база данных с ее основными элементами и видами; практическое применение теоретического материала; первоначальные умения по...
Разработка урока по теме «Базы данных»
Средства ИКТ не только обеспечивают образование с использованием той же технологии, которую учащиеся применяют для связи и развлечений вне школы, но и создают условия для индивидуализации у...
открытый урок по теме Архивация данных. 10 класс. профиль
двухчасовое заняти по изучению темы "Архивацияфайлов" с презентацией,тестом (+ключ к тесту) по проверке знаний предыдущих уроков (Аппаратное и программное обеспечение), опорным конспектом для учащихся...
Раздаточные материалы к уроку по теме "Известные люди Китая. Анкетные данные" （китайский язык）
......
Уроки по теме "Базы данных"
Разработка содержит пять уроков по теме "Базы данных", данный материал может быть использован, как в 11 классе, так и в 9-м классе при знакомстве с понятием баз данных, в сокращенном виде. Э...