Сайт о телевидении

Кодирование Хаффмана. Часть 1.
Вступление
Здравствуй, дорогой читатель! В данной статье будет рассмотрен один из способов сжатия данных. Этот способ является достаточно широко распространённым и заслуживает определённого внимания. Данный материал рассчитан по объёму на три статьи, первая из которых будет посвящена алгоритму сжатия, вторая - программной реализации алгоритма, а третья ― декомпрессии. Алгоритм сжатия будет написан на языке C++, алгоритм декомпрессии ― на языке Assembler.
Однако, перед тем, как приступить к самому алгоритму, следует включить в статью немного теории.
Немного теории
Компрессия (сжатие ) ― способ уменьшения объёма данных с целью дальнейшей их передачи и хранения.
Декомпрессия ― это способ восстановления сжатых данных в исходные.
Компрессия и декомпрессия могут быть как без потери качества (когда передаваемая/хранимая информация в сжатом виде после декомпрессии абсолютно идентична исходной), так и с потерей качества (когда данные после декомпрессии отличаются от оригинальных). Например, текстовые документы, базы данных, программы могут быть сжаты только способом без потери качества, в то время как картинки, видеоролики и аудиофайлы сжимаются именно за счёт потери качества исходных данных (характерный пример алгоритмов ― JPEG, MPEG, ADPCM), при порой незаметной потере качества даже при сжатии 1:4 или 1:10.
Выделяются основные виды упаковки:

• Десятичная упаковка предназначена для упаковки символьных данных, состоящих только из чисел. Вместо используемых 8 бит под символ можно вполне рационально использовать всего лишь 4 бита для десятичных и шестнадцатеричных цифр, 3 бита для восьмеричных и так далее. При подобном подходе уже ощущается сжатие минимум 1:2.
• Относительное кодирование является кодированием с потерей качества. Оно основано на том, что последующий элемент данных отличается от предыдущего на величину, занимающую в памяти меньше места, чем сам элемент. Характерным примером является аудиосжатие ADPCM (Adaptive Differencial Pulse Code Modulation), широко применяемое в цифровой телефонии и позволяющее сжимать звуковые данные в соотношении 1:2 с практически незаметной потерей качества.
• Символьное подавление - способ сжатия информации, при котором длинные последовательности из идентичных данных заменяются более короткими.
• Статистическое кодирование основано на том, что не все элементы данных встречаются с одинаковой частотой (или вероятностью). При таком подходе коды выбираются так, чтобы наиболее часто встречающемуся элементу соответствовал код с наименьшей длиной, а наименее частому ― с наибольшей.

Кроме этого, коды подбираются таким образом, чтобы при декодировании можно было однозначно определить элемент исходных данных. При таком подходе возможно только бит-ориентированное кодирование, при котором выделяются разрешённые и запрещённые коды. Если при декодировании битовой последовательности код оказался запрещённым, то к нему необходимо добавить ещё один бит исходной последовательности и повторить операцию декодирования. Примерами такого кодирования являются алгоритмы Шеннона и Хаффмана, последний из которых мы и будем рассматривать.
Конкретнее об алгоритме
Как уже известно из предыдущего подраздела, алгоритм Хафмана основан на статистическом кодировании. Разберёмся поподробнее в его реализации.
Пусть имеется источник данных, который передаёт символы (a_1, a_2, ..., a_n) с разной степенью вероятности, то есть каждому a_i соответствует своя вероятность (или частота) P_i(a_i) , при чём существует хотя бы одна пара a_i и a_j ,i\ne j , такие, что P_i(a_i) и P_j(a_j) не равны. Таким образом образуется набор частот {P_1(a_1), P_2(a_2),...,P_n(a_n)} , при чём \displaystyle \sum_{i=1}^{n} P_i(a_i)=1 , так как передатчик не передаёт больше никаких символов кроме как {a_1,a_2,...,a_n} .
Наша задача ― подобрать такие кодовые символы {b_1, b_2,...,b_n} с длинами {L_1(b_1),L_2(b_2),...,L_n(b_n)} , чтобы средняя длина кодового символа не превышала средней длины исходного символа. При этом нужно учитывать условие, что если P_i(a_i)>P_j(a_j) и i\ne j , то L_i(b_i)\le L_j(b_j) .
Хафман предложил строить дерево, в котором узлы с наибольшей вероятностью наименее удалены от корня. Отсюда и вытекает сам способ построения дерева:
1. Выбрать два символа a_i и a_j , i\ne j , такие, что P_i(a_i) и P_j(a_j) из всего списка {P_1(a_1),P_2,...,P_n(a_n)} являются минимальными.
2. Свести ветки дерева от этих двух элементов в одну точку с вероятностью P=P_i(a_i)+P_j(a_j) , пометив одну ветку нулём, а другую ― единицей (по собственному усмотрению).
3. Повторить пункт 1 с учётом новой точки вместо a_i и a_j , если количество получившихся точек больше единицы. В противном случае мы достигли корня дерева.
Теперь попробуем воспользоваться полученной теорией и закодировать информацию, передаваемую источником, на примере семи символов.
Разберём подробно первый цикл. На рисунке изображена таблица, в которой каждому символу a_i соответствует своя вероятность (частота) P_i(a_i) . Согласно пункту 1 мы выбираем два символа из таблицы с наименьшей вероятностью. В нашем случае это a_1 и a_4 . Согласно пункту 2 сводим ветки дерева от a_1 и a_4 в одну точку и помечаем ветку, ведущую к a_1 , единицей, а ветку, ведущую к a_4 ,― нулём. Над новой точкой приписываем её вероятность (в данном случае ― 0.03) В дальнейшем действия повторяются уже с учётом новой точки и без учёта a_1 и a_4 .

