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

Арифметическое декодирование

Обозначим

l - массив нижних границ интервалов при кодировании

h - массив верхних границ интервалов при кодировании

r - массив длин интервалов

Q – массив для величин Q_i

length – количество закодированных символов,

value – значение из входного файла.

l [0] :=0; h [0] :=1; r [0] :=1;

value:=ReadCode(); (читаем код из файла)

DO (i=1,…,length)

DO (j=1,…,n)

l [i] = l [i-1] + r [i-1]·Q [j-1]

h [i] = l [i-1] + r [i-1]·Q [j]

r [i] = h [i] - l [i]

IF (( l [i] <= value ) и ( value< h [i] ) OD FI

OD

Write(a[i]) (пишем символ в выходной файл)

OD

Заметим, что при кодировании и декодировании для экономии памяти достаточно использовать не массивы, а переменные l, r и h.

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

· необходима арифметика с плавающей точкой теоретически неограниченной точности;

· результат кодирования становится известен только после окончания входного потока.

Для решения этих проблем реальные алгоритмы работают с целыми числами и оперируют с дробями, числитель и знаменатель которых являются целыми числами (например, знаменатель равен 10000h=65536, l₀=0, h₀=65535). При этом с потерей точности можно бороться, отслеживая сближение l_i и h_i и умножая числитель и знаменатель представляющей их дроби на одно и то же число, например на 2. С переполнением сверху можно бороться, записывая старшие биты l_i и h_i в файл только тогда, когда они перестают меняться (т.е. уже не участвуют в дальнейшем уточнении интервала), когда l_i и h_i одновременно находятся в верхней или нижней половине интервала.

6. адаптивные методы кодирования

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

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

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

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

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

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

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

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

,

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

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

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

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

1. Перед кодированием очередной буквы подсчитываются частоты появления в окне всех символов исходного алфавита А={a₁, a₂, ..., a_n}. Обозначим эти частоты как q(a₁), q(a₂), ..., q(a_n). Вероятности символов исходного алфавита оцениваются на основе значений частот символов в окне

P(a₁)= q(a₁)/W, P(a₂) =q(a₂)/W, ..., P(a_n)= q(a_n)/W.

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

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

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

Пример. Рассмотрим пример адаптивного кодирования с помощью метода Хаффмана для алфавита А={a₁, a₂, a₃, a₄} и длины окна W=6 (см. рис. 9).

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

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

При кодировании буквы a₃получаем следующие частоты встреч символов в окне: q(a₁)=3, q(a₂)=1, q(a₃)=1, q(a₄)=1. Тогда вероятности символов алфавита A оцениваются так

Строим код Хаффмана для полученного распределения вероятностей (см. рис. 10 (а)) и кодируем символ а₃ кодовым символом 001.

a)

Символы	Вероятности	Построение кода	Кодовые cлова
а1	1/2	1
а2	1/6	1/2 0
а3	1/6	1/3
а4	1/6

б)

Символы	Вероятности	Построение кода	Кодовые слова
а1	1/3	1
а2	1/6	1/3 2/3 0
а3	1/3
а4	1/6

в)

Символы	Вероятности	Построение кода	Кодовые слова
а1	1/3	1/2 1
а2		1/6 0
а3	1/2
а4	1/6

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

Далее передвигаем окно на один символ вправо и снова подсчитываем частоты встреч символов в окне q(a₁)=2, q(a₂)=1, q(a₃)=2, q(a₄)=1 и оцениваем вероятности:

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

Снова передвигаем окно на один символ вправо, подсчитываем частоты встреч символов в окне q(a₁)=2, q(a₂)=0, q(a₃)=3, q(a₄)=1 и оцениваем вероятности:

Строим код на основе полученных оценок вероятностного распределения (см. рис. 10 (в)) и кодируем очередной символа₂ кодовым словом - 101. Таким образом, после кодирования символов a₃a₃a₂ получаем кодовую последовательность 00100101.