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

Алгоритм Хаффмана — алгоритм оптимального префиксного кодирования алфавита с минимальной избыточностью.

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

Например, код, состоящий из слов 0, 10 и 11, является префиксным, и сообщение 01001101110 можно разбить на слова единственным образом: 0 10 0 11 0 11 10

Этот метод кодирования состоит из двух основных этапов:

-Построение оптимального кодового дерева;

-Построение отображения код-символ на основе построенного дерева.

Пример: кол_около_колокола

а -111 ; _ -110; л -10; к -01; о -00

0010. 0101. 1000. 0100. 1000. 1100. 1001. 0000. 1001. 0111

Ставим 0 в начале, чтобы на конце было 4 цифры.

2.5.8.4.12.9.0.9.7.

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

Код Хаффмана восстанавливается даже если не сообщается длина кода каждого переданного символа.

Схема восстановления: маркер устанавливается в вершину дерева; сжимаемый массив читается слитно, если читаемый бит 0, то перемещаемся из вершины по верхнему ребру, если 1, то по нижнему ребру;

Читаем следующий бит перемещаемся до тех пор пока маркер не попадет а конечный узел дерева; дальше символ записывается в восстанавливающий массив и маркер устанавливается в вершину дерева и повторяет цикл.