После многократного повторения изложенных действий выстраивается следующее дерево:

По построенному дереву можно определить значение кодов {b_1,b_2,...,b_n} , осуществляя спуск от корня к соответствующему элементу a_i , при этом приписывая к получаемой последовательности при прохождении каждой ветки ноль или единицу (в зависимости от того, как именуется конкретная ветка). Таким образом таблица кодов выглядит следующим образом:

i b i L i (b i) 1 011111 62 1 13 0110 44 011110 65 010 36 00 27 01110 5

Теперь попробуем закодировать последовательность из символов.
Пусть символу a_i соответствует (в качестве примера) число i . Пусть имеется последовательность 12672262. Нужно получить результирующий двоичный код.
Для кодирования можно использовать уже имеющуюся таблицу кодовых символов b_i при учёте, что b_i соответствует символу a_i . В таком случае код для цифры 1 будет представлять собой последовательность 011111, для цифры 2 ― 1, а для цифры 6 ― 00. Таким образом, получаем следующий результат:

Данные12672262Длина кодаИсходные001010110111010010110 01024 битКодированные011111100011101100119 бит

В результате кодирования мы выиграли 5 бит и записали последовательность 19 битами вместо 24.
Однако это не даёт полной оценки сжатия данных. Вернёмся к математике и оценим степень сжатия кода. Для этого понадобится энтропийная оценка.
Энтропия ― мера неопределённости ситуации (случайной величины) с конечным или с чётным числом исходов. Математически энтропия формулируется как сумма произведений вероятностей различных состояний системы на логарифмы этих вероятностей, взятых с обратным знаком:

H(X)=-\displaystyle \sum_{i=1}^{n}P_i\cdot log_d (P_i) .​

Где X ― дискретная случайная величина (в нашем случае ― кодовый символ), а d ― произвольное основание, большее единицы. Выбор основания равносилен выбору определённой единицы измерения энтропии. Так как мы имеем дело с двоичными цифрами, то в качестве основания рационально выбрать d=2 .
Таким образом, энтропию для нашего случая можно представить в виде:

H(b)=-\displaystyle \sum_{i=1}^{n}P_i(a_i)\cdot log_2 (P_i(a_i)) .​

Энтропия обладает замечательным свойством: она равна минимальной допустимой средней длине кодового символа \overline{L_{min}} в битах. Сама же средняя длина кодового символа вычисляется по формуле

\overline{L(b)}=\displaystyle \sum_{i=1}^{n}P_i(a_i)\cdot L_i(b_i) .​

Подставляя значения в формулы H(b) и \overline{L(b)} , получаем следующий результат: H(b)=2,048 , \overline{L(b)}=2,100 .
Величины H(b) и \overline{L(b)} очень близки, что говорит о реальном выигрыше в выборе алгоритма. Теперь сравним среднюю длину исходного символа и среднюю длину кодового символа через отношение:

\frac{\overline{L_{src}}}{L(b)}=\frac{3}{2,1}=1,429 .​

Таким образом, мы получили сжатие в соотношении 1:1,429, что очень неплохо.
И напоследок, решим последнюю задачу: дешифровка последовательности битов.
Пусть для нашей ситуации имеется последовательность битов:

001101100001110001000111111​

Необходимо определить исходный код, то есть декодировать эту последовательность.
Конечно, в такой ситуации можно воспользоваться таблицей кодов, но это достаточно неудобно, так как длина кодовых символов непостоянна. Гораздо удобнее осуществить спуск по дереву (начиная с корня) по следующему правилу:
1. Исходная точка ― корень дерева.
2. Прочитать новый бит. Если он ноль, то пройти по ветке, помеченной нулём, в противном случае ― единицей.
3. Если точка, в которую мы попали, конечная, то мы определили кодовый символ, который следует записать и вернуться к пункту 1. В противном случае следует повторить пункт 2.
Рассмотрим пример декодирования первого символа. Мы находимся в точке с вероятностью 1,00 (корень дерева), считываем первый бит последовательности и отправляемся по ветке, помеченной нулём, в точку с вероятностью 0,60. Так как эта точка не является конечной в дереве, то считываем следующий бит, который тоже равен нулю, и отправляемся по ветке, помеченной нулём, в точку a_6 , которая является конечной. Мы дешифровали символ ― это число 6. Записываем его и возвращаемся в исходное состояние (перемещаемся в корень).
Таким образом декодированная последовательность принимает вид.

Данные

001101100001110001000111111 Длина кодаКодированные00110110000111000100011111127 битИсходные6223676261233 бит

В данном случае выигрыш составил 6 бит при достаточно небольшой длине последовательности.
Вывод напрашивается сам собой: алгоритм прост. Однако следует сделать замечание: данный алгоритм хорош для сжатия текстовой информации (действительно, реально мы используем при набивке текста примерно 60 символов из доступных 256, то есть вероятность встретить иные символы близка к нулю), но достаточно плох для сжатия программ (так как в программе все символы практически равновероятны). Так что эффективность алгоритма очень сильно зависит от типа сжимаемых данных.
Постскриптум
В этой статье мы рассмотрели алгоритм кодирования по методу Хаффмана, который базируется на неравномерном кодировании. Он позволяет уменьшить размер передаваемых или хранимых данных. Алгоритм прост для понимания и может давать реальный выигрыш. Кроме этого, он обладает ещё одним замечательным свойством: возможность кодировать и декодировать информацию "на лету" при условии того, что вероятности кодовых слов правильно определены. Хотя существует модификация алгоритма, позволяющая изменять структуру дерева в реальном времени.
В следующей части статьи мы рассмотрим байт-ориентированное сжатие файлов с использованием алгоритма Хаффмана, реализованное на C++.
Кодирование Хаффмана. Часть 2
Вступление
В прошлой части мы рассмотрели алгоритм кодирования, описали его математическую модель, произвели кодирование и декодирование на конкретном примере, рассчитали среднюю длину кодового слова, а также определили коэффициент сжатия. Кроме этого, были сделаны выводы о преимуществах и недостатках данного алгоритма.
Однако, помимо этого неразрешёнными остались ещё два вопроса: реализация программы, сжимающей файл данных, и программы, распаковывающей сжатый файл. Первому вопросу и посвящена настоящая статья. Поэтому следует заняться проектированием.
Проектирование
Первым делом необходимо посчитать частоты вхождения символов в файл. Для этого опишем следующую структуру:

// Структура для подсчёта частоты символа

typedef struct TFreq

int ch;

TTable * table;

DWORD freq;

} TFreq;

Эта структура будет описывать каждый символ из 256. ch ― сам ASCII-символ, freq ― количество вхождений символа в файл. Поле table ― указатель на структуру:

// Описатель узла

typedef struct TTable

int ch;

TTable * left;

TTable * right;

} TTable;

Как видно, TTable ― это описатель узла с разветвлением по нулю и единице. При помощи этих структур в дальнейшем и будет осуществляться построение дерева компрессии. Теперь объявим для каждого символа свою частоту и свой узел:

TFreq Freq[ 256 ] ;

Попробуем разобраться, каким образом будет осуществляться построение дерева. На начальной стадии программа должна осуществить проход по всему файлу и подсчитать количество вхождений символов в него. Помимо этого, для каждого найденного символа программа должна создать описатель узла. После этого из созданных узлов с учётом частоты символов программа строит дерево, размещая узлы в определённом порядке и устанавливая между ними связи.
Построенное дерево хорошо для декодирования файла. Но для кодирования файла оно неудобно, потому что неизвестно, в каком направлении следует идти от корня, чтобы добраться до необходимого символа. Для этого удобнее построить таблицу преобразования символов в код. Поэтому определим ещё одну структуру:

// Описатель кодового символа

typedef struct TOpcode

DWORD opcode;

DWORD len;

} TOpcode;

Здесь opcode ― кодовая комбинация символа, а len - её длина (в битах). И объявим таблицу из 256 таких структур:

TOpcode Opcodes[ 256 ] ;

Зная кодируемый символ, можно определить его кодовое слово по таблице. Теперь перейдём непосредственно к подсчёту частот символов (и не только).
Подсчёт частот символов
В принципе, это действие не составляет труда. Достаточно открыть файл и подсчитать в нём число символов, заполнив соответствующие структуры. Посмотрим реализацию этого действия.
Для этого объявим глобальные дескрипторы файлов:

FILE * in, * out, * assemb;

in ― файл, из которого осуществляется чтение несжатых данных.
out ― файл, в который осуществляется запись сжатых данных.
assemb ― файл, в который будет сохранено дерево в удобном для распаковки виде. Так как распаковщик будет написан на ассемблере, то вполне рационально дерево сделать частью распаковщика, то есть представить его в виде инструкций на Ассемблере.
Первым делом необходимо проинициализировать все структуры нулевыми значениями:

// Подсчёт частот символов

int CountFrequency(void )

int i; // переменная цикла

int count= 0 ; // вторая переменная цикла

DWORD TotalCount= 0 ; // размер файла.

// Инициализация структур

for (i= 0 ; i< 256 ; i++ )

Freq[ i] .freq = 0 ;

Freq[ i] .table = 0 ;

Freq[ i] .ch = i;

После этого мы подсчитываем число вхождений символа в файл и размер файла (конечно, не самым идеальным способом, но в примере нужна наглядность):

// Подсчёт частот символов (по-символьно)

while (! feof (in) ) // пока не достигнут конец файла

i= fgetc (in) ;

if (i! = EOF ) // если не конец файла

Freq[ i] .freq ++ ; // частота ++

TotalCount++ ; // размер ++

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

// "Сообщаем" распаковщику размер файла

fprintf (assemb, "coded_file_size:\n dd %8lxh\n \n " , TotalCount) ;

После этого все используемые символы смещаются в начало массива, а неиспользуемые затираются (путём перестановок).

// смещаем все неиспользуемые символы в конец

i= 0 ;

count= 256 ;

while (i< count) // пока не достигли конца

if (Freq[ i] .freq == 0 ) // если частота 0

Freq[ i] = Freq[ -- count] ; // то копируем запись из конца

else

i++ ; // всё ОК - двигаемся дальше.

И только после такой "сортировки" выделяется память под узлы (для некоторой экономии).

// Выделяем память под узлы

for (i= 0 ; i< count; i++ )

Freq[ i] .table = new TTable; // создаём узел

Freq[ i] .table - > left= 0 ; // без соединений

Freq[ i] .table - > right= 0 ; // без соединений

Freq[ i] .table - > ch= Freq.ch ; // копируем символ

Freq[ i] .freq = Freq.freq ; // и частоту

return count;

