Цифровая фотоаппаратура. Трубникова Т.А - 59 стр.

UptoLike

ВУЗ: 

СПбГИКиТ | Санкт-Петербург

Составители: 

Рубрика: 

155 156
0011 1100
В итоге получаем коды Хаффмана, но записанные в
обратном порядке (табл.9.1.). Последовательности символов
будет соответствовать код
01011111011100. С 0 начинается только один код- код симво-
ла , поэтому он так и декодируется. Затем идёт код, на-
чинающийся с битовой единицы. Таких кодов несколько, по-
этому прочитывается следующий бит, который равен 0. Код
10- единственный, соответствующий символу . После
этого идёт код 111- это однозначно говорит, что это .
Последние два кода точно декодируют символы
. Среднее количество бит на символ можно по-
считать по формуле:
(9.13.)
где n- количество символов в коде, р- вероятность появления
символа, i- количество символов. Для данного примера по-
строенные таким образом однозначные коды будут тратить
2,2 бита на символ. Обычный двоичный код потребовал бы 3
бита на символ, т.е. в этом случае последовательность можно
было бы сжать в 1,36 раза.
Однако, данный алгоритм имеет ряд недостатков: для
восстановления содержимого сообщения декодер должен
знать таблицу частот, которой пользовался кодер. Длина сжа-
того сообщения увеличивается на длину таблицы вероятно-
стей, которая должна посылаться впереди данных. Кроме это-
го, необходима полная вероятностная статистика перед нача-
лом кодирования, для этого необходимо делать два прохода
по сообщению. Поэтому, на практике применяют другой ме-
тод формирования кодов переменной длины, который позво-
ляет по мере кодирования данных уточнять коды Хаффмана -
адаптивное кодирование.
9.4.3. Адаптивное кодирование Хаффмана
Адаптивное кодирование позволяет не передавать модель со-
общения вместе с ним самим и ограничиться одним проходом
по сообщению как при кодировании, так и при декодирова-
нии. Алгоритм называют адаптивным потому, что этот алго-
ритм при каждом сопоставлении символу кода, кроме того
изменяет внутренний ход вычислений так, что в следующий
раз этому же символу может быть сопоставлен другой код,
т.е. происходит адаптация алгоритма к поступающим для ко-
дирования символам. Компрессор и декомпрессор начинают
работать с пустого дерева Хаффмана, а потом модифицируют
его по мере чтения и обработки символов. Сначала кодер
строит пустое дерево Хаффмана, не присваивая код никакому
символу. Первый символ записывается в выходной поток в
незакодированной форме (в 8 битной кодировке ASC2). Затем
этот символ помещается в дерево и ему присваивается код,

Страницы