Добавить материал и получить бесплатное свидетельство о публикации в СМИ
Эл. №ФС77-60625 от 20.01.2015
Свидетельство о публикации

Автоматическая выдача свидетельства о публикации в официальном СМИ сразу после добавления материала на сайт - Бесплатно

Добавить свой материал

За каждый опубликованный материал Вы получите бесплатное свидетельство о публикации от проекта «Инфоурок»

(Свидетельство о регистрации СМИ: Эл №ФС77-60625 от 20.01.2015)

Инфоурок / Информатика / Презентации / Презентация по информатике на тему "Сжатие двоичного кода" (10 класс, профильный уровень)
ВНИМАНИЮ ВСЕХ УЧИТЕЛЕЙ: согласно Федеральному закону № 313-ФЗ от 03.07.2016 все педагоги должны пройти обучение навыкам оказания первой помощи.

Дистанционный курс "Оказание первой помощи детям и взрослым" от проекта "Инфоурок" даёт Вам возможность привести свои знания в соответствие с требованиями закона и получить удостоверение о повышении квалификации установленного образца (180 часов). Начало обучения новой группы: 26 апреля.


Подать заявку на курс
  • Информатика

Презентация по информатике на тему "Сжатие двоичного кода" (10 класс, профильный уровень)

библиотека
материалов
Сжатие двоичного кода
Любая информация в компьютере представляется в форме двоичного кода. Чем бол...
Для сокращения объема данных выполняется их сжатие. Сжатие данных – это проце...
При упаковке данных в файловые архивы производится их сжатие без потери инфо...
Например: Если сжатию подвергается текст, то после распаковки в нем не должен...
Сжатие с частичной потерей информации Производится при сжатии кода изображени...
Сжатие кода графики. Объем кода можно сократить за счет того, что коды цвета...
Сжатие кода видео. Быстро меняющиеся фрагменты фильма можно кодировать менее...
Сжатие кода звука. Поддается труднее всего. При хорошем качестве записи его о...
Сжатие без потери информации Первый подход: использование неравномерного кода...
Использование неравномерного кода. Символы с меньшим информационным весом, т....
Одним из простейших, но весьма эффективных способов построения двоичного нер...
Алгоритм Хаффмана - Адаптивный алгоритм оптимального префиксного кодирования ...
Таблица Хаффмана В этой таблице буквы расположены в порядке убывания частоты...
Префиксные коды Чтобы понять, как строятся префиксные коды, рассмотрим, как п...
Префиксные коды Построим граф этого кода. Из начальной вершины выходят две ду...
Префиксные коды Если при этом какая-то последовательность оказывается прочита...
Коэффициентом сжатия называют отношение длины кода в байтах после сжатия к ег...
Графическое изображение дерева Хаффмана, соответствующего табл. 1.8
Пример: Предположим, что необходимо выполнить сжатие текстового документа с ф...
1. Составляем таблицу частот, то есть, подсчитываем количество вхождений кажд...
2. Сортируем значения в таблице по весам, в порядке спадания: м а - ы л р у 4...
3. Выбираем 2 значения с минимальными весами (“р” и “у”), суммируем их веса и...
Формируем дерево
4. Снова выбираем 2 значения с минимальными весами (“ы” и “л”), делаем с ними...
Дерево стало таким:
5. Снова выбираем 2 значения с минимальными весами (“ыл” и “ру”), делаем с ни...
Дерево стало таким:
6. Снова выбираем 2 значения с минимальными весами (“_” и “ылру”), делаем с н...
Дерево стало таким:
7. Снова выбираем 2 значения с минимальными весами (“м” и “а”), делаем с ними...
Дерево стало таким:
Последний шаг: МА_ЫЛРУ 14
РЕЗУЛЬТАТ КОЭФФИЦИЕНТ СЖАТИЯ: 112/40=2,8 м а - ы л р у 00 01 10 1100 1101 111...
Решить самостоятельно: Постройте код Хаффмана для фраз и определить коэффицие...
Решить самостоятельно: 2. Закодируйте с помощью кода Хаффмана следующий текст...
Для кодирования сообщения, состоящего из букв А, Б, В, Г и Д, используется не...
Задача А9. Решение. Построим двоичное дерево, в котором от каждого узла отход...
Задача А9. Решение. По дереву определим, что для букв Г и Д код можно сократи...
Для передачи по каналу связи сообщения, состоящего только из букв А, Б, В, Г,...
Для 5 букв латинского алфавита заданы их двоичные коды. Эти коды представлены...
Для передачи по каналу связи сообщения, состоящего только из букв А, Б, В, Г,...
Д/З Постройте код Хаффмана для фраз и определить коэффициент сжатия. ОТ_ТОПОТ...
47 1

