Школа » Презентации » Презентации по Информатике » Алгоритм построения орграфа Хаффмана (алгоритм сжатия)

Презентация - "Алгоритм построения орграфа Хаффмана (алгоритм сжатия)"

0
14.10.20
На нашем сайте презентаций klass-uchebnik.com вы можете бесплатно ознакомиться с полной версией презентации "Алгоритм построения орграфа Хаффмана (алгоритм сжатия)". Учебное пособие по дисциплине - Презентации / Презентации по Информатике, от атора . Презентации нашего сайта - незаменимый инструмент для школьников, здесь они могут изучать и просматривать слайды презентаций прямо на сайте на вашем устройстве (IPhone, Android, PC) совершенно бесплатно, без необходимости регистрации и отправки СМС. Кроме того, у вас есть возможность скачать презентации на ваше устройство в формате PPT (PPTX).
Алгоритм построения орграфа Хаффмана (алгоритм сжатия) 📚 Учебники, Презентации и Подготовка к Экзаменам для Школьников на Klass-Uchebnik.com

0
0
0

Поделиться презентацией "Алгоритм построения орграфа Хаффмана (алгоритм сжатия)" в социальных сетях: 

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

Алгоритм построения орграфа Хаффмана (алгоритм сжатия) Учитель информатики: Константинова Елена Иван
1 слайд

Алгоритм построения орграфа Хаффмана (алгоритм сжатия) Учитель информатики: Константинова Елена Ивановна Муниципальное образовательное учреждение Раменская средняя общеобразовательная школа №8

Давид Хаффман (1925-1999) Давид начал свою научную карьеру студентом в Массачусетсом технологическом
2 слайд

Давид Хаффман (1925-1999) Давид начал свою научную карьеру студентом в Массачусетсом технологическом институте (MIT), где построил свои коды в начале пятидесятых годов прошлого века.

Закодируем предложение «НА_ДВОРЕ_ТРАВА,_НА_ТРАВЕ_ДРОВА» Вначале нужно подсчитать количество вхождени
3 слайд

Закодируем предложение «НА_ДВОРЕ_ТРАВА,_НА_ТРАВЕ_ДРОВА» Вначале нужно подсчитать количество вхождений каждого символа в тексте. Создаем первый узел 0 1 3 6 4 2 1 2 2 4 2 2 5 а в д , е н р о т _ 6 4 2 1 2 2 4 2 2 5 а в д , е н р о т _

Создаем еще один узел 1 1 4 0 4 0 0 1 3 0 0 1 1 4 Создаем еще один узел 3 6 4 2 1 2 2 4 2 2 5 а в д
4 слайд

Создаем еще один узел 1 1 4 0 4 0 0 1 3 0 0 1 1 4 Создаем еще один узел 3 6 4 2 1 2 2 4 2 2 5 а в д , е н р о т _ 6 4 2 1 2 2 4 2 2 5 а в д , е н р о т _

Создаем еще один узел 1 1 1 0 0 4 0 0 0 1 7 1 8 7 0 0 0 0 1 1 1 1 4 4 Создаем еще один узел 6 4 2 1
5 слайд

Создаем еще один узел 1 1 1 0 0 4 0 0 0 1 7 1 8 7 0 0 0 0 1 1 1 1 4 4 Создаем еще один узел 6 4 2 1 2 2 4 2 2 5 а в д , е н р о т _ 6 4 2 1 2 2 4 2 2 5 а в д , е н р о т _

Создаем еще один узел 1 1 1 1 0 0 0 0 0 0 1 7 1 8 9 6 4 2 1 2 2 4 2 2 5 а в д , е н р о т _
6 слайд

Создаем еще один узел 1 1 1 1 0 0 0 0 0 0 1 7 1 8 9 6 4 2 1 2 2 4 2 2 5 а в д , е н р о т _

