Сжатие и распаковка информации по методу Хаффмана

Метод Хаффмана предусматривает генерацию бинарных последовательностей на основе дерева алфавита, которое составляют попарные объединения виртуальных символов, образующие узлы дерева. Причем две ветви, образующие узел, обозначаются соответственно 1 и 0. Созданный узел образует виртуальный символ алфавита с вероятностью появления, равной сумме вероятностей, образующих узел, в дальнейшем этот узел может участвовать в создании нового. Объединение символов начинается с двух символов с наименьшими вероятностями. Структурно дерево имеет вид иерархию. Последний узел называется корнем. Стремиться нужно к тому, чтобы на каждой ветви узлы создавали символы с примерно одинаковыми вероятностями. Бинарный код каждого символа исходного алфавита создают обозначения ветвей дерева при их обходе от корня дерева к данному символу.

Прямое преобразование заключается в замене каждого символа соответствующим бинарным кодом.

Обратное преобразование наоборот, т.е. компрессор и декомпрессор должны пользоваться одинаковой таблицей код-символ и наоборот. Т. е. процедура сжатия и распаковки такая же, как и у метода Шеннона-Фано

	Сортировка
	=0,3 =0,54
	=0,2 корень дерева дерева
	=0,14 =0,46
	=0,26
	узел (а10,а8) – виртуальный символ виртуальный символ =0,12
	=0,07

Формально можно выделить 4 уровня иерархии.

Сформированные бинарные коды должны отвечать следующим условиям:

1) все коды должны быть уникальными;

2) должно выполняться свойство префикса: ни один код меньшей длины не может быть началом кода большей длины.

Могут существовать различные варианты объединения символов в пары. Наилучший вариант – когда ему соответствует минимальное значение интегрального коэффициента R: [bit], l _i – длина бинарного кода для i-того символа.

Поиск по сайту: