Пример

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

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

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

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

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

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

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

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

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

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

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.

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