Методичка (сети)

Кодирование Хаффмана

Процесс кодирования Хаффмана выполняется следующим образом. Символы сообщения, которые нужно закодировать, перечисляются в порядке убывания вероятности (Т.е. символы с самой высокой вероятностью должны быть в верхней части этого списка). Если используется двоичный кодовый алфавит, то две ветви с самыми низкими вероятностями объединяются (со сложением их вероятностей), но перед этим одна из них маркируется как 0, а другая – как 1. Затем эти ветви вновь упорядочиваются по вероятности и процесс повторяется. Процесс продолжается до тех пор, пока не останется только одна ветвь. Затем считываются кодовые слова, причем чтение выполняется в обратном порядке от последнего элемента с добавлением в кодовое слово встречающихся по пути нулей и единиц.

Например, возьмем систему со следующими вероятностями: A 0,25; B 0,3; C 0,35; D 0,1. Ранжируем их. Самые маленькие вероятности у элементов А и D (0,25 и 0,1). Они объединяются в одну AD ветвь, ветвь А маркируется как 0, а ветвь D как 1, и выполняется новое упорядочивание по убыванию вероятности:

С – 0,35; AD – 0,35; B – 0,3.

Относительно упорядочивания компонента AD имеется свобода выбора: располагать его можно либо выше, либо ниже компонента C. В каждом случае будут получены разные, но эквивалентные коды.

Затем объединяются компоненты AD и B, причем AD помечается как 0, а B – как 1. Это приводит к следующему списку:

ADB – 0,65; C – 0,35.

в котором компонента ADB маркируется как 0, а С – как 1, что дает только одну ветвь, на этом процесс заканчивается.

Извлечение кодовых слов выполняется следующим образом (начиная с последнего столбца, в обратном порядке):

А: 0 – от ветви ADB (последний столбец), 0 – от ветви AD (средний столбец) и 0 – от ветви А (первый столбец), что дает первое кодовое слово: 000;

В : 0 – от ветви ADB, 1 – от ветви В (средний столбец), что дает второе кодовое слово: 01 и т.д.

Рис. 1 Пример построения кода Хаффмана

Чтобы использовать кодирование Хаффмана для кодовых алфавитов, состоящих из большего количества символов, нужно выполнить небольшую модификацию этапа группировки: вместо объединения двух самых маловероятных компонентов перед переходом к следующему этапу нужно объединять n таких компонентов, где n – число символов кодового алфавита. Эти символы следует использовать для нумерации последних ветвей дерева на различных этапах процесса построения кодов Хаффмана. Следовательно, на каждом этапе этого процесса удаляются (n-1) входов (элементов) списка. Поскольку, в конце концов, остается элемент помеченный как 1, то в предыдущем списке должно быть 1+(n-1) элементов, а в его предшественнике – 1+2(n-1) элементов и т.д.

Содержание