Хаффмановское кодирование появилось в 1952 году.Главное его предназначение заключалось в упаковке текстовых файлов - для другого он мало приспособлен. Имеет довольно простую реализацию, так что его вполне удобно использовать в устройствах имеющих слабые микропроцессоры.
Частота появления символов в обычных текстах различна и поэтому нерационально для кодирования каждого бита тратить одно и тоже число бит (обычно 8), лучше будет потратить на менее часто встречаемые символы больше, но потом это окупится тем, что на более встречаемые символы тратится меньше бит. Идея алгоритма кодирования:зная вероятность вхождения символов, можно описать процедуру построения кодов переменной. Символу, имеющему большую вероятность, присваиваются более короткие коды.
Рассмотрим следующий пример:
исходный поток АБАБАБАВАБВГ = 12 байт
выходной поток Пусть символы кодируются как
А=1
Б=01
В=001
Г=000
тогда будет 101101101101001101001000 = 25 бит = 3 байт + 1 бит
Классический алгоритм Хаффмана имеет на входе таблицу частот появления символов и, зная ее основание, строится так называемое дерево Хаффмана.
Граф - это совокупность множества углов и соединяющих их дуг.Направленные графы могут быть циклическими.
Дерево - граф, обладающий следующими свойствами:
Лист дерева - это узел, из которого не выходит ни одной дуги. Два листа, имеющие общий узел, называются родственными.
Двоичное дерево - дерево, у которого из каждого угла выходит только две дуги.
H- дерево - двоичное дерево кодирования, у которого каждый узел имеет вес, причем вес родителя равен сумме весов детей.
Входной алфавит - совокупность всех символов.
Алгоритм Хаффмана:
Этапы алгоритма Хаффмана:
1. Присвоение листьям дерева частоты вращения.
2. Выбираются два свободных листа с наименьшими весами. Создается родительский узел, равный сумме весов листьев.
3. Полученный родительский узел добавляется в список свободных листов, а соответствующие листья удаляются.
4. Одной дуге выходящей ставится в соответствие 1, а другой 0.
5. Шаги с первого по четвертый повторяются до тех пор, пока не останется свободный узел - корень дерева.
Классический алгоритм Хаффмана имеет один недостаток: для восстановления содержимого сжатого сообщения декодер должен знать таблицу частот появления символов, которая должна высылаться впереди данных.