Алгоритм Хаффмана. Сравнение алгоритмов сжатия. Использование архиватора

3-4 урок, 11 класс – практика

Учитель: Брух Т.В.

Дата: __________

Тема урока: «Алгоритм Хаффмана. Сравнение алгоритмов сжатия. Использование архиватора».

Цель урока: условие рассмотрения алгоритма сжатия на основе построения орграфа Хаффмана.

Задачи:

Образовательная:

1. Познакомить учащихся с понятиями алгоритм сжатия, дерево, дуга, орграф, орграф Хаффмана.

2. Рассмотреть пример построения орграфа Хаффмана, и чем он хорош при нахождении коэффициента сжатия.

3. Организовать практическую работу по нахождению частотности букв русского алфавита в тексте, освоению алгоритма построения дерева Хаффмана.

Развивающая:

1. Развивать у учащихся познавательный интерес к курсу «Математические основы информатики».

2. Развивать алгоритмическое мышление, память.

3. Развитие практических навыков.

Воспитательная:

1. Способствовать воспитанию у учащихся внимательности.

2. Воспитывать аккуратность ведения записей в тетради.

3. Привитие навыка самостоятельности в работе.

4. Воспитание трудолюбия и чувства уважения к науке.

Х од урока:

1. Организация начала урока.

Приветствие учителя.

1. Проверка домашнего задания

Теория + в рабочей тетради заполнить таблицу

1. Изучение нового материала

Построить код Хаффмана для фразы «НА_ ДВОРЕ_ ТРАВА,_ НА_ ТРАВЕ_ ДРОВА». Определить коэффициент сжатия для данной фразы и сравнить его, если каждый символ кодируется в ASCII.

Сжатие информации - проблема, имеющая достаточно давнюю историю, гораздо более давнюю, нежели история развития вычислительной техники, которая (история) обычно шла параллельно с историей развития проблемы кодирования и шифровки информации.
Все алгоритмы сжатия оперируют входным потоком информации, минимальной единицей которой является бит, а максимальной - несколько бит, байт или несколько байт.
Целью процесса сжатия, как правило, есть получение более компактного выходного потока информационных единиц из некоторого изначально некомпактного входного потока при помощи некоторого их преобразования.
Построение алгоритма Хаффмана.

Коды или Алгоритм Хаффмана (Huffman codes) — широко распространенный и очень эффективный метод сжатия данных, который, в зависимости от характеристик этих данных, обычно позволяет сэкономить от 20% до 90% объема.
Рассматриваются данные, представляющие собой последовательность символов. В алгоритме Хаффмана используется таблица, содержащая частоты появления тех или иных символов.

НА_ ДВОРЕ_ ТРАВА,_ НА_ ТРАВЕ_ ДРОВА

При обычном кодировании мы каждый символ записываем в фиксированном количестве бит, например каждый символ в одном байте, или в двух.

Однако, т. к. некоторые символы встречаются чаще, а некоторые реже − можно записать часто встречающиеся символы в небольшом количестве бит, а для редко встречающихся символов использовать более длинные коды. Тогда суммарная длина закодированного текста может стать меньше.

Алгоритм построения дерева (орграфа Хаффмана) прост.

• Символы входного алфавита образуют список свободных узлов. Каждый лист имеет вес, равный количеству вхождений символа в сжимаемое сообщение.
• Выбираются два свободных узла дерева с наименьшими весами.
• Создается их родитель с весом, равным их суммарному весу.
• Родитель добавляется в список свободных узлов, а двое его детей удаляются из этого списка.
• Одной дуге, выходящей из родителя, ставится в соответствие бит 1, другой - бит 0.
• Шаги, начиная со второго, повторяются до тех пор, пока в списке свободных узлов не останется только один свободный узел. Он и будет считаться корнем дерева.
Допустим, у нас есть следующая таблица частот:

На первом шаге из листьев дерева выбираются два с наименьшими весами - д и , (запятая)

3

0 1

Они присоединяются к новому узлу-родителю, вес которого устанавливается 2+1 = 3.

Затем узлы д и , (запятая) удаляются из списка свободных. Узел д соответствует ветви 0 родителя, узел ,(запятая) - ветви 1.

На следующем шаге то же происходит с узлами е и н, так как теперь эта пара имеет самый меньший вес в дереве.

3 4

0 1 0 1