"Инфоурок" приглашает всех педагогов и детей к участию в самой массовой интернет-олимпиаде «Весна 2017» с рекордно низкой оплатой за одного ученика - всего 45 рублей

В олимпиадах "Инфоурок" лучшие условия для учителей и учеников:

1. невероятно низкий размер орг.взноса — всего 58 рублей, из которых 13 рублей остаётся учителю на компенсацию расходов;
2. подходящие по сложности для большинства учеников задания;
3. призовой фонд 1.000.000 рублей для самых активных учителей;
4. официальные наградные документы для учителей бесплатно(от организатора - ООО "Инфоурок" - имеющего образовательную лицензию и свидетельство СМИ) - при участии от 10 учеников
5. бесплатный доступ ко всем видеоурокам проекта "Инфоурок";
6. легко подать заявку, не нужно отправлять ответы в бумажном виде;
7. родителям всех учеников - благодарственные письма от «Инфоурок».
и многое другое...

Подайте заявку сейчас - https://infourok.ru/konkurs

Описание презентации по отдельным слайдам:

№ слайда 1 Сжатие двоичного кода
Описание слайда:

Сжатие двоичного кода

№ слайда 2 Любая информация в компьютере представляется в форме двоичного кода. Чем бол
Описание слайда:

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

№ слайда 3 Для сокращения объема данных выполняется их сжатие. Сжатие данных – это проце
Описание слайда:

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

№ слайда 4 При упаковке данных в файловые архивы производится их сжатие без потери инфо
Описание слайда:

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

№ слайда 5 Например: Если сжатию подвергается текст, то после распаковки в нем не должен
Описание слайда:

Например: Если сжатию подвергается текст, то после распаковки в нем не должен быть искажен ни один символ. Сжатая программа также должна полностью восстанавливаться, поскольку малейшее искажение приведет ее в неработоспособное состояние.

№ слайда 6 Сжатие с частичной потерей информации Производится при сжатии кода изображени
Описание слайда:

Сжатие с частичной потерей информации Производится при сжатии кода изображения (графики, видео) и звука.

№ слайда 7 Сжатие кода графики. Объем кода можно сократить за счет того, что коды цвета
Описание слайда:

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

№ слайда 8 Сжатие кода видео. Быстро меняющиеся фрагменты фильма можно кодировать менее
Описание слайда:

Сжатие кода видео. Быстро меняющиеся фрагменты фильма можно кодировать менее подробно, чем статические кадры.

№ слайда 9 Сжатие кода звука. Поддается труднее всего. При хорошем качестве записи его о
Описание слайда:

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

№ слайда 10 Сжатие без потери информации Первый подход: использование неравномерного кода
Описание слайда:

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

№ слайда 11 Использование неравномерного кода. Символы с меньшим информационным весом, т.
Описание слайда:

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

№ слайда 12 Одним из простейших, но весьма эффективных способов построения двоичного нер
Описание слайда:

Одним из простейших, но весьма эффективных способов построения двоичного неравномерно кода, является алгоритм Дэвида Хаффмана

№ слайда 13 Алгоритм Хаффмана - Адаптивный алгоритм оптимального префиксного кодирования 
Описание слайда:

Алгоритм Хаффмана - Адаптивный алгоритм оптимального префиксного кодирования алфавита с минимальной избыточностью. Был разработан 1952 году аспирантом Массачусетского технологического института Дэвидом Хаффманом при написании им курсовой работы. В настоящее время используется во многих программах сжатия данных.

