X

Код презентации скопируйте его

Ширина px

Вы можете изменить размер презентации, указав свою ширину плеера!

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

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

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

Скачать эту презентацию
Cлайд 1
Алгоритм построения орграфа Хаффмана (алгоритм сжатия) Учитель информатики: К... Алгоритм построения орграфа Хаффмана (алгоритм сжатия) Учитель информатики: Константинова Елена Ивановна Муниципальное образовательное учреждение Раменская средняя общеобразовательная школа №8
Cлайд 2
Давид Хаффман (1925-1999) Давид начал свою научную карьеру студентом в Массач... Давид Хаффман (1925-1999) Давид начал свою научную карьеру студентом в Массачусетсом технологическом институте (MIT), где построил свои коды в начале пятидесятых годов прошлого века.
Cлайд 3
Закодируем предложение «НА_ДВОРЕ_ТРАВА,_НА_ТРАВЕ_ДРОВА» Вначале нужно подсчит... Закодируем предложение «НА_ДВОРЕ_ТРАВА,_НА_ТРАВЕ_ДРОВА» Вначале нужно подсчитать количество вхождений каждого символа в тексте. Создаем первый узел 6 4 2 1 2 2 4 2 2 5 а в д , е н р о т _ 6 4 2 1 2 2 4 2 2 5 а в д , е н р о т _
Cлайд 4
Создаем еще один узел Создаем еще один узел 6 4 2 1 2 2 4 2 2 5 а в д , е н р... Создаем еще один узел Создаем еще один узел 6 4 2 1 2 2 4 2 2 5 а в д , е н р о т _ 6 4 2 1 2 2 4 2 2 5 а в д , е н р о т _
Cлайд 5
Создаем еще один узел Создаем еще один узел 6 4 2 1 2 2 4 2 2 5 а в д , е н р... Создаем еще один узел Создаем еще один узел 6 4 2 1 2 2 4 2 2 5 а в д , е н р о т _ 6 4 2 1 2 2 4 2 2 5 а в д , е н р о т _
Cлайд 6
Создаем еще один узел 6 4 2 1 2 2 4 2 2 5 а в д , е н р о т _ Создаем еще один узел 6 4 2 1 2 2 4 2 2 5 а в д , е н р о т _
Cлайд 7
Создаем еще один узел 6 4 2 1 2 2 4 2 2 5 а в д , е н р о т _ Создаем еще один узел 6 4 2 1 2 2 4 2 2 5 а в д , е н р о т _
Cлайд 8
Создаем еще один узел 6 4 2 1 2 2 4 2 2 5 а в д , е н р о т _ Создаем еще один узел 6 4 2 1 2 2 4 2 2 5 а в д , е н р о т _
Cлайд 9
Создаем еще один узел 6 4 2 1 2 2 4 2 2 5 а в д , е н р о т _ Создаем еще один узел 6 4 2 1 2 2 4 2 2 5 а в д , е н р о т _
Cлайд 10
Чтобы определить код для каждого из символов, входящих в сообщение, мы должны... Чтобы определить код для каждого из символов, входящих в сообщение, мы должны пройти путь от листа дерева, соответствующего этому символу, до корня дерева, накапливая биты при перемещении по ветвям дерева. Полученная таким образом последовательность битов является кодом данного символа, записанным в обратном порядке. а в д , е н р о т _ 00 010 0110 0111 1000 1001 101 1100 1101 111 6 4 2 1 2 2 4 2 2 5
Cлайд 11
ПОДСЧИТАЕМ, СКОЛЬКО ДВОИЧНЫХ СИМВОЛОВ ОКАЖЕТСЯ В СООБЩЕНИИ «НА_ ДВОРЕ_ ТРАВА,... ПОДСЧИТАЕМ, СКОЛЬКО ДВОИЧНЫХ СИМВОЛОВ ОКАЖЕТСЯ В СООБЩЕНИИ «НА_ ДВОРЕ_ ТРАВА,_ НА_ ТРАВЕ_ ДРОВА» ДЛЯ ЭТОГО НАДО НАЙТИ ПРОИЗВЕДЕНИЕ ЧИСЛА СИМВОЛОВ В КОДЕ КАЖДОЙ БУКВЫ НА КОЛИЧЕСТВО РАЗ, КОТОРОЕ ЭТА БУКВА ВСТРЕЧАЕТСЯ В СООБЩЕНИИ, А ЗАТЕМ ПОЛУЧЕННЫЕ ПРОИЗВЕДЕНИЯ СЛОЖИТЬ. ПОЛУЧАЕМ: 2*6+ 3*4+ 4*2+ 4*1+ 4*2+ 4*2 +3*4 +4*2 +4*2 +3*5 = 95
Cлайд 12
ПОСКОЛЬКУ В СООБЩЕНИИ ИСПОЛЬЗУЕТСЯ 10 РАЗЛИЧНЫХ СИМВОЛОВ, ДЛЯ ИХ КОДИРОВАНИЯ ... ПОСКОЛЬКУ В СООБЩЕНИИ ИСПОЛЬЗУЕТСЯ 10 РАЗЛИЧНЫХ СИМВОЛОВ, ДЛЯ ИХ КОДИРОВАНИЯ ТРЕБУЕТСЯ КАК МИНИМУМ ЧЕТЫРЕХБИТОВЫЕ ЦЕПОЧКИ, ПОЭТОМУ ПОСЛЕ КОДИРОВАНИЯ ДАННОГО СООБЩЕНИЯ ПОЛУЧИТСЯ ЦЕПОЧКА ОБЪЕМОМ 120 БИТ. КОЭФФИЦИЕНТ СЖАТИЯ ЭТО ОТНОШЕНИЕ ОБЪЕМА ИСХОДНОГО СООБЩЕНИЯ К ОБЪЕМУ СЖАТОГО. В НАШЕМ СЛУЧАЕ ЭТО ОТНОШЕНИЕ РАВНО 120/95 = 120/95 = 1,26 .
Cлайд 13
НА САМОМ ДЕЛЕ ДАННОЕ СООБЩЕНИЕ В ПАМЯТИ КОМПЬЮТЕРА ЗАКОДИРОВАНО С ПОМОЩЬЮ ASC... НА САМОМ ДЕЛЕ ДАННОЕ СООБЩЕНИЕ В ПАМЯТИ КОМПЬЮТЕРА ЗАКОДИРОВАНО С ПОМОЩЬЮ ASCII, ПОЭТОМУ НА КАЖДЫЙ СИМВОЛ ОТВЕДЕНО 8 БИТ. ТЕМ САМЫМ, ОБЪЕМ ИСХОДНОГО СООБЩЕНИЯ 240 БИТ, А КОЭФФИЦИЕНТ СЖАТИЯ СОСТАВЛЯЕТ 240/95 = 2,53. ИЗ ЭТОГО ВИДНО, КАКОЙ ВЫИГРЫШ МЫ ПОЛУЧИЛИ, ЕСЛИ ЭТО СООБЩЕНИЕ НУЖНО БЫЛО БЫ ПЕРЕДАТЬ ПО КАНАЛУ СВЯЗИ ИЛИ СОХРАНИТЬ НА КАКОМ-ЛИБО НОСИТЕЛЕ.
Cлайд 14
ДЛЯ ДЕКОДИРОВНИЯ СЖАТОГО СООБЩЕНИЯ ВМЕСТЕ С НИМ ОБЫЧНО ПЕРЕСЫЛАЮТ НЕ КОДЫ ИСХ... ДЛЯ ДЕКОДИРОВНИЯ СЖАТОГО СООБЩЕНИЯ ВМЕСТЕ С НИМ ОБЫЧНО ПЕРЕСЫЛАЮТ НЕ КОДЫ ИСХОДНЫХ СИМВОЛОВ (Т.Е. ПЕРВЫЕ ДВЕ СТРОКИ), А САМ ОРГРАФ ХАФФМАНА (БЕЗ УКАЗАНИЯ ВЕСА КОРНЯ И РАЗМЕТКИ НА ДУГАХ, ИБО ОНА СТАНДАРТНА: ДУГА, ИДУЩАЯ ВЛЕВО, РАЗМЕЧАЕТСЯ -0, А ИДУЩАЯ ВПРАВО -1). НА ЭТОМ, ОКАЗЫВАЕТСЯ, ТО ЖЕ МОЖНО СЭКОНОМИТЬ. МАТЕМАТИКИ ДОКАЗАЛИ, ЧТО СРЕДИ АЛГОРИТМОВ КОДИРУЮЩИХ КАЖДЫЙ СИМВОЛ ПО ОТДЕЛЬНОСТИ И ЦЕЛЫМ КОЛИЧЕСТВОМ БИТ АЛГОРИТМ ХАФФМАНА ОБЕСПЕЧИВАЕТ НАИЛУЧШЕЕ СЖАТИЕ.
Cлайд 15
Используемая литература: А.Г. Гейн. Математические основы информатики. Педаго... Используемая литература: А.Г. Гейн. Математические основы информатики. Педагогический университет «Первое сентября», 2008г. http://edu.1september.ru/courses/07/008/01.pdf
Скачать эту презентацию
Наверх