PPt4Web Хостинг презентаций

Главная / Информатика / Алгоритм построения орграфа Хаффмана (алгоритм сжатия)
X Код для использования на сайте:

Скопируйте этот код и вставьте его на свой сайт

X

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

После чего скачивание начнётся автоматически!

Кнопки:

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


Скачать эту презентацию

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


Скачать эту презентацию



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

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

№ слайда 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,
Описание слайда:

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

№ слайда 14 ДЛЯ ДЕКОДИРОВНИЯ СЖАТОГО СООБЩЕНИЯ ВМЕСТЕ С НИМ ОБЫЧНО ПЕРЕСЫЛАЮТ НЕ КОДЫ ИСХОДН
Описание слайда:

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

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

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

Скачать эту презентацию


Презентации по предмету
Презентации из категории
Лучшее на fresher.ru