Что такое findslide.org?

FindSlide.org - это сайт презентаций, докладов, шаблонов в формате PowerPoint.


Для правообладателей

Обратная связь

Email: Нажмите что бы посмотреть 

Яндекс.Метрика

Презентация на тему Алгоритмы сжатия. Алгоритм построения орграфа Хаффмана

Давид Хаффман (1925-1999) Давид начал свою научную карьеру студентом в Массачусетсом технологическом институте (MIT), где построил свои коды в начале пятидесятых годов прошлого века.
Алгоритм построения орграфа хаффмана (алгоритм сжатия)Учитель информатики:Константинова Елена ИвановнаМуниципальное образовательное учреждение Раменская средняя общеобразовательная школа №8 Давид Хаффман (1925-1999)    Давид начал свою научную карьеру Закодируем предложение «НА_ДВОРЕ_ТРАВА,_НА_ТРАВЕ_ДРОВА»  Вначале нужно подсчитать количество вхождений каждого символа в тексте.Создаем первый узел Создаем еще один узелСоздаем еще один узел Создаем еще один узелСоздаем еще один узел Создаем еще один узел Создаем еще один узел Создаем еще один узел Создаем еще один узел ТЕПЕРЬ ОПРЕДЕЛЯЕМ КОДЫ СИМВОЛОВ, ДВИГАЯСЬ ОТ КОРНЯ К СООТВЕТСТВУЮЩЕМУ ПОДСЧИТАЕМ, СКОЛЬКО ДВОИЧНЫХ СИМВОЛОВ ОКАЖЕТСЯ В СООБЩЕНИИ  «НА_ ПОСКОЛЬКУ В СООБЩЕНИИ ИСПОЛЬЗУЕТСЯ 10 РАЗЛИЧНЫХ СИМВОЛОВ, ДЛЯ ИХ НА САМОМ ДЕЛЕ ДАННОЕ СООБЩЕНИЕ В ПАМЯТИ ДЛЯ ДЕКОДИРОВНИЯ СЖАТОГО СООБЩЕНИЯ ВМЕСТЕ С НИМ ОБЫЧНО ПЕРЕСЫЛАЮТ Используемая литература:А.Г. Гейн. Математические основы информатики.Педагогический университет «Первое сентября», 2008г.http://edu.1september.ru/courses/07/008/01.pdf
Слайды презентации

Слайд 2 Давид Хаффман (1925-1999)


Давид

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

начал свою научную карьеру студентом в Массачусетсом технологическом институте

(MIT), где построил свои коды в начале пятидесятых годов прошлого века.


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

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

символа в тексте.

Создаем первый узел


Слайд 4 Создаем еще один узел
Создаем еще один узел

Создаем еще один узелСоздаем еще один узел

Слайд 5
Создаем еще один узел
Создаем еще один узел

Создаем еще один узелСоздаем еще один узел

Слайд 6 Создаем еще один узел

Создаем еще один узел

Слайд 7 Создаем еще один узел

Создаем еще один узел

Слайд 8 Создаем еще один узел

Создаем еще один узел

Слайд 9 Создаем еще один узел

Создаем еще один узел

Слайд 10 ТЕПЕРЬ ОПРЕДЕЛЯЕМ КОДЫ СИМВОЛОВ, ДВИГАЯСЬ

ТЕПЕРЬ ОПРЕДЕЛЯЕМ КОДЫ СИМВОЛОВ, ДВИГАЯСЬ ОТ КОРНЯ К СООТВЕТСТВУЮЩЕМУ

ОТ КОРНЯ К СООТВЕТСТВУЮЩЕМУ СИМВОЛУ.
В

ТРЕТЬЕЙ СТРОКЕ ТАБЛИЦЫ УКАЗАНЫ СКОЛЬКО РАЗ ВСТРЕЧАЕТСЯ ДЛИННАЯ БУКВА В СООБЩЕНИИ.

Слайд 11 ПОДСЧИТАЕМ, СКОЛЬКО ДВОИЧНЫХ СИМВОЛОВ ОКАЖЕТСЯ

ПОДСЧИТАЕМ, СКОЛЬКО ДВОИЧНЫХ СИМВОЛОВ ОКАЖЕТСЯ В СООБЩЕНИИ «НА_ ДВОРЕ_

В СООБЩЕНИИ
«НА_ ДВОРЕ_ ТРАВА,_ НА_ ТРАВЕ_ ДРОВА»

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


Слайд 12 ПОСКОЛЬКУ В СООБЩЕНИИ ИСПОЛЬЗУЕТСЯ 10

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

РАЗЛИЧНЫХ СИМВОЛОВ, ДЛЯ ИХ КОДИРОВАНИЯ ТРЕБУЕТСЯ КАК МИНИМУМ ЧЕТЫРЕХБИТОВЫЕ

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

Слайд 13
НА САМОМ ДЕЛЕ

НА САМОМ ДЕЛЕ ДАННОЕ СООБЩЕНИЕ В ПАМЯТИ КОМПЬЮТЕРА

ДАННОЕ СООБЩЕНИЕ В ПАМЯТИ КОМПЬЮТЕРА ЗАКОДИРОВАНО С ПОМОЩЬЮ ASCII,

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

ИЗ ЭТОГО ВИДНО, КАКОЙ ВЫИГРЫШ МЫ ПОЛУЧИЛИ, ЕСЛИ ЭТО СООБЩЕНИЕ НУЖНО БЫЛО БЫ ПЕРЕДАТЬ ПО КАНАЛУ СВЯЗИ ИЛИ СОХРАНИТЬ НА КАКОМ-ЛИБО НОСИТЕЛЕ.


Слайд 14 ДЛЯ ДЕКОДИРОВНИЯ СЖАТОГО СООБЩЕНИЯ ВМЕСТЕ

ДЛЯ ДЕКОДИРОВНИЯ СЖАТОГО СООБЩЕНИЯ ВМЕСТЕ С НИМ ОБЫЧНО ПЕРЕСЫЛАЮТ

С НИМ ОБЫЧНО ПЕРЕСЫЛАЮТ НЕ КОДЫ ИСХОДНЫХ СИМВОЛОВ (Т.Е.

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

  • Имя файла: algoritmy-szhatiya-algoritm-postroeniya-orgrafa-haffmana.pptx
  • Количество просмотров: 113
  • Количество скачиваний: 0