Сумский государственный университет

Ю.А Зубань, канд. техн. наук;

В.В. Петров, студ.

Адаптивные алгоритмы кодирования весьма эффективны для сжатия данных. Адаптивный (динамический) метод Хаффмана позволяет достичь наиболее высокой степени сжатия и достаточно хорошей скорости обработки данных. Синтез автоматной модели адаптивного кодирования Хаффмана - основная цель данной статьи. Полученная модель автомата и результаты исследования могут использоваться для аппаратной реализации адаптивного алгоритма кодирования Хаффмана.

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

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

Любой способ, подход и алгоритм, реализующий сжатие данных, предназначен для снижения объема выходного потока данных при помощи ее обратимого или необратимого преобразования.

Метод Хаффмана даёт достаточно высокую скорость и хорошее качество сжатия. Широко применяется как в программных (всевозможные компрессоры, архиваторы и программы резервного копирования файлов и дисков), так и в аппаратных (системы сжатия, ”прошитые” в модемы и факсы, сканеры) реализациях.

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

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

Первый - заключается в просмотре входного потока и построении кодирования на основании собранной статистики, при этом требуется два прохода по массиву данных: один - для просмотра и сбора статистической информации, второй - для кодирования. В таком случае в выходной поток записывается статистическая схема использованного кодирования. Это несколько ограничивает сферу применения таких алгоритмов, так как исключает возможность однопроходного кодирования “на лету”, применяемого в телекоммуникационных системах, где и объем данных подчас не известен, а их повторная передача или разбор может занять неоправданно много времени. Данный метод известен как статическое кодирование Хаффмана.

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

Поскольку статические модели (в которых распределение принимается неизменным) в большинстве случаев не дают максимального качества сжатия, гораздо больший интерес представляют так называемые адаптивные модели, учитывающие текущий контекст потока. Такие модели позволяют строить быстрые однопроходные алгоритмы сжатия, не требующие априорных знаний о входном потоке данных и строящие распределение “на лету”.

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

Как правило, кодовые комбинации синтезируются программно. Для аппаратной реализации обычно используется табличный метод. Его суть в том, что кодирование входных символов осуществляется с помощью таблицы (размещенной в ROM, ПЛМ и др. носителях данных, имеющих адресный доступ и соответствующую разрядность), которая содержит в себе информацию о дереве или о нескольких деревьях, структура и количество которых выбираются в зависимости от характеристик источника информации. По сути, в данном случае таблица представляет собой преобразователь кода, который пришедшей кодовой комбинации ставит в соответствие одну из немногих комбинаций кода Хаффмана, согласно изменению одного или группы параметров источника [2].

Алгоритм построения кодового дерева Хаффмана:

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

б) выбираются два свободных узла дерева с наименьшими весами;

в) создается узел с суммарным весом выбранных узлов;

г) созданный узел добавляется в список свободных, а два исходных удаляются из этого списка;

д) одной связи, выходящей из созданного узла, ставится в соответствие бит 1, другой - бит 0;

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

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

В общем виде автомат построения кода Хаффмана можно представить входным алфавитом

,

распределение вероятностей которого

,

выходным алфавитом

,

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

,

.(1)

В соответствии с (1) в ходе построения кода происходит n-1 сортировка, в результате каждой из которых определяются два узла с наименьшими значениями вероятностей и , где

, .

Совокупность минимальных значений вероятностей представляет собой множество (2).

={,, …, }{, …, }, (2)

|| = 2(n-1) = 2n - 2 ,

Сумма двух минимальных вероятностей дает третью - вероятность узла дерева Хаффмана:

.

Число создаваемых узлов в соответствии с (1) равно (n-1).Таким образом, существует множество узлов дерева

={,, …, }, || = (n-1),

являющееся подмножеством

().

Множество Y состоит из 0 и 1. В процессе формирования кода символа автоматом выполняется Z переходов, в результате чего формируется двоичная последовательность длины Z, которая и является кодом данного символа. Обозначим принадлежность символа входного алфавита к поддереву как . Поддерево- дерево, построенное начиная с узла, являющегося корнем. Значение y_i-го бита зависит от и , например: если , то бит y_i равен 0, а если , то y_i=1. Формирование кодового дерева Хаффмана приведено в таблице 2.

Таблица 2

СПИСОК ЛИТЕРАТУРЫ

1 Жураковський Ю.П., Полторак В.П. Теорія інформації та кодування: Підручник. - К.: Вища шк., 2001. - 255 с.:іл..

2 Ватолин Д., Ратушняк и др. Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео. - М.: ДИАЛОГ-МИФИ, 2002. - 348 с