Реферат: Научные проблемы Интернета

Дальнейший процесс объединения комбинаций выполним по аналогии (рис. 1.16, 1.17)

‘000-101’ – 2 ‘010-111’ – 2 ‘001-011’ – 2 Рис. 3.16.

‘010-111-001-011’ – 4 ‘000-101’ – 4 Рис. 3.17.

Теперь нарисуем дерево, схематически передающее реализованный нами способ объединения комбинаций (рис. 1.18)

Рис. 1.18.

Для полученного дерева выполним движение с корневой вершины к исходным тройкам. При выходе из любого узла помечаем одно из двух ребер «1», а другое – «0» (рис. 1.18). Итак, запомним, что разметка выполняется при движении справа на лево по построенному дереву. Теперь новый код для любой из исходных троек получаем как комбинацию, сопоставляемую пути из корня в данную вершину. Получаем следующее соответствие исходных троек и новых комбинаций:

000 – 11

101 – 10

010 – 001

111 – 010

001 – 001

011 – 000

С учетом нового способа кодировки исходная последовательность (1.17) может быть переписана таким образом:

01111101110010001000.

(1.18)

Длина последовательности (3.18) сократилась в сравнении с длиной (1.17) с 24 бит до 20 бит. Основной принцип кодирования Хаффмана состоит в том, что часто встречаемые комбинации кодируются более короткими последовательностями. Таким образом, общая длина последовательности оценивается как

,

(1.19)

где – число битов в i -ой комбинации,

– относительная частота встречаемости i -ой комбинации.

Было замечено, хотя это и не обязательно верно во всех случаях, что длина кода Хаффмана комбинации , как правило, не превосходит величину (– ). Так, в нашем примере относительная частота комбинации 000 составляет . Ее код Хаффмана есть 11 (длина этого кода равна 2). Имеем

(что справедливо).

Таким образом, при кодировании Хаффмана результирующую длину кода можно ориентированно записать в виде

.

(1.20)

Кодирование Хаффмана модно применять повторно.

Арифметическое кодирование

Пусть имеется последовательность .

(1.21)

Относительная частота символов:

, , .