Раздел: Документация
0 ... 27 28 29 30 31 32 33 ... 122 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.
Таблица 3.4. Вероятности векторов движения в последовательности .V»2.
2. Кодирование. Каждому листу двоичного дерева ставится в соответствие код переменной длины. Для нахождения этого кода следует пройтись по дереву, начиная от корня (узел D) и двигаясь в сторону выбранного листа (элемента списка). При проходе каждой ветви к коду добавляются двоичные цифры 0 или
На рис. 3.46 построено соответствующее дерево Хаффмана. Заметим, что «форма» дерева претерпела некоторые изменения (в силу изменения распределения вероятностей), и это, в свою очередь, породило новые коды Хаффмана (табл. 3.5). У дерева по-прежиему четыре узла, на один меньше числа элементов (пять), что характерно для любого дерева Хаффмана. Конец примера 1; 0 соответствует верхней ветви, а 1 — нижней (они показаны на рис. 3.45). Полученное множество кодов приведено в табл. 3.3. Кодирование состоит в передаче соответствующего кода вместо вектора. Отметим, что дерево Хаффмана строится один раз и полученные коды можно хранить в поисковой таблице. Элементам, имеющим большие вероятности, присваиваются короткие коды (например, код 1 присвоен вектору 0, который появляется чаще других). Векторам (—2, +2, —1, +1) присвоены коды из 3 бит (несмотря иа то что векторы —1 и +1 имеют большую вероятность, чем -2 и +2). Длины кодов Хаффмана (целые числа) не совпадают с идеальными длинами, задаваемыми формулой log2(l/p). Кроме того, ни одно кодовое слово не является началом (префиксом) никакого другого кодового слова. Это означает, что каждая кодовая последовательность будет однозначно декодирована при чтении слева направо. Код, обладающий этим свойством, называется однозначно декодируемым. Например, последовательность векторов (1,0, -2) будет передана с помощью двоичного кода 0111000. 3. Декодирование. Для декодирования данных декодер должен иметь копию дерева Хаффмана (или таблицу кодов). Эту таблицу можно передать отдельно, а можно переслать список элементов вместе с их вероятностями перед передачей кодированных данных. Каждый однозначно декодируемый код позволяет восстановить исходные данные, например: 011 декодируется в (1), 1 декодируется в (0), 000 декодируется в (2). Конец примера Пример- Кодирование Хаффмана, последовательность Л«2 векторов перемещения. Применение описанной выше процедуры к последовательности №2 с другим распределением вероятностей векторов приводит к другим кодам Хаффмана. Новые вероятности приведены в табл. 3.4. Отметим, что в этом примере нулевой вектор встречается существенно чаще (это соответствует видеопоследовательности с медленным движением). Таблица 3.S. Коды Хаффмана для векторов движения последовательности N2.  Рис. 3.46. Дерево Хаффмана (последовательность №2). Если распределение вероятностей хорошо соответствует частотам появления символов, то кодирование Хаффмана дает достаточно компактное представление исходных данных. В этих примерах вектор (0) с наибольшей вероятностью представляется кодом длиной в 1 бит. Однако для достижения оптимального сжатия необходимо использовать разные таблицы для этих последовательностей, имеющих разные распределения вероятностей векторов. Определенное снижение эффективности сжатия при использовании кодов с целочисленной длиной отчетливо видно при кодировании вектора (0) последовательности №2, так как оптимальное число бит (информационная емкость) для этого вектора равно 0.32 бит, однако лучшее, что может обеспечить код Хаффмана, это 1 бит. 3.5.2.2. Кодирование Хаффмана с предварительными вычислениями Кодирование Хаффмана имеет два недостатка, которые проявляются при его реализации на практике в видеокодеках. Во-первых, декодер должен использовать то же самое семейство кодов. Передача информации, содержащейся в таблице вероятностей, потребует дополнительных битов, что сокращает степень сжатия, особенно при кодировании коротких видеофрагментов. Во-вторых, таблицу вероятностей для длинной видеопоследовательности (необходимую для построения дерева Хаффмана) можно определить только после просмотра всей видеопоследовательности. Это может привести к недопустимой задержке процесса кодирования, передачи 0 ... 27 28 29 30 31 32 33 ... 122
|
