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

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

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

Задачи:

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

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, а узел р  удаляется из списка свободных.