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

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

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

Основная часть.

1.     Построение алгоритма Хаффмана.

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

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

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

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

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

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

Допустим, у нас есть следующая таблица частот:

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

                                                     3

                                              0            1