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

Презентация к уроку информатики по учебнику И.Г. Семакин, Т. Ю. Шеина, Л. В. Шестакова, Информатика и ИКТ(профильный уровень) 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 в тетради

По теме: методические разработки, презентации и конспекты

Разработка урока на тему: Двоичное кодирование числовой информации. Перевод целых десятичных чисел в двоичный код.

Разработка ученицы 11 класса.

Урок по информатике в 6 классе по теме "Двоичное кодирование числовой информации. Перевод целых десятичных чисел в двоичную систему счисления"В материалы урока входят конспект урока, презентация.

В МБОУ Липницкой СОШ с 5 по 10 декабря 2016г. прошла Всероссийская акция «Час кода» в рамках Международной недели изучения информатики и Дня информ.

технологическая карта урока.

Рабочая программа углубленного преподавания информатики и программирования дл я 3-11 класса.

Урок рассматривает вопросы записи чисел в двоичном виде и переводу чисел из двоичной записи в десятичную с помощью двоичного ряда, 6 класс. Презентация, представленная с технологической картой урока, .

Идёт приём заявок

Подать заявку

Для учеников 1-11 классов и дошкольников

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Список используемой литературы: 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?PHPSESS >

Чтобы скачать материал, введите свой E-mail, укажите, кто Вы, и нажмите кнопку

Нажимая кнопку, Вы соглашаетесь получать от нас E-mail-рассылку

Если скачивание материала не началось, нажмите еще раз "Скачать материал".

• Информатика

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

Содержимое разработки

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

• Потеря информации в результате сжатия недопустима;
• Допустима частичная потеря информации в результате сжатия.

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

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

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

Сжатие без потери информации:

• использование неравномерного кода; выявление повторяющихся фрагментов кода.
• использование неравномерного кода; выявление повторяющихся фрагментов кода.
• использование неравномерного кода;
• выявление повторяющихся фрагментов кода.

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

Важнейшая характеристика процесса сжатия – коэффициент сжатия.

Коэффициент сжатия – отношение объема исходного сообщения к объему сжатого.

Алгоритмы сжатия, использование неравномерного кода

В основе первого подхода лежит использование неравномерного кода.

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

Сжатие с использованием кодов переменной длины

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

Алгоритм Хаффмана — адаптивный алгоритм оптимального префиксного кодирования алфавита с минимальной избыточностью.

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

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

Чтобы понять, как строятся префиксные коды, рассмотрим, как построить ориентированный граф, определяющий этот код.

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

Построим граф этого кода.

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

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

Из получившихся вершин снова проводятся дуги — и так далее, до тех пор, пока не будут исчерпаны все коды.

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

Деревом называется графическое представление (граф) структуры связей между элементами некоторой системы.

Двоичным деревом называется дерево, в котором любая вершина, имеет не более двух потомков.

Корнем дерева называется единственная вершина, не имеющая родительской вершины.

Листьями дерева называются вершины, не имеющие потомков.

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

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