Создается новый узел с весом 4, а узлы е и н удаляются из списка свободных.

3 4 4

0 1 0 1 0 1

Создается точно такой узел с весом 4, а узлы о и т удаляются из списка свободных. Создается новый узел с весом 7, а узел в удаляется из списка свободных.

7

1

4 4

0 0 1 0 1 0 1

Создается новый узел с весом 8, а узел р удаляется из списка свободных.

7 8

1 0

4 1 4

0 0 1 0 1 0 1

Создается новый узел с весом 9, а узел _ (пробел) удаляется из списка свободных.

7 8 9

1 0 0

1 1

0 0 1 0 1 0 1

Создается очередной новый узел с весом 13, а узел а удаляется из списка свободных.

13

1

1 8 9

0 0 0 0

0 1 0 1 1 0 1 1

На следующем шаге "наилегчайшей" парой оказываются узлы 8 и 9. Для них еще раз создается родитель, теперь уже с весом 17.

13 17

1 0 1

1 0 1 0 1

0 0 0 1 0 1 0 1

Узел 8 соответствует ветви 0 родителя, 9 - ветви 1. На последнем шаге в списке свободных осталось только два узла - это 13 и узел 17. В очередной раз создается родитель с весом 30 и бывшие свободными узлы присоединяются к разным его ветвям.
Поскольку свободным остался только один узел, то алгоритм построения дерева кодирования Хаффмана завершается.

Алгоритм Хаффмана представлен на рисунке

30

1 0 1

1 0 1 0 1

0 0 0 1 0 1 0 1

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

Нахождение коэффициента сжатия.

Подсчитаем, сколько двоичных символов окажется в сообщении

«НА_ ДВОРЕ_ ТРАВА,_ НА_ ТРАВЕ_ ДРОВА»

Для этого надо найти произведение числа символов в коде каждой буквы на количество раз, которое эта буква встречается в сообщении, а затем полученные произведения сложить.

Получаем: 2*6+ 3*4+ 4*2+ 4*1+ 4*2+ 4*2 +3*4 +4*2 +4*2 +3*5 = 95

Узел 8 соответствует ветви 0 родителя, 9 - ветви 1. На последнем шаге в списке свободных осталось только два узла - это 13 и узел 17. В очередной раз создается родитель с весом 30 и бывшие свободными узлы присоединяются к разным его ветвям.

На самом деле данное сообщение в памяти компьютера закодировано с помощью ASCII, поэтому на каждый символ отведено 8 бит, тем самым, объем исходного сообщения 240 бит, а коэффициент сжатия составляет 240/95 = 2,53.

IV. Закрепление знаний. Практическая работа.

1) построить код Хаффмана для фразы «ОТ ТОПОТА КОПЫТ ПЫЛЬ ПО ПОЛЮ ЛЕТИТ».

2) определить коэффициент сжатия для данной фразы.

«ОТ ТОПОТА КОПЫТ ПЫЛЬ ПО ПОЛЮ ЛЕТИТ».

б) Определите коэффициент сжатия для данной фразы, если каждый символ кодируется в ASCII.

1 1 2 5 6 3 1 1 1 1 5 6

5*1+5*1+4*2+3*5+2*6+3*3+4*1+4*1+5*1+5*1+4*5+3*6=5+5+8+15+12+9+4+4+5+5+20+18=10+20+15+17+48=30+32+48=62+48+110

33*8=264

264/110=2,4 – коэффициент сжатия

1. Подведение итогов урока.

Из этого видно, какой выигрыш мы получили, если это сообщение нужно было бы передать по каналу связи или сохранить на каком-либо носителе.

Для декодирования сжатого сообщения вместе с ним обычно пересылают не коды исходных символов (т.е. первые две строки), а сам орграф Хаффмана (без указания веса корня и разметки на дугах, ибо она стандартна: дуга, идущая влево, размечается 0, а идущая вправо -1).

На этом, оказывается, то же можно сэкономить.

Математики доказали, что среди алгоритмов кодирующих каждый символ по отдельности и целым количеством бит алгоритм Хаффмана обеспечивает наилучшее сжатие.

VI. Домашнее задание:

1) конспект урока;

2)построить код Хаффмана для фразы «ШЛА САША ПО ШОССЕ И СОСАЛА СУШКУ».

3)определить коэффициент сжатия для данной фразы.