Создаем еще один узел 1 1 1 1 0 0 0 0 0 0 0 1 1 1 13 8 9 6 4 2 1 2 2 4 2 2 5 а в д , е н р о т _
7 слайд

Создаем еще один узел 1 1 1 1 0 0 0 0 0 0 0 1 1 1 13 8 9 6 4 2 1 2 2 4 2 2 5 а в д , е н р о т _

Создаем еще один узел 1 1 1 1 1 0 0 0 0 0 0 0 0 1 1 1 13 17 6 4 2 1 2 2 4 2 2 5 а в д , е н р о т _
8 слайд

Создаем еще один узел 1 1 1 1 1 0 0 0 0 0 0 0 0 1 1 1 13 17 6 4 2 1 2 2 4 2 2 5 а в д , е н р о т _

Создаем еще один узел 30 0 1 1 1 1 1 1 0 0 0 0 0 0 0 0 1 1 1 6 4 2 1 2 2 4 2 2 5 а в д , е н р о т _
9 слайд

Создаем еще один узел 30 0 1 1 1 1 1 1 0 0 0 0 0 0 0 0 1 1 1 6 4 2 1 2 2 4 2 2 5 а в д , е н р о т _

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

Чтобы определить код для каждого из символов, входящих в сообщение, мы должны пройти путь от листа дерева, соответствующего этому символу, до корня дерева, накапливая биты при перемещении по ветвям дерева. Полученная таким образом последовательность битов является кодом данного символа, записанным в обратном порядке. а в д , е н р о т _ 00 010 0110 0111 1000 1001 101 1100 1101 111 6 4 2 1 2 2 4 2 2 5

ПОДСЧИТАЕМ, СКОЛЬКО ДВОИЧНЫХ СИМВОЛОВ ОКАЖЕТСЯ В СООБЩЕНИИ «НА_ ДВОРЕ_ ТРАВА,_ НА_ ТРАВЕ_ ДРОВА» ДЛЯ
11 слайд

ПОДСЧИТАЕМ, СКОЛЬКО ДВОИЧНЫХ СИМВОЛОВ ОКАЖЕТСЯ В СООБЩЕНИИ «НА_ ДВОРЕ_ ТРАВА,_ НА_ ТРАВЕ_ ДРОВА» ДЛЯ ЭТОГО НАДО НАЙТИ ПРОИЗВЕДЕНИЕ ЧИСЛА СИМВОЛОВ В КОДЕ КАЖДОЙ БУКВЫ НА КОЛИЧЕСТВО РАЗ, КОТОРОЕ ЭТА БУКВА ВСТРЕЧАЕТСЯ В СООБЩЕНИИ, А ЗАТЕМ ПОЛУЧЕННЫЕ ПРОИЗВЕДЕНИЯ СЛОЖИТЬ. ПОЛУЧАЕМ: 2*6+ 3*4+ 4*2+ 4*1+ 4*2+ 4*2 +3*4 +4*2 +4*2 +3*5 = 95

ПОСКОЛЬКУ В СООБЩЕНИИ ИСПОЛЬЗУЕТСЯ 10 РАЗЛИЧНЫХ СИМВОЛОВ, ДЛЯ ИХ КОДИРОВАНИЯ ТРЕБУЕТСЯ КАК МИНИМУМ Ч
12 слайд

ПОСКОЛЬКУ В СООБЩЕНИИ ИСПОЛЬЗУЕТСЯ 10 РАЗЛИЧНЫХ СИМВОЛОВ, ДЛЯ ИХ КОДИРОВАНИЯ ТРЕБУЕТСЯ КАК МИНИМУМ ЧЕТЫРЕХБИТОВЫЕ ЦЕПОЧКИ, ПОЭТОМУ ПОСЛЕ КОДИРОВАНИЯ ДАННОГО СООБЩЕНИЯ ПОЛУЧИТСЯ ЦЕПОЧКА ОБЪЕМОМ 120 БИТ. КОЭФФИЦИЕНТ СЖАТИЯ ЭТО ОТНОШЕНИЕ ОБЪЕМА ИСХОДНОГО СООБЩЕНИЯ К ОБЪЕМУ СЖАТОГО. В НАШЕМ СЛУЧАЕ ЭТО ОТНОШЕНИЕ РАВНО 120/95 = 120/95 = 1,26 .

