Главная / Информатика / Презентация по информатике на тему "Сжатие информации. Алгоритм Хаффмана" (10 класс)

Презентация по информатике на тему "Сжатие информации. Алгоритм Хаффмана" (10 класс)

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

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

№ слайда 1 Сжатие информации Алгоритм Хаффмана Создатель: учитель информатики Москвитина Е.
Описание слайда:

Сжатие информации Алгоритм Хаффмана Создатель: учитель информатики Москвитина Е.В.

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

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

№ слайда 3 Сжатие информации Сжатие данных – сокращение объема данных при сохранении закоди
Описание слайда:

Сжатие информации Сжатие данных – сокращение объема данных при сохранении закодированного в них содержания.

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

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

№ слайда 5 Сжатие информации Сжатие происходит за счет устранения избыточности кода, наприм
Описание слайда:

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

№ слайда 6 Алгоритмы сжатия, использование неравномерного кода В основе первого подхода леж
Описание слайда:

Алгоритмы сжатия, использование неравномерного кода В основе первого подхода лежит использование неравномерного кода. В восьмиразрядной таблице символьной кодировки (ASCII), каждый символ кодируется восемью битами и, следовательно, занимает в памяти 1 байт. Информационный вес символа тем больше, чем меньше его частота встречаемости. С этим обстоятельством и связана идея сжатия текста в компьютерной памяти: отказаться от одинаковой длины кодов символов.

№ слайда 7 Сжатие с использованием кодов переменной длины Одним из простейших, но весьма эф
Описание слайда:

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

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

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

№ слайда 9 Таблица Хаффмана Особенностью данного кода является его префиксная структура. Эт
Описание слайда:

Таблица Хаффмана Особенностью данного кода является его префиксная структура. Это значит, что код любого символа не совпадает с началом кода всех остальных символов.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

№ слайда 34 Алгоритм кода Хаффмана: 1. Символы исходного алфавита образуют вершины. Вес кажд
Описание слайда:

Алгоритм кода Хаффмана: 1. Символы исходного алфавита образуют вершины. Вес каждой вершины вес равен количеству вхождений данного символа в сжимаемое сообщение. 2. Среди вершин выбираются две с наименьшими весами (если таких пар несколько, выбирается любая из них). 3. Создается следующая вершина графа, из которой выходят две дуги к выбранным вершинам; одна дуга помечается цифрой 0, другая — символом 1. Вес созданной вершины равен сумме весов, выбранных на втором шаге вершин. 4. К новым вершинам применяются шаги 2 и 3 до тех пор, пока не останется одна вершина с весом, равным сумме весов исходных символов.

№ слайда 35 Математики доказали, что среди алгоритмов, кодирующих каждый символ по отдельнос
Описание слайда:

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

№ слайда 36 Ко второму подходу к сжатию без потерь относится подход, основанный на идее выяв
Описание слайда:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

№ слайда 46 Список используемой литературы: http://crazycode.net/blog/10-algorithms-and-data
Описание слайда:

Список используемой литературы: http://crazycode.net/blog/10-algorithms-and-data-structures/31-huffman http://edu.1september.ru/courses/07/008/01.pdf http://www.lukomor.ru/attach/pages/ege13/A09.pdf?PHPSESSID=9fa7039ee3de232e76b2a13614accbf5 Педагогический университет «Первое сентября», 2008г. И.Г. Семакин «Информатика и ИКТ» 10 класс профильный уровень,2012

Презентация по информатике на тему "Сжатие информации. Алгоритм Хаффмана" (10 класс)
  • Информатика
Описание:

Данная презентация предназнача для 10 класса (профильного) на урок информатики по теме "Сжатие двоичного кода.Алгоритм Хаффмана". Особое внимание уделяется на виды сжатия иформации (с потерей и без потери информации). Подробно описывается алгоритм Хаффмана, приводятся примеры, рассчитывается коэффициент сжатия информации; для закрепления даны задачи для самостоятелного решения; также в конце приведены задания по данной теме, которые встречаются в ЕГЭ, первые задачи приведены с решением, затем опять для самостоятельно решения, для закрепления полученных знаний.

Автор Москвитина Екатерина Васильевна
Дата добавления 17.11.2014
Раздел Информатика
Подраздел Презентации
Просмотров 1715
Номер материала 1562
Скачать свидетельство о публикации

Оставьте свой комментарий:

Введите символы, которые изображены на картинке:

Получить новый код
* Обязательные для заполнения.


Комментарии:

↓ Показать еще коментарии ↓