Презентация - Сжатие информации:"Алгоритм Хаффмана"

Нажмите для просмотра
Сжатие информации:"Алгоритм Хаффмана"
Распечатать
  • Последний IP: 213.180.203.85
  • Уникальность: 84%
  • Слайдов: 46
  • Просмотров: 1294
  • Скачиваний: 714
  • Размер: 1.3 MB
  • Онлайн: Да
  • Формат: ppt и pptx
В закладки
Оцени!

Слайды и текст этой онлайн презентации

Слайд 1

Сжатие информации:"Алгоритм Хаффмана", слайд 1
Сжатие информации Алгоритм Хаффмана

Слайд 2

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

Слайд 3

Сжатие информации:"Алгоритм Хаффмана", слайд 3
Сжатие информации Сжатие данных – сокращение объема данных при сохранении закодированного в них содержания.

Слайд 4

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

Слайд 5

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

Слайд 6

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

Слайд 7

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

Слайд 8

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

Слайд 9

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

Слайд 10

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

Слайд 11

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

Слайд 12

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

Слайд 13

Сжатие информации:"Алгоритм Хаффмана", слайд 13

Слайд 14

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

Слайд 15

Сжатие информации:"Алгоритм Хаффмана", слайд 15

Слайд 16

Сжатие информации:"Алгоритм Хаффмана", слайд 16

Слайд 17

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

Слайд 18

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

Слайд 19

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

Слайд 20

Сжатие информации:"Алгоритм Хаффмана", слайд 20
3. Выбираем 2 значения с минимальными весами ( р и у ), суммируем их веса и заменяем эти значения в таблице одним объединенным значением: м а - ы л ру 4 4 2 1 1 2

Слайд 21

Сжатие информации:"Алгоритм Хаффмана", слайд 21
Формируем дерево

Слайд 22

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

Слайд 23

Сжатие информации:"Алгоритм Хаффмана", слайд 23
Дерево стало таким:

Слайд 24

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

Слайд 25

Сжатие информации:"Алгоритм Хаффмана", слайд 25
Дерево стало таким :

Слайд 26

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

Слайд 27

Сжатие информации:"Алгоритм Хаффмана", слайд 27
Дерево стало таким:

Слайд 28

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

Слайд 29

Сжатие информации:"Алгоритм Хаффмана", слайд 29
Дерево стало таким:

Слайд 30

Сжатие информации:"Алгоритм Хаффмана", слайд 30
Последний шаг: МА ЫЛРУ 14

Слайд 31

Сжатие информации:"Алгоритм Хаффмана", слайд 31

Слайд 32

Сжатие информации:"Алгоритм Хаффмана", слайд 32

Слайд 33

Сжатие информации:"Алгоритм Хаффмана", слайд 33
РЕЗУЛЬТАТ м а - ы л р у 00 01 10 1100 1101 1110 1111 4 4 2 1 1 1 1 КОЭФФИЦИЕНТ СЖАТИЯ: 112/40 2,8

Слайд 34

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

Слайд 35

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

Слайд 36

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

Слайд 37

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

Слайд 38

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

Слайд 39

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

Слайд 40

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

Слайд 41

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

Слайд 42

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

Слайд 43

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

Слайд 44

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

Слайд 45

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

Слайд 46

Сжатие информации:"Алгоритм Хаффмана", слайд 46
Список используемой литературы: Педагогический университет «Первое сентября», 2008г. И. Г. Семакин «Информатика и ИКТ» 10 класс профильный уровень,2012
^ Наверх
X

Благодарим за оценку!

Мы будем признательны, если Вы так же поделитесь этой презентацией со своими друзьями и подписчиками.