№ слайда 14 Таблица Хаффмана В этой таблице буквы расположены в порядке убывания частоты
Описание слайда:

Таблица Хаффмана В этой таблице буквы расположены в порядке убывания частоты повторяемости в тексте. Самые часто используемые в текстах буквы «Е» и «Т» имеют коды размером 3 бита, а самые редкие буквы «Q» и «Z» – 10 битов. Особенностью данного кода является его префиксная структура. Это значит, что код любого символа не совпадает с началом кода всех остальных символов.

№ слайда 15 Префиксные коды Чтобы понять, как строятся префиксные коды, рассмотрим, как п
Описание слайда:

Префиксные коды Чтобы понять, как строятся префиксные коды, рассмотрим, как построить ориентированный граф, определяющий этот код. Например, кодовые слова 00, 01, 10, 011, 100, 101, 1001, 1010, 1111, кодируют соответственно буквы: a, b, c, d, e, f, g, h, i.

№ слайда 16 Префиксные коды Построим граф этого кода. Из начальной вершины выходят две ду
Описание слайда:

Префиксные коды Построим граф этого кода. Из начальной вершины выходят две дуги, помеченные 0 и 1. Затем из конца каждой такой дуги входят новые дуги, помеченные 0 и 1 так, чтобы, идя по этим дугам от корня, читалось начало какого-либо кодового слова.

№ слайда 17 Префиксные коды Если при этом какая-то последовательность оказывается прочита
Описание слайда:

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

№ слайда 18
Описание слайда:

№ слайда 19 Коэффициентом сжатия называют отношение длины кода в байтах после сжатия к ег
Описание слайда:

Коэффициентом сжатия называют отношение длины кода в байтах после сжатия к его длине до сжатия. В данном примере: коэффициент сжатия = 16/29  0,55 Раскодирование (распаковка) текста производится с помощью двоичного дерева кодирования Хаффмана. Деревом называется графическое представление (граф) структуры связей между элементами некоторой системы. Двоичным деревом называется дерево, в котором любая вершина, имеет не более двух потомков. Корнем дерева называется единственная вершина, не имеющая родительской вершины. Листьями дерева называются вершины, не имеющие потомков.

№ слайда 20 Графическое изображение дерева Хаффмана, соответствующего табл. 1.8
Описание слайда:

Графическое изображение дерева Хаффмана, соответствующего табл. 1.8

№ слайда 21
Описание слайда:

№ слайда 22 Пример: Предположим, что необходимо выполнить сжатие текстового документа с ф
Описание слайда:

Пример: Предположим, что необходимо выполнить сжатие текстового документа с фразой “мама_мыла_раму”. Наш исходный текст “весит” 112 бит, так как каждый символ занимает 8 бит в кодовой таблице, а таких символов у нас 14 штук.

№ слайда 23 1. Составляем таблицу частот, то есть, подсчитываем количество вхождений кажд
Описание слайда:

1. Составляем таблицу частот, то есть, подсчитываем количество вхождений каждой буквы во фразу, в результате чего получим вес каждой буквы: у р л ы - а М 1 1 1 1 2 4 4

№ слайда 24 2. Сортируем значения в таблице по весам, в порядке спадания: м а - ы л р у 4
Описание слайда:

2. Сортируем значения в таблице по весам, в порядке спадания: м а - ы л р у 4 4 2 1 1 1 1

№ слайда 25 3. Выбираем 2 значения с минимальными весами (“р” и “у”), суммируем их веса и
Описание слайда:

3. Выбираем 2 значения с минимальными весами (“р” и “у”), суммируем их веса и заменяем эти значения в таблице одним объединенным значением: м а - ы л ру 4 4 2 1 1 2

№ слайда 26 Формируем дерево
Описание слайда:

Формируем дерево

№ слайда 27 4. Снова выбираем 2 значения с минимальными весами (“ы” и “л”), делаем с ними
Описание слайда:

4. Снова выбираем 2 значения с минимальными весами (“ы” и “л”), делаем с ними то же, что и на предыдущем шаге: М А - ЫЛ РУ 4 4 2 2 2

