Лекция 5. Адаптивные алгоритмы сжатия.

Кодирование Хаффмана.

В современной технике связи широко применяется один из таких способов экономного представления - код Хаффмана. При кодировании символов сообщения комбинациями переменной длины возникает также проблема отделения одной комбинации от другой. Код Хаффмана обладает свойством префиксности, т.е. ни одна его кодовая комбинация не является началом другой комбинации, что позволяет обойтись в тексте кодированного сообщения без разделителей между комбинациями. Применение кода Хаффмана позволяет сократить длину сообщения с 5*N двоичных знаков (при равномерном двоичном кодировании) практически до H1*N=4,1*N двоичных знаков. Теперь для кодирования одной буквы будет в среднем расходоваться 4,1 двоичных знаков, и длина сообщения сократится.

Алгоритм, является практичным, однопроходным, не требующим передачи таблицы кодов. Его суть в использовании адаптивного алгоритма, т.е. алгоритма, который при каждом сопоставлении символу кода, кроме того, изменяет внутренний ход вычислений так, что в следующий раз этому же символу может быть сопоставлен другой код, т.е. происходит адаптация алгоритма к поступающим для кодирования символам. При декодировании происходит аналогичный процесс.

В начале работы алгоритма дерево кодирования содержит только один специальный символ, всегда имеющий частоту 0. Он необходим для занесения в дерево новых символов: после него код символа передается непосредственно. Обычно такой символ называют escape-символом (<ESC>). Расширенный ASCII кодируют каждый символ 8-бнтным числом, т.е. числом от 0 до 255. При построении дерева кодирования необходимо для возможности правильного декодирования как-то упорядочивать структуру дерева. Расположим листья дерева в порядке возрастания частот и затем в порядке возрастания стандартных кодов символов. Узлы собираются слева направо без пропусков. Левые ветви помечаются 0, а правые 1.

Рассмотрим процесс построения кодов по адаптивному алгоритму Хаффмана для сообщения АССВСАААВС. которое соответствует выборке 10-и значений д. с в. Х' из 2-го примера на построение неадаптивного кода Хаффмана:

Здесь L₁(ACCBCAAABC) = 4.1 бит/сим. Если не использовать сжатия, то L₁(ACCBCAAABC) = 8 бит/сим. Для рассматриваемой д.c. в. ранее были получены значения ML₁(X) = 1.6бит/сим и НХ ≈1,523 бит/сим. Но с ростом длины сообщения среднее количество бит на символ сообщения при адаптивном алгоритме кодирования будет мало отличаться от значения, полученного при использовании неадаптивного метода Хаффмана или Шеннона-Фано, т.к. алфавит символов ограничен и полный код каждого символа нужно передавать только один раз.

Теперь рассмотрим процесс декодирования сообщения 'А'0'С'100'В'1001010100101.

Здесь и далее символ в апострофах означает восемь бит, представляющих собой запись двоичного числа, номера символа, в таблице ASCII+. В начале декодирования дерево Хаффмана содержит только еsсаре -символ с частотой 0. С раскодированием каждого нового символа дерево заново перестраивается.

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

Дата добавления: 2022-01-22; просмотров: 75; Мы поможем в написании вашей работы!

Поделиться с друзьями:

⇐ Предыдущая 1 2 3 4 567 8 9 10 Следующая ⇒

Мы поможем в написании ваших работ!