Таким образом, мы написали функцию первоначальной иницализации системы, или, если смотреть на алгоритм в первой части статьи, "записали используемые символы в столбик и приписали к ним вероятности", а также для каждого символа создали "отправную точку" ― узел ― и проинициализировали её. В поля left и right записали нули. Таким образом, если узел будет в дереве последним, то это будет легко увидеть по left и right , равным нулю.
Создание дерева
Итак, в предыдущем разделе мы "записали используемые символы в столбик и приписали к ним вероятности". На самом деле, мы приписали к ним не вероятности, а числители дроби (то есть количество вхождений символов в файл). Теперь надо построить дерево. Но для того, чтобы это сделать, необходимо найти минимальный элемент в списке. Для этого вводим функцию, в которую передаём два параметра ― количество элементов в списке и элемент, который следует исключить (потому что искать будем парами, и будет очень неприятно, если мы от функции дважды получим один и тот же элемент):

// поиск узла с наименьшей вероятностью.

int FindLeast(int count, int index)

int i;

DWORD min= (index== 0 ) ? 1 : 0 ; // элемент, который считаем

// минимальным

for (i= 1 ; i< count; i++ ) // цикл по массиву

if (i! = index) // если элемент не исключён

if (Freq[ i] .freq < Freq[ min] .freq ) // сравниваем

min= i; // меньше минимума - запоминаем

return min; // возвращаем индекс минимума

Поиск реализован несложно: сначала выбираем "минимальный" элемент массива. Если исключаемый элемент ― 0, то берём в качестве минимума первый элемент, в противном случае минимумом считаем нулевой. По мере прохождения по массиву сравниваем текущий элемент с "минимальным", и если он окажется меньше, то его помечаем как минимальный.
Теперь, собственно говоря, сама функция построения дерева:

// Функция построения дерева

void PreInit(int count)

int ind1, ind2; // индексы элементов

TTable * table; // указатель на "новый узел"

while (count> 1 ) // цикл, пока не достигли корня

ind1= FindLeast(count,- 1 ) ; // первый узел

ind2= FindLeast(count,ind1) ; // второй узел

table= new TTable; // создаём новый узел

table- > ch= - 1 ; // не конечный

table- > left= Freq[ ind1] .table ; // 0 - узел 1

table- > right= Freq[ ind2] .table ; // 1 - узел 2

Freq[ ind1] .ch = - 1 ; // модифицируем запись о

Freq[ ind1] .freq + = Freq[ ind2] .freq ; // частоте для символа

Freq[ ind1] .table = table; // и пишем новый узел

if (ind2! = (-- count) ) // если ind2 не последний

Freq[ ind2] = Freq[ count] ; // то на его место

// помещаем последний в массиве

Таблица кодовых символов
Итак, дерево в памяти мы построили: попарно брали два узла, создавали новый узел, в который записывали на них указатели, после чего второй узел удаляли из списка, а вместо первого узла писали новый с разветвлением.
Теперь возникает ещё одна проблема: кодировать по дереву неудобно, потому что необходимо точно знать, по какому пути находится тот или иной символ. Однако проблема решается довольно просто: создаётся ещё одна таблица ― таблица кодовых символов ― в неё и записываются битовые комбинации всех используемых символов. Для этого достаточно однократно рекурсивно обойти дерево. Заодно, чтобы повторно его не обходить, можно в функцию обхода добавить генерацию ассемблерного файла для дальнейшего декодирования сжатых данных (см. раздел "Проектирование ").
Собственно, сама функция не сложна. Она должна приписывать к кодовой комбинации 0 или 1, если узел не конечный, в противном случае добавить кодовый символ в таблицу. Помимо всего этого, сгенерировать ассемблерный файл. Рассмотрим эту функцию:

void RecurseMake(TTable * tbl, DWORD opcode, int len)

fprintf (assemb,"opcode%08lx_%04x:\n " ,opcode,len) ; // метку в файл

if (tbl- > ch! = - 1 ) // узел конечный

BYTE mod= 32 - len;

Opcodes[ tbl- > ch] .opcode = (opcode>> mod) ; // сохраняем код

Opcodes[ tbl- > ch] .len = len; // и его длину (в битах)

// и создаём соответствующую метку

fprintf (assemb," db %03xh,0ffh,0ffh,0ffh\n \n " ,tbl- > ch) ;

else // узел не конечный

opcode>>= 1 ; // освобождаем место под новый бит

len++ ; // увеличиваем длину кодового слова

\n " ,opcode,len) ;

fprintf (assemb," dw opcode%08lx_%04x\n \n " ,opcode| 0x80000000 ,len) ;

RecurseMake(tbl- > left,opcode,len) ;

RecurseMake(tbl- > right,opcode| 0x80000000 ,len) ;

// удаляем узел (он уже не нужен)

delete tbl;

Помимо всего прочего, после прохождения узла функция удаляет его (освобождает указатель). Теперь разберёмся, что за параметры передаются в функцию.

• tbl ― узел, который надо обойти.
• opcode ― текущее кодовое слово. Старший бит должен быть всегда свободен.
• len ― длина кодового слова.

В принципе, функция не сложнее "классического факториала" и не должна вызывать трудностей.
Битовый вывод
Вот мы и добрались до не самой приятной части нашего архиватора, а именно ― до вывода кодовых символов в файл. Проблема состоит в том, что кодовые символы имеют неравномерную длину и вывод приходится осуществлять побитовый. В этом поможет функция PutCode . Но для начала объявим две переменные ― счётчик битов в байте и выводимый байт:

// Счётчик битов

int OutBits;

// Выводимый символ

BYTE OutChar;

OutBits увеличивается на один при каждом выводе бита, OutBits==8 сигнализирует о том, что OutChar следует сохранить в файл.

void PutCode(int ch)

int len;

int outcode;

// получаем длину кодового слова и само кодовое слово

outcode= Opcodes[ ch] .opcode ; // кодовое слово

len= Opcodes[ ch] .len ; // длина (в битах)