№ слайда 28 Дерево стало таким:
Описание слайда:

Дерево стало таким:

№ слайда 29 5. Снова выбираем 2 значения с минимальными весами (“ыл” и “ру”), делаем с ни
Описание слайда:

5. Снова выбираем 2 значения с минимальными весами (“ыл” и “ру”), делаем с ними то же, что и на предыдущем шаге: М Ф - ЫЛРУ 4 4 2 4

№ слайда 30 Дерево стало таким:
Описание слайда:

Дерево стало таким:

№ слайда 31 6. Снова выбираем 2 значения с минимальными весами (“_” и “ылру”), делаем с н
Описание слайда:

6. Снова выбираем 2 значения с минимальными весами (“_” и “ылру”), делаем с ними то же, что и на предыдущем шаге М А -ЫЛРУ 4 4 6

№ слайда 32 Дерево стало таким:
Описание слайда:

Дерево стало таким:

№ слайда 33 7. Снова выбираем 2 значения с минимальными весами (“м” и “а”), делаем с ними
Описание слайда:

7. Снова выбираем 2 значения с минимальными весами (“м” и “а”), делаем с ними то же, что и на предыдущем шаге: МА -ЫЛРУ 8 6

№ слайда 34 Дерево стало таким:
Описание слайда:

Дерево стало таким:

№ слайда 35 Последний шаг: МА_ЫЛРУ 14
Описание слайда:

Последний шаг: МА_ЫЛРУ 14

№ слайда 36
Описание слайда:

№ слайда 37
Описание слайда:

№ слайда 38 РЕЗУЛЬТАТ КОЭФФИЦИЕНТ СЖАТИЯ: 112/40=2,8 м а - ы л р у 00 01 10 1100 1101 111
Описание слайда:

РЕЗУЛЬТАТ КОЭФФИЦИЕНТ СЖАТИЯ: 112/40=2,8 м а - ы л р у 00 01 10 1100 1101 1110 1111 4 4 2 1 1 1 1

№ слайда 39 Решить самостоятельно: Постройте код Хаффмана для фраз и определить коэффицие
Описание слайда:

Решить самостоятельно: Постройте код Хаффмана для фраз и определить коэффициент сжатия. Карл_ у_клары_украл_ кораллы, а_клара_У_карла_украла_кларнет НА_ ДВОРЕ_ ТРАВА,_ НА_ ТРАВЕ_ ДРОВА

№ слайда 40 Решить самостоятельно: 2. Закодируйте с помощью кода Хаффмана следующий текст
Описание слайда:

Решить самостоятельно: 2. Закодируйте с помощью кода Хаффмана следующий текст: HAPPYNEWYEAR 3. Расшифруйте с помощью двоичного дерева Хаффмана следующий код: 11110111 10111100 00011100 00101100 10010011 01110100 11001111 11101101 001100

№ слайда 41 Для кодирования сообщения, состоящего из букв А, Б, В, Г и Д, используется не
Описание слайда:

Для кодирования сообщения, состоящего из букв А, Б, В, Г и Д, используется неравномерный двоичный код, позволяющий однозначно декодировать полученную двоичную последовательность. А–00, Б–010, В–011, Г–101, Д–111. Можно ли сократить для одной из букв длину кодового слова так, чтобы код по-прежнему можно было декодировать однозначно? Выберите правильный вариант ответа. 1) для буквы Б – 01 2) это невозможно 3) для буквы В – 01 4) для буквы Г – 01 Задача А9

№ слайда 42 Задача А9. Решение. Построим двоичное дерево, в котором от каждого узла отход
Описание слайда:

Задача А9. Решение. Построим двоичное дерево, в котором от каждого узла отходит две ветки: 0 или 1. Разместим на дереве буквы А, Б, В, Г и Д так, чтобы их код получался как последовательность чисел на рёбрах: 0 0 0 0 0 1 0 1 1 1 1 0 1 1 корень А Б В Г Д

№ слайда 43 Задача А9. Решение. По дереву определим, что для букв Г и Д код можно сократи
Описание слайда:

