7.1 Основная идея адаптивного кодирования

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

Большинство адаптивных методов для учета изменений статистики исходных данных используют так называемое окно. Окном называют последовательность символов, предшествующих  кодируемой букве, а длиной окна - количество символов в окне.

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

Рисунок 8  Схема перемещения окна при кодировании

 

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

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

Однако для всех методов адаптивного кодирования, которые приводятся в этой главе, справедлива следующая теорема:

Теорема. Величина средней длины кодового слова при адаптивном кодировании удовлетворяет неравенству

,

где H –  энтропия источника информации, C  –  константа, зависящая от размера алфавита источника и длины окна.

 

7.2 Адаптивный код Хаффмана

В 1978 г. Р. Галлагер предложил метод кодирования источников с неизвестной или меняющейся статистикой, основанный на коде Хаффмана, и поэтому названный адаптивным кодом Хаффмана.

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

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

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

3. По полученному распределению вероятностей строится код Хаффмана для алфавита A

4. Очередная буква кодируется при помощи  построенного кода.

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

Пример 7.2.1. Рассмотрим пример адаптивного кодирования с помощью метода Хаффмана для алфавита  и длины окна W=6 (см. рис. 9).

Рисунок 9 Кодирование адаптивным кодом Хаффмана

 

Рассмотрим подробно этапы кодирования сообщения.

Перед началом кодирования символы в окне встречаются со следующими частотами .  Тогда вероятности символов алфавита A оцениваются так

   

Построим код Хаффмана для этого распределения вероятностей и закодируем символы, входящие в окно построенным кодом (рис. 10а)

При кодировании буквы  (буква находится вне окна) частоты пока не изменились, поэтому  кодируем символ  кодовым символом 001.

a)

 

б)

 

в)

Рисунок 10 Построение адаптивного кода Хаффмана

 

Далее передвигаем окно на один символ вправо и снова подсчитываем частоты символов в окне  и оцениваем вероятности:

   

Строим код на основе полученных оценок вероятностного распределения (см. рис. 10 (б)) и кодируем очередной символ  другим кодовым словом - 00. В этом случае частота символа а3в окне увеличилась, соответственно уменьшилась длина его кодового слова.

Снова передвигаем окно на один символ вправо, подсчитываем частоты символов в окне  и оцениваем вероятности:

    

Строим код на основе полученных оценок вероятностного распределения (см. рис. 10 (в)) и кодируем очередной символ  кодовым словом - 101. Таким образом, сообщение  получаем кодовую последовательность 1 01 1 1 001 000 001 00 101.

 

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

Адаптивный код Хаффмана

Обозначим
w – окно
mas – массив вероятностей символов и кодовых слов

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

 

7.3 Код «Стопка книг»

Этот метод был предложен Б. Я. Рябко в 1980 году. Название метод получил по аналогии со стопкой книг, лежащей на столе. Обычно сверху стопки находятся книги, которые недавно использовались, а внизу стопки – книги, которые использовались давно, и после каждого обращения к стопке использованная книга кладется сверху стопки.

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

Пример 7.3.1. Приведем описание кода на примере алфавита . Статистика источника неизвестна. Пусть необходимо закодировать сообщение

  • Символ находится в третьей позиции начальной стопки, кодируется кодовым словом 110 и перемещается на первую позицию в стопке, при этом символы и
  • Следующий символ уже находится в первой позиции стопки, кодируется кодовым словом 0 и стопка не изменяется.
  • Символ находится в последней позиции стопки, кодируется кодовым словом 111 и перемещается на первую позицию в стопке, при этом символы , , смещаются на одну позицию вниз.
  • Следующий символ уже находится в первой позиции стопки, кодируется кодовым словом 0 и стопка не изменяется.
  • Символ находится во второй позиции стопки, кодируется кодовым словом 10 и перемещается на первую позицию в стопке, при этом символ смещается на одну позицию вниз.

Кодовое слово

Начальная «стопка»

Преобразования «стопки»

 

1

0

а1

а3

а3

а4

А4

а3

2

10

а2

а1

а1

а3

А3

а4

3

110

а3

а2

а2

а1

А1

а1

4

111

а4

а4

а4

а2

А2

а2

 

Рисунок 11 Кодирование методом «стопка книг»

 

Таким образом, закодированное сообщение имеет следующий вид:

 

 

 

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

При декодировании используется такая же «стопка книг», находящаяся первоначально в том же состоянии. Над «стопкой» проводятся такие же преобразования, что и при кодировании. Это гарантирует однозначное восстановление исходной последовательности.

 

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

Кодирование кодом «Стопка книг»

Обозначим

length – длина кодируемой строки

code – массив кодовых слов для позиции «стопки»

s_in – строка для кодирования

s_out – результат кодирования

S – строка, содержащая исходный алфавит

insert(T,S) – процедура, которая перемещает символ S[T] на первую позицию строки S, при этом сдвигая символы S[1], S[2], …,>S[T-1] на одну позицию вправо

 

length:=<длина s_in>

DO (i=1,…,length)

         T:=<номер символа s_in[i] в строке S>

         s_out:=s_out+code[T]

         insert(T,S)

OD