Метод сжатия Хаффмана

Хаффмановское кодирование появилось в 1952 году.Главное его предназначение заключалось в упаковке текстовых файлов - для другого он мало приспособлен. Имеет довольно простую реализацию, так что его вполне удобно использовать в устройствах имеющих слабые микропроцессоры.

Частота появления символов в обычных текстах различна и поэтому нерационально для кодирования каждого бита тратить одно и тоже число бит (обычно 8), лучше будет потратить на менее часто встречаемые символы больше, но потом это окупится тем, что на более встречаемые символы тратится меньше бит. Идея алгоритма кодирования:зная вероятность вхождения символов, можно описать процедуру построения кодов переменной. Символу, имеющему большую вероятность, присваиваются более короткие коды.

Рассмотрим следующий пример:
   исходный поток     АБАБАБАВАБВГ     = 12 байт
   выходной поток     Пусть символы кодируются как
    А=1
    Б=01
    В=001
    Г=000
тогда будет 101101101101001101001000     = 25 бит = 3 байт + 1 бит

Классический алгоритм Хаффмана имеет на входе таблицу частот появления символов и, зная ее основание, строится так называемое дерево Хаффмана.

Граф - это совокупность множества углов и соединяющих их дуг.Направленные графы могут быть циклическими.

Дерево - граф, обладающий следующими свойствами:

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

Лист дерева - это узел, из которого не выходит ни одной дуги. Два листа, имеющие общий узел, называются родственными.

Двоичное дерево - дерево, у которого из каждого угла выходит только две дуги.

H- дерево - двоичное дерево кодирования, у которого каждый узел имеет вес, причем вес родителя равен сумме весов детей.

Входной алфавит - совокупность всех символов.

Алгоритм Хаффмана:

• символы входного алфавита образуют список свободных углов
• каждый лист имеет вес, который равен либо вероятности, либо количеству вхождений символа в сжимаемое сообщение

Этапы алгоритма Хаффмана:

1. Присвоение листьям дерева частоты вращения.
2. Выбираются два свободных листа с наименьшими весами. Создается родительский узел, равный сумме весов листьев.
3. Полученный родительский узел добавляется в список свободных листов, а соответствующие листья удаляются.
4. Одной дуге выходящей ставится в соответствие 1, а другой 0.
5. Шаги с первого по четвертый повторяются до тех пор, пока не останется свободный узел - корень дерева.

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