Задача А9. Решение. По дереву определим, что для букв Г и Д код можно сократить. Выберем ответ из предложенных вариантов: 1) для буквы Б – 01 2) это невозможно 3) для буквы В – 01 4) для буквы Г – 01 Ответ: 4. 0 0 0 0 0 1 0 1 1 1 1 0 1 1 А Б В Г Д

№ слайда 44 Для передачи по каналу связи сообщения, состоящего только из букв А, Б, В, Г,
Описание слайда:

Для передачи по каналу связи сообщения, состоящего только из букв А, Б, В, Г, решили использовать неравномерный по длине код: A=0, Б=10, В=110. Как нужно закодировать букву Г, чтобы длина кода была минимальной и допускалось однозначное разбиение кодированного сообщения на буквы? 1) 1 2) 1110 3) 111 4) 11 Для самостоятельной работы

№ слайда 45 Для 5 букв латинского алфавита заданы их двоичные коды. Эти коды представлены
Описание слайда:

Для 5 букв латинского алфавита заданы их двоичные коды. Эти коды представлены в таблице: Задача А9 Определить, какой набор букв закодирован двоичной строкой 0110100011000 A B C D E 000 01 100 10 011

№ слайда 46 Для передачи по каналу связи сообщения, состоящего только из букв А, Б, В, Г,
Описание слайда:

Для передачи по каналу связи сообщения, состоящего только из букв А, Б, В, Г, решили использовать неравномерный по длине код: A=0, Б=10, В=110. Как нужно закодировать букву Г, чтобы длина кода была минимальной и допускалось однозначное разбиение кодированного сообщения на буквы? Задача А9

№ слайда 47 Д/З Постройте код Хаффмана для фраз и определить коэффициент сжатия. ОТ_ТОПОТ
Описание слайда:

Д/З Постройте код Хаффмана для фраз и определить коэффициент сжатия. ОТ_ТОПОТА_КОПЫТ_ПЫЛЬ_ПО_ПОЛЮ_ЛЕТИТ ШЛА_САША_ПО_ШОССЕ_И СОСАЛА_СУШКУ

Автор
Дата добавления 23.11.2016
Раздел Информатика
Подраздел Презентации
Просмотров115
Номер материала ДБ-381552
Получить свидетельство о публикации

"Инфоурок" приглашает всех педагогов и детей к участию в самой массовой интернет-олимпиаде «Весна 2017» с рекордно низкой оплатой за одного ученика - всего 45 рублей

В олимпиадах "Инфоурок" лучшие условия для учителей и учеников:

1. невероятно низкий размер орг.взноса — всего 58 рублей, из которых 13 рублей остаётся учителю на компенсацию расходов;
2. подходящие по сложности для большинства учеников задания;
3. призовой фонд 1.000.000 рублей для самых активных учителей;
4. официальные наградные документы для учителей бесплатно(от организатора - ООО "Инфоурок" - имеющего образовательную лицензию и свидетельство СМИ) - при участии от 10 учеников
5. бесплатный доступ ко всем видеоурокам проекта "Инфоурок";
6. легко подать заявку, не нужно отправлять ответы в бумажном виде;
7. родителям всех учеников - благодарственные письма от «Инфоурок».
и многое другое...

Подайте заявку сейчас - https://infourok.ru/konkurs


Выберите специальность, которую Вы хотите получить:

Обучение проходит дистанционно на сайте проекта "Инфоурок".
По итогам обучения слушателям выдаются печатные дипломы установленного образца.

ПЕРЕЙТИ В КАТАЛОГ КУРСОВ


Идёт приём заявок на международный конкурс по математике "Весенний марафон" для учеников 1-11 классов и дошкольников

Уникальность конкурса в преимуществах для учителей и учеников:

1. Задания подходят для учеников с любым уровнем знаний;
2. Бесплатные наградные документы для учителей;
3. Невероятно низкий орг.взнос - всего 38 рублей;
4. Публикация рейтинга классов по итогам конкурса;
и многое другое...

Подайте заявку сейчас - https://urokimatematiki.ru

Похожие материалы

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