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

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

2 Давид Хаффман ( ) Давид начал свою научную карьеру студентом в Массачусетсом технологическом институте (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 РАЗЛИЧНЫХ СИМВОЛОВ, ДЛЯ ИХ КОДИРОВАНИЯ ТРЕБУЕТСЯ КАК МИНИМУМ ЧЕТЫРЕХБИТОВЫЕ ЦЕПОЧКИ. ПОЭТОМУ ПОСЛЕ КОДИРОВАНИЯ ДАННОГО СООБЩЕНИЯ ПОЛУЧИТСЯ ЦЕПОЧКА ОБЪЕМОМ 120 БИТ. КОЭФФИЦИЕНТ СЖАТИЯ ЭТО ОТНОШЕНИЕ ОБЪЕМА ИСХОДНОГО СООБЩЕНИЯ К ОБЪЕМУ СЖАТОГО. В НАШЕМ СЛУЧАЕ ЭТО ОТНОШЕНИЕ РАВНО 120/95 = 120/95 = 1,26.

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

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

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