НА САМОМ ДЕЛЕ ДАННОЕ СООБЩЕНИЕ В ПАМЯТИ КОМПЬЮТЕРА ЗАКОДИРОВАНО С ПОМОЩЬЮ ASCII, ПОЭТОМУ НА КАЖДЫЙ С
13 слайд

НА САМОМ ДЕЛЕ ДАННОЕ СООБЩЕНИЕ В ПАМЯТИ КОМПЬЮТЕРА ЗАКОДИРОВАНО С ПОМОЩЬЮ ASCII, ПОЭТОМУ НА КАЖДЫЙ СИМВОЛ ОТВЕДЕНО 8 БИТ. ТЕМ САМЫМ, ОБЪЕМ ИСХОДНОГО СООБЩЕНИЯ 240 БИТ, А КОЭФФИЦИЕНТ СЖАТИЯ СОСТАВЛЯЕТ 240/95 = 2,53. ИЗ ЭТОГО ВИДНО, КАКОЙ ВЫИГРЫШ МЫ ПОЛУЧИЛИ, ЕСЛИ ЭТО СООБЩЕНИЕ НУЖНО БЫЛО БЫ ПЕРЕДАТЬ ПО КАНАЛУ СВЯЗИ ИЛИ СОХРАНИТЬ НА КАКОМ-ЛИБО НОСИТЕЛЕ.

ДЛЯ ДЕКОДИРОВНИЯ СЖАТОГО СООБЩЕНИЯ ВМЕСТЕ С НИМ ОБЫЧНО ПЕРЕСЫЛАЮТ НЕ КОДЫ ИСХОДНЫХ СИМВОЛОВ (Т.Е. ПЕ
14 слайд

ДЛЯ ДЕКОДИРОВНИЯ СЖАТОГО СООБЩЕНИЯ ВМЕСТЕ С НИМ ОБЫЧНО ПЕРЕСЫЛАЮТ НЕ КОДЫ ИСХОДНЫХ СИМВОЛОВ (Т.Е. ПЕРВЫЕ ДВЕ СТРОКИ), А САМ ОРГРАФ ХАФФМАНА (БЕЗ УКАЗАНИЯ ВЕСА КОРНЯ И РАЗМЕТКИ НА ДУГАХ, ИБО ОНА СТАНДАРТНА: ДУГА, ИДУЩАЯ ВЛЕВО, РАЗМЕЧАЕТСЯ -0, А ИДУЩАЯ ВПРАВО -1). НА ЭТОМ, ОКАЗЫВАЕТСЯ, ТО ЖЕ МОЖНО СЭКОНОМИТЬ. МАТЕМАТИКИ ДОКАЗАЛИ, ЧТО СРЕДИ АЛГОРИТМОВ КОДИРУЮЩИХ КАЖДЫЙ СИМВОЛ ПО ОТДЕЛЬНОСТИ И ЦЕЛЫМ КОЛИЧЕСТВОМ БИТ АЛГОРИТМ ХАФФМАНА ОБЕСПЕЧИВАЕТ НАИЛУЧШЕЕ СЖАТИЕ.

Используемая литература: А.Г. Гейн. Математические основы информатики. Педагогический университет «П
15 слайд

Используемая литература: А.Г. Гейн. Математические основы информатики. Педагогический университет «Первое сентября», 2008г. http://edu.1september.ru/courses/07/008/01.pdf

Комментарии (0) к презентации "Алгоритм построения орграфа Хаффмана (алгоритм сжатия)"