Читать в оригинале

<< ПредыдущаяОглавлениеСледующая >>


3.5.2. Коды переменной длины

Метод кодирования переменной длины сопоставляет потоку входных символов определенную последовательность кодовых слов (коды переменной длины, VLC, Variable Length Codes). Каждый символ отображается в кодовое слово, которое может иметь переменную длину, но каждое из них имеет целое число бит. Символы, встречающиеся чаще, представляются более короткими словами VLC, а редко встречающиеся символы кодируются более длинными словами VLC. Эффект сжатия данных начинает проявляться после кодирования достаточно большого числа входных символов.

3.5.2.1. Коды Хаффмана

Метод кодирования Хаффмана присваивает каждому символу код VLC, исходя из вероятности появления этого символа. В соответствии со схемой, предложенной Хаффманом в 1952 году [7], следует предварительно вычислить вероятность появления каждого символа и построить множество кодовых слов переменной длины. Этот процесс будет проиллюстрирован на двух примерах.

Пример

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

Таблица 3.2. Вероятности векторов движения в последовательности № 1.

Вектор

Вероятность

-2

0,1

3,32

-1

0,2

2,32

0

0,4

1,32

+1

0,2

2,32

+2

0,1

3,32

Рис. 3.45. Построение дерева Хаффмана (последовательность №1).

1. Построение дерева Хаффмана. Чтобы построить таблицу кодов Хаффмана для этого множества элементов, следует совершить итеративную процедуру:

1. упорядочить элементы по возрастанию вероятностей;

2. объединить два элемента с наименьшими вероятностями в один узел и присвоить этому узлу суммарную вероятность этих элементов;

3. переупорядочить оставшиеся элементы и узлы по возрастанию юс вероятностей и повторить шаг 2.

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

Исходный список:

Исходные элементы обозначены квадратами. Векторы

 

(-2) и (+2) имеют наименьшие вероятности и являются

 

первыми кандидатами на слияние в узел А.

Шаг 1:

Созданный новый узел А (показан кружком) имеет

 

вероятность 0,2 (сумма вероятностей (-2) и (+2)).

 

Теперь имеется три элемента с вероятностью 0,2.

 

Выбираем векторы (-1) и (+1) и объединяем их

 

в один узел В.

Шаг 2:

Узел А имеет теперь наименьшую вероятность (0,2),

 

за ним следует узел В и вектор (0). Сливаем А и

 

В в один узел С.

Шаг 3:

Узел С и вектор (0) сливаются в узел D.

Конечное дерево:

Все элементы (векторы) встроены в двоичное дерево,

 

состоящее из пяти элементов и четырех узлов. Каждый

 

из элементов называется листом дерева.

Таблица 3.3. Коды Хаффмана для векторов движения последовательности №1.

Вектор

Код

Битов (фактически)

Битов (в идеале)

0

1

1

1,32

+ 1

011

3

2,32

-1

010

3

2,32

+2

001

3

3,32

-2

000

3

3,32

Таблица 3.4. Вероятности векторов движения в последовательности №2.

Вектор

Вероятность

-2

0,02

5,64

-1

0,07

3,84

0

0,80

0,32

+ 1

0,08

3,64

+2

0,03

5,06

2. Кодирование. Каждому листу двоичного дерева ставится в соответствие код переменной длины. Для нахождения этого кода следует пройтись по дереву, начиная от корня (узел D) и двигаясь в сторону выбранного листа (элемента списка). При проходе каждой ветви к коду добавляются двоичные цифры 0 или 1; 0 соответствует верхней ветви, а 1 — нижней (они показаны на рис. 3.45). Полученное множество кодов приведено в табл. 3.3.

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

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

3. Декодирование. Для декодирования данных декодер должен иметь копию дерева Хаффмана (или таблицу кодов). Эту таблицу можно передать отдельно, а можно переслать список элементов вместе с их вероятностями перед передачей кодированных данных. Каждый однозначно декодируемый код позволяет восстановить исходные данные, например:

011 декодируется в (1),

1 декодируется в (0),

000 декодируется в (2).

 

Пример

Кодирование Хаффмана, последовательность №2 векторов перемещения. Применение описанной выше процедуры к последовательности №2 с другим распределением вероятностей векторов приводит к другим кодам Хаффмана. Новые вероятности приведены в табл. 3.4. Отметим, что в этом примере нулевой вектор встречается существенно чаще (это соответствует видеопоследовательности с медленным движением).

Таблица З.5. Коды Хаффмана для векторов движения последовательности N2.

Вектор

Код

Битов (фактически)

Битов (в идеале)

0

1

1

0,32

+ 1

01

2

3,64

-1

001

3

3,84

+2

0001

4

5,06

-2

0000

4

5,64

На рис. 3.46 построено соответствующее дерево Хаффмана. Заметим, что «форма» дерева претерпела некоторые изменения (в силу изменения распределения вероятностей), и это, в свою очередь, породило новые коды Хаффмана (табл. 3.5). У дерева по-прежнему четыре узла, на один меньше числа элементов (пять), что характерно для любого дерева Хаффмана.

Рис. 3.46. Дерево Хаффмана (последовательность №2).

Если распределение вероятностей хорошо соответствует частотам появления символов, то кодирование Хаффмана дает достаточно компактное представление исходных данных. В этих примерах вектор (0) с наибольшей вероятностью представляется кодом длиной в 1 бит. Однако для достижения оптимального сжатия необходимо использовать разные таблицы для этих последовательностей, имеющих разные распределения вероятностей векторов. Определенное снижение эффективности сжатия при использовании кодов с целочисленной длиной отчетливо видно при кодировании вектора (0) последовательности №2, так как оптимальное число бит (информационная емкость) для этого вектора равно 0,32 бит, однако лучшее, что может обеспечить код Хаффмана, это 1 бит.

 



<< ПредыдущаяОглавлениеСледующая >>