while (len> 0 ) // выводим по-битно

// Цикл пока переменная OutBits занята не полностью

while ((OutBits< 8 ) && (len> 0 ) )

OutChar>>= 1 ; // освобождаем место

OutChar| = ((outcode& 1 ) << 7 ) ; // и в него помещаем бит

outcode>>= 1 ; // следующий бит кода

len-- ; // уменьшаем длину

1. OutBits++ ; // количество битов выросло

2. }

3. // если используются все 8 бит, то сохраняем их в файл

4. if (OutBits== 8 )

5. {

6. fputc (OutChar,out) ; // сохраняем в файл

7. OutBits= 0 ; // обнуляем

8. OutChar= 0 ; // параметры

9. }

10. }

11. }

Помимо этого, нужно организовать что-то вроде "fflush", то есть после вывода последнего кодового слова OutChar не поместится в выходной файл, так как OutBits !=8. Отсюда появляется ещё одна небольшая функция:

1. // "Очистка" буфера битов

2. void EndPut(void )

3. {

4. // Если в буфере есть биты

5. if (OutBits! = 0 )

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

История алгоритма

Самым первым алгоритмом проведения эффективного кодирования электронной информации стал код, предложенный Хаффманом еще в середине двадцатого века, а именно в 1952 году. Именно он на данный момент является основным базовым элементом большинства программ, созданных для сжатия информации. На данный момент одними из самых популярных источников, использующих этот код, являются архивы ZIP, ARJ, RAR и многие другие.

Также данный алгоритм Хаффмана применяется для и других графических объектов. Ну и все современные факсы также используют кодирование, изобретенное в 1952 году. Несмотря на то что со времени создания кода прошло так много времени, по сей день его используют в самых новых оболочках и на оборудовании старого и современного типов.

Принцип эффективного кодирования

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

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

Код Хаффмана, пример

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

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

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

Алгоритм построения дерева по Хаффману

Построение кода Хаффмана делается из букв входного алфавита. Образуется список тех узлов, которые свободны в будущем кодовом дереве. Вес каждого узла в этом списке должен быть таким же, как и вероятность возникновения буквы сообщения, соответствующей этому узлу. При этом среди нескольких свободных узлов будущего дерева выбирается тот, который весит меньше всего. При этом если минимальные показатели наблюдаются в нескольких узлах, то можно свободно выбирать любую из пар.

После чего происходит создание родительского узла, который должен весить столько же, сколько весит сумма этой пары узлов. После этого родителя отправляют в список со свободными узлами, а дети удаляются. При этом дуги получают соответствующие показатели, единицы и нули. Этот процесс повторяется ровно столько, сколько нужно, чтобы оставить только один узел. После чего выписываются по направлению сверху вниз.

Повышение эффективности сжатия

Чтобы повысить эффективность сжатия, нужно во время построения дерева кода использовать все данные относительно вероятности появления букв в конкретном файле, прикрепленном к дереву, и не допускать того, чтобы они были раскиданы по большому количеству текстовых документов. Если предварительно пройтись по этому файлу, можно сразу просчитать статистику того, насколько часто встречаются буквы из объекта, подлежащего сжиманию.

Ускорение процесса сжатия

Чтобы ускорить работу букв нужно проводить не по показателям вероятности появления той или иной буквы, а по частоте ее встречаемости. Благодаря этому алгоритм становится проще, и работа с ним значительно ускоряется. Также это позволяет избежать операций, связанных с плавающими запятыми и делением.

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

Заключение

Коды Хаффмана - простой и давно созданный алгоритм, который до сих пор используется многими известными программами и компаниями. Его простота и понятность позволяют добиться эффективных результатов сжатия файлов любых объемов и значительно уменьшить занимаемое ими место на диске хранения. Иными словами, алгоритм Хаффмана - давно изученная и проработанная схема, актуальность которой не уменьшается по сей день.

А благодаря возможности уменьшить размер файлов, их передача через сеть или другими способами становится более простой, быстрой и удобной. Работая с алгоритмом, можно сжать совершенно любую информацию без вреда для ее структуры и качества, но с максимальным эффектом уменьшения веса файла. Иными словами, кодирование по коду Хаффмана было и остается самым популярным и актуальным методом сжатия размера файла.

Сегодня мало кого из пользователей интересует вопрос, связанный с механизмом сжатия файлов. Процесс работы с персональным компьютером по сравнению с прошлым стал осуществляться намного проще.

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

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

Алгоритм: история

Первым алгоритмом, предназначенным для проведения эффективного кодирования электронной информации, стал код, предложенный Хаффманом в 1952 году. Именно этот код на сегодняшний день можно считать базовым элементом большинства программ, разработанных для сжатия информации. Одними из наиболее популярных источников, которые используют данный код, на сегодняшний день являются архивы RAR, ARJ, ZIP. Данный алгоритм также используется для сжатия изображений JPEG и графических объектов. Также во всех современных факсах используется алгоритм кодирования, который был изобретен еще в 1952 году. Несмотря на то, что со времени создания данного кода прошло достаточно много времени, его эффективно используют в оборудовании старого типа, а также в новом оборудовании и оболочках.

Принцип эффективного кодирования

В основе алгоритма Хаффмана используется схема, которая позволяет заменить самые вероятные и наиболее часто встречающиеся символы кодами двоичной системы. Те символы, которые встречаются реже, заменяют длинными кодами. Переход к длинным кодам Хаффмана осуществляется только после того, как система использует все минимальные значения. Данная методика дает возможность минимизировать длину кода на символ исходного сообщения. В данном случае особенность заключается в том, что вероятности появления букв в начале кодирования должны быть уже известны. Конечное сообщение будет составляться именно из них. Исходя из этой информации, осуществляется построение кодового дерева Хаффмана. На основе него и будет осуществляться процесс кодирования букв в архиве.

Код Хаффмана: пример

Для того чтобы проиллюстрировать алгоритм Хаффмана, рассмотрим графический вариант построения кодового дерева. Чтобы использование данного способа было более эффективным, необходимо уточнить определение некоторых значений, которые необходимы для понятия данного способа. Всю совокупность множества узлов и дуг, которые направлены от узла к узлу, называют графом. Дерево само по себе является графом с набором определенных свойств. В каждый узел должно входить не больше одной из всех дуг. Один из узлов должен являться корнем дерева. Это значит, что в него не должны вообще входить дуги. Если начать от корня перемещения по дугам, то данный процесс должен позволять попасть в любой узел.

В коды Хаффмана также входит такое понятие, как лист дерева. Он представляет собой узел, из которого не должна выходить ни одна дуга. Если два узла между собой соединены дугой, то один из них является родителем, а другой ребенком. Если два узла имеют общий родительский узел, то их называют братскими узлами. Если кроме листьев у узлов выходит по несколько дуг, то такое дерево называют двоичным. Именно таким и является дерево Хаффмана. Особенностью узлов данного строения является то, что вес каждого родителя равняется сумме веса узловых детей.

Дерево Хаффмана: алгоритм построения

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

Как повысить эффективность сжатия

Для повышения эффективности сжатия, во время построения дерева кода необходимо использовать все данные, касающиеся вероятности появления букв в конкретном файле, который прикреплен к дереву. Нельзя допускать того, чтобы они были раскиданы по большому числу текстовых документов. Если пройтись предварительно по данному файлу, то можно получить статистику того, как часто встречаются буквы из объекта, который подлежит сжиманию.

Как ускорить процесс сжатия

Для ускорения работы алгоритма, определение букв нужно осуществлять не по показателям появления тех или иных букв, а по частоте их встречаемости. Алгоритм благодаря этому становится проще, а работа с ним значительно ускоряется. Это также дает возможность избежать операций, связанных с делением и плавающими запятыми. Также при работе в таком режиме, алгоритм не подлежит изменению. В основном это связано с тем, что вероятности прямо пропорциональны частотам. Стоит также обратить внимание на тот факт, что конечный вес корневого узла будет равняться сумме количества букв в объекте, который подлежит обработке.

Вывод

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

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

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

Классический алгоритм Хаффмана на входе получает таблицу частот встречаемости символов в сообщении. Далее на основании этой таблицы строится дерево кодирования Хаффмана (Н-дерево).

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

Допустим, у нас есть следующая таблица частот:

15	7	6	6	5
А	Б	В	Г	Д

Этот процесс можно представить как построение дерева , корень которого - символ с суммой вероятностей объединенных символов, получившийся при объединении символов из последнего шага, его n 0 потомков - символы из предыдущего шага и т. д.

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

Для данной таблицы символов коды Хаффмана будут выглядеть следующим образом.

А	Б	В	Г	Д
0	100	101	110	111

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

При этом общая длина сообщения, состоящего из приведённых в таблице символов, составит 87 бит (в среднем 2,2308 бита на символ). При использовании равномерного кодирования общая длина сообщения составила бы 117 бит (ровно 3 бита на символ). Заметим, что энтропия источника, независимым образом порождающего символы с указанными частотами составляет ~2,1858 бита на символ, т.е. избыточность построенного для такого источника кода Хаффмана, понимаемая, как отличие среднего числа бит на символ от энтропии, составляет менее 0,05 бит на символ.

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

Адаптивное сжатие

Адаптивное сжатие позволяет не передавать модель сообщения вместе с ним самим и ограничиться одним проходом по сообщению как при кодировании, так и при декодировании.

В создании алгоритма адаптивного кодирования Хаффмана наибольшие сложности возникают при разработке процедуры обновления модели очередным символом. Теоретически можно было бы просто вставить внутрь этой процедуры полное построение дерева кодирования Хаффмана, однако, такой алгоритм сжатия имел бы неприемлемо низкое быстродействие, так как построение Н-дерева - это слишком большая работа и производить её при обработке каждого символа неразумно. К счастью, существует способ модифицировать уже существующее Н-дерево так, чтобы отобразить обработку нового символа.

Обновление дерева при считывании очередного символа сообщения состоит из двух операций.

Первая - увеличение веса узлов дерева. Вначале увеличиваем вес листа, соответствующего считанному символу, на единицу. Затем увеличиваем вес родителя, чтобы привести его в соответствие с новыми значениями веса потомков. Этот процесс продолжается до тех пор, пока мы не доберемся до корня дерева. Среднее число операций увеличения веса равно среднему количеству битов, необходимых для того, чтобы закодировать символ.

Вторая операция - перестановка узлов дерева - требуется тогда, когда увеличение веса узла приводит к нарушению свойства упорядоченности, то есть тогда, когда увеличенный вес узла стал больше, чем вес следующего по порядку узла. Если и дальше продолжать обрабатывать увеличение веса, двигаясь к корню дерева, то дерево перестанет быть деревом Хаффмана.

Чтобы сохранить упорядоченность дерева кодирования, алгоритм работает следующим образом. Пусть новый увеличенный вес узла равен W+1. Тогда начинаем двигаться по списку в сторону увеличения веса, пока не найдем последний узел с весом W. Переставим текущий и найденный узлы между собой в списке, восстанавливая таким образом порядок в дереве (при этом родители каждого из узлов тоже изменятся). На этом операция перестановки заканчивается.

После перестановки операция увеличения веса узлов продолжается дальше. Следующий узел, вес которого будет увеличен алгоритмом, - это новый родитель узла, увеличение веса которого вызвало перестановку.

Переполнение

В процессе работы алгоритма сжатия вес узлов в дереве кодирования Хаффмана неуклонно растет. Первая проблема возникает тогда, когда вес корня дерева начинает превосходить вместимость ячейки, в которой он хранится. Как правило, это 16-битовое значение и, следовательно, не может быть больше, чем 65535. Вторая проблема, заслуживающая ещё большего внимания, может возникнуть значительно раньше, когда размер самого длинного кода Хаффмана превосходит вместимость ячейки, которая используется для того, чтобы передать его в выходной поток. Декодеру все равно, какой длины код он декодирует, поскольку он движется сверху вниз по дереву кодирования, выбирая из входного потока по одному биту. Кодер же должен начинать от листа дерева и двигаться вверх к корню, собирая биты, которые нужно передать. Обычно это происходит с переменной типа «целое», и, когда длина кода Хаффмана превосходит размер типа «целое» в битах, наступает переполнение.

Можно доказать, что максимальную длину код Хаффмана для сообщений с одним и тем же входным алфавитом будет иметь, если частоты символов образует последовательность Фибоначчи. Сообщение с частотами символов, равными числам Фибоначчи до Fib (18), - это отличный способ протестировать работу программы сжатия по Хаффману.

Масштабирование весов узлов дерева Хаффмана

Принимая во внимание сказанное выше, алгоритм обновления дерева Хаффмана должен быть изменен следующим образом: при увеличении веса нужно проверять его на достижение допустимого максимума. Если мы достигли максимума, то необходимо «масштабировать» вес, обычно разделив вес листьев на целое число, например, 2, а потом пересчитав вес всех остальных узлов.

Однако при делении веса пополам возникает проблема, связанная с тем, что после выполнения этой операции дерево может изменить свою форму. Объясняется это тем, что мы делим целые числа и при делении отбрасываем дробную часть.

Правильно организованное дерево Хаффмана после масштабирования может иметь форму, значительно отличающуюся от исходной. Это происходит потому, что масштабирование приводит к потере точности нашей статистики. Но со сбором новой статистики последствия этих «ошибок» практически сходят на нет. Масштабирование веса - довольно дорогостоящая операция, так как она приводит к необходимости заново строить все дерево кодирования. Но, так как необходимость в ней возникает относительно редко, то с этим можно смириться.

Выигрыш от масштабирования

Масштабирование веса узлов дерева через определенные интервалы дает неожиданный результат. Несмотря на то, что при масштабировании происходит потеря точности статистики, тесты показывают, что оно приводит к лучшим показателям сжатия, чем если бы масштабирование откладывалось. Это можно объяснить тем, что текущие символы сжимаемого потока больше «похожи» на своих близких предшественников, чем на тех, которые встречались намного раньше. Масштабирование приводит к уменьшению влияния «давних» символов на статистику и к увеличению влияния на неё «недавних» символов. Это очень сложно измерить количественно, но, в принципе, масштабирование оказывает положительное влияние на степень сжатия информации. Эксперименты с масштабированием в различных точках процесса сжатия показывают, что степень сжатия сильно зависит от момента масштабирования веса, но не существует правила выбора оптимального момента масштабирования для программы, ориентированной на сжатие любых типов информации.

Применение

Сжатие данных по Хаффману применяется при сжатии фото- и видеоизображений (JPEG , стандарты сжатия MPEG), в архиваторах (PKZIP , LZH и др.), в протоколах передачи данных MNP5 и MNP7.

Примечания

Литература

• Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн. Алгоритмы: построение и анализ = Introduction to Algorithms. - 2-е изд. - М .: Вильямс, 2006. - 1296 с. - ISBN 0-07-013151-1
• Д. Сэломон. Сжатие данных, изображения и звука. - М .: Техносфера, 2004. - 368 с. - 3000 экз. - ISBN 5-94836-027-X
• Ананий В. Левитин. Глава 9. Жадные методы: Алгоритм Хаффмана // Алгоритмы: введение в разработку и анализ = Introduction to The Design and Analysis of Aigorithms. - М .: Вильямс, 2006. - С. 392-398. - ISBN 0-201-74395-7

Ссылки

• Код Хаффмана (WebArchive)
• Сжатие по алгоритму Хаффмана на algolist.manual.ru

Методы сжатия
Теория
Без потерь	Энтропийное сжатие Алгоритм Хаффмана · Адаптивный алгоритм Хаффмана · Алгоритм Шеннона - Фано · Арифметическое кодирование (Интервальное) · Коды Голомба · Дельта · Универсальный код (Элиаса · Фибоначчи) Словарные методы RLE · Deflate · LZ (LZ77/LZ78 · LZSS · LZW · LZWL · LZO · LZMA · LZX · LZRW · LZJB · LZT) Прочее RLE · CTW · BWT · MTF · PPM · DMC
Аудио	Теория Свёртка · PCM · Алиасинг · Дискретизация · Теорема Котельникова Методы LPC (LAR · LSP) · WLPC · CELP · ACELP · A-закон · μ-закон · MDCT · Преобразование Фурье · Психоакустическая модель Прочее Компрессор аудиосигнала · Сжатие речи · Полосное кодирование
Изображения	Термины Цветовое пространство · Пиксель · Субдискретизация насыщенности · Артефакты сжатия Методы RLE · DPCM · Фрактальный · Вейвлетный · EZW · SPIHT · LP ·

Один из первых алгоритмов эффективного кодирования информации был предложен Хаффманом в 1952 г. Этот алгоритм стал базой для большого количества программ сжатия информации. Например, кодирование по Хаффману используется в программах сжатия ARJ, ZIP, RAR, в алгоритме сжатия графических изображений с потерями JPEG, а также встроено в современные факс-аппараты.

Эффективное кодирование по Хаффману состоит в представлении наиболее вероятных (часто встречающихся) букв двоичными кодами наименьшей длины, а менее вероятных - кодами большей длины (если все кодовые слова меньшей длины уже исчерпаны). Это делается таким образом, чтобы средняя длина кода на букву исходного сообщения была минимальной.

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

Построение кодового дерева Хаффмана

Для иллюстрации алгоритма Хаффмана рассмотрим графический способ построения дерева кодирования. Перед этим введем некоторые определения, принятые для описания алгоритма Хаффмана с использованием этого способа.

Граф - совокупность множества узлов и множества дуг, направленных от одного узла к другому.

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

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

Лист дерева - узел, из которого нс выходит ни одной дуги. В парс

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

Два узла называются братьями, если имеют одного и того же родителя.

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

Дерево кодирования Хаффмана - двоичное дерево, у которого каждый узел имеет вес, и при этом вес родителя равен суммарному весу его детей. Алгоритм построения дерева кодирования Хаффмана таков:

• 1. Буквы входного алфавита образуют список свободных узлов будущего дерева кодирования. Каждый узел в этом списке имеет вес, равный вероятности появления соответствующей буквы в сообщении.
• 2. Выбираются два свободных узла дерева с наименьшими весами. Если имеется более двух свободных узлов с наименьшими весами, то можно брать любую пару.
• 3. Создается их родитель с весом, равным их суммарному весу.
• 4. Родитель добавляется в список свободных узлов, а двое его детей удаляются из этого списка.
• 5. Одной дуге, выходящей из узла-родителя, ставится в соответствие бит 1, другой - 0.
• 6. Пункты 2, 3, 4, 5 повторяются до тех пор, пока в списке свободных узлов не останется только один узел. Этот узел будет являться корнем дерева. Его вес получается равным единице - суммарной вероятности всех букв сообщения.

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

Для примера рассмотрим построение дерева кодирования Хаффмана для приведенного в табл. 10.1 алфавита из восьми букв.

Таблица 10.1

Вероятность

Построение дерева начинаем со списка листьев (рис. 10.2) и выполняем по шагам.

Рис. 10.2.

На первом шаге из листьев дерева выбираются два с наименьшим весом - z 7 и zg. Они присоединяются к узлу-родителю, вес которого устанавливается в 0,04 + 0,02 = 0,06. Затем узлы z 7 и z 8 удаляются из списка свободных. Узел z 7 соответствует ветви 0 родителя, узел z 8 - ветви 1. Дерево кодирования после первого шага приведено на рис. 10.3.

Рис. 10.3.

На втором шаге «наилегчайшей» парой оказывается лист Zb и свободный узел (г 7 + z 8). Для них создастся родитель с весом 0,16. Узел Zb соответствует ветви 0 родителя, узел (г 7 + zg) - ветви 1. На данном шаге дерево кодирования приведено на рис. 10.4.

Рис. 10.4.

На третьем шаге наименьшие вероятности имеют zs, z* , Zj и свободный узел (zb + Zi+ z.g ). Таким образом, на данном шаге можно создать родителя для z$ и (Zb + г 7 + г 8) с весом 0,26, получив при этом дерево кодирования, представленное на рис. 10.5. Обратите внимание, что в данной ситуации возможны несколько вариантов соединения узлов с наименьшими весами. При этом все такие варианты будут правильными, хотя и могут привести к различным наборам кодов, которые, впрочем, будут обладать одинаковой эффективностью для заданного распределения вероятностей.

Рис. 10.5.

На четвертом шаге «наилегчайшей» парой оказываются листья ц и 24- Дерево кодирования Хаффмана приведено на рис. 10.6.

Рис. 10.6.

Рис. 10. 7.

Рис. 10.8.

На пятом шаге выбираем узлы с наименьшими весами 0,22 и 0,20. Дерево кодирования Хаффмана после пятого шага приведено на рис. 10.7.

На шестом шаге остается три свободных узла с весами 0,42, 0,32 и 0,26. Выбираем наименьшие веса 0,32 и 0,26. Дерево кодирования Хаффмана после шестого шага приведено на рис. 10.8.

На седьмом шаге остается объединить две оставшиеся свободные вершины, после чего получаем окончательное дерево кодирования Хаффмана, приведенное на рис. 10.9.

Рис. 10.9.

На основании построенного дерева буквы представляются кодами, отражающими путь от корневого узла до листа, соответствующего нужной букве. В рассмотренном примере буквы входного алфавита кодируются так, как показано в табл. 10.2.

Таблица 10.2

Рис. 10.10.

Видно, что наиболее вероятные буквы закодированы самыми короткими кодами, а наиболее редкие - кодами большей длины, причем коды построены таким образом, что ни одна кодовая комбинация нс совпадает с началом более длинной комбинации. Это позволяет однозначно декодировать сообщения без использования разделительных символов.

Для заданных в табл. 10.1 вероятностей можно построить и другие правильные варианты кодового дерева Хаффмана. Одно из допустимых деревьев приведено на рис. 10.10. Коды букв входного алфавита для данного кодового дерева приведены в табл. 10.3.

Из табл. 10.3 видно, что коды также получились префиксными, и наиболее вероятным буквам соответствуют наиболее короткие коды.

Таблица 10.3