Файл: Методы кодирования данных (Понятие кодирования).pdf

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

Рассматриваемые виды кодов могут быть действенны в определенных ситуациях:

1. Вероятности чисел убывают с ростом значений элементов и их распределение близко к P(x)≥P(x+1), при любом x. Точнее маленькие числа встречаются чаще больших.
2. Диапазон значений входных элементов не ограничен или неизвестен. Например, при кодировании 32-битовых чисел реально большинство чисел маленькие, но могут быть и большие.
3. При использовании в составе других схем кодирования, например, кодирование длин серий.

2.3 Кодирование длин серий

Метод кодирования информации, известный как метод кодирования длин серий, его предложил П. Элиасом, при построении использует коды целых чисел [6]. Входным потоком для кодирования является последовательность из нулей и единиц. Идея кодирования заключается в кодирование последовательности одинаковых элементов, к примеру, нулей. Последовательность одинаковых элементов называется серией, количество элементов в ней – длиной серии.

Желательно рассмотреть пример:

Исходную последовательность (общая длина 31бит) можно разбить на серии, а затем закодировать их длины.

000000 1 00000 1 0000000 1 1 00000000 1

Используется, например, γ-код Элиаса. Поскольку в коде нет кодового слова для нуля, то придется кодировать длину серии +1, точнее последовательность 7 6 8 1 9:

7 6 8 1 9 ⇒ 00111 00110 0001000 1 0001001

Длина полученной кодовой последовательности равна 25 бит.

Метод длин серий эффективен для кодирования данных, имющие длинные последовательности одинаковых бит.

Глава 3. Адаптивные методы кодирования

Адаптивные модификации методов кодирования применяют в том случае, когда при решении реальных задач истинные значения вероятностей источника, в большинстве случаев, неизвестны или могут изменяться с течением времени. Многие адаптивные методы для учета изменений исходных данных используют окно – это последовательность символов, предшествующих кодируемой букве [7]. А количество символов в этом окне называют длиной окна. Окно имеет фиксированную длину и передвигается вправо на одну единицу после каждой буквы. Из этого выходит, что для одной буквы код строится с учетом информации из окна. На рисунке 2 показ этот процесс.

кодируемый символ

... a₃ a₂ a₅ a₂ a₄ a₁ a₁ a₃ a₂ a₂ a₂ a₄ a₃ a₁ a₂ ...

... a₃ a₂ a₅ a₂ a₄ a₁ a₁ a₃ a₂ a₂ a₂ a₄ a₃ a₁ a₂ ...

кодируемый символ

... a₃ a₂ a₅ a₂ a₄ a₁ a₁ a₃ a₂ a₂ a₂ a₄ a₃ a₁ a₂ ...

кодируемый символ

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

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

При рассматриваемом методе кодирования оценка избыточности становится непростой математической задачей, так как избыточность состоит из двух компонентов:

• Избыточности копирования;
• Избыточности, возникающей при рассмотрении оценки вероятностей появления символов.

Благодаря этим параметрам действенность методов адаптивного кодирования обычно определяют экспериментальным путем.

Для всех методов адаптивного кодирования существует следующая теорема: Величина средней длины кодового слова при адаптивном кодировании удовлетворяет неравенству L_cp ≤ H+C,

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

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

Метод кодирования источников с меняющейся статистикой был предложен Р. Галлагером в 1978 г., и был основан на коде Хаффмана, поэтому и получил название «Адаптивный код Хаффмана» [8].

Рассматриваемый код используется во многих методах сжатия данных в роли составной части. Кодирование происходит на основе информации из окна длины 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.

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

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

кодируемый символ

... a₁ a₂ a₁ a₁ a₃ a₄ a₃ a₃ a₂ ...

... a₁ a₂ a₁ a₁ a₃ a₄ a₃ a₃ a₂ ...

кодируемый символ

... a₁ a₂ a₁ a₁ a₃ a₄ a₃ a₃ a₂ ...

кодируемый символ

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

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

P(a₁)= , P(a₂)= , P(a₃)= , P(a₄)= .

На рисунке 4а) построен код Хаффмана для полученного распределения вероятностей и кодируется символ а₃ с помощью кодового символа 001.

a)

б)

в)

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

На следующем шаге окно сдвигается на один знак вправо и обновляется подсчет частоты встреч символов в окне q(a₁) = 2, q(a₂) = 1, q(a₃) = 2, q(a₄) = 1 и оценивается вероятность:

P(a₁)= , P(a₂)= , P(a₃)= , P(a₄)= .

Далее происходит построение кода на основе полученного результата вероятного распределения, что представлено на рисунке 4б), кодируется символ а₃ кодовым словом «00». Следует увеличение частоты встречи символа а₃, соответственно длина кодового слова уменьшилась.

После окно снова движется вправо на один символ, что приводит к изменению частоты символов в окне q(a₁)=2, q(a₂)=0, q(a₃)=3, q(a₄)=1. Происходит оценка вероятности: P(a₁)= , P(a₂)=0 , P(a₃)= , P(a₄)= .

На рисунке 4в) представлен код, построенный на основе полученных оценок вероятностей. Происходит кодирование символа а₂ кодовым словом 101. В итоге выходит кодовая последовательность 00100101.

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

Обозначение:

w – окно;

mas – массив вероятностей символов и кодовых слов.

DO (i=1,…n) w[i]:=a[i] OD \\заполнение окна символами алфавита

DO (not EOF) \\ до конца входного файла

DO (i=1,…,n) mas[i].p:=0 OD

DO (i=1,…,n) mas[w[i]].p:= mas[w[i]].p +1 OD \\частоты встречи

символов в окне

DO (i=1,…,n) mas[w[i]].p:= mas[w[i]].p/n OD \\вероятности символов

в окне

Сортировка(mas)

DO (i=1,…,n) \\определение количества

IF (mas[i].p=0) OD ненулевых вероятностей

OD

Huffman(i,P) \\построение кода Хаффмана

C:=Read( ) \\чтение следующий символ из файла

Write(mas[C].code) \\код символа – в выходной файл

DO (i=1,…,n-1) w[i]:= w[i+1] OD

w[n]:=C \\включение в окно текущего символа

OD

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

Метод «Стопка книг» был предложен Рябко Б.Я. в 1980 г. Благодаря аналогии со стопкой книг, код получил свое название [9]. Чем раньше использовалась книга, тем выше она лежит, и каждый раз использованная книга кладется сверху.

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

Описание кода можно представить с помощью алфавита A={a₁, a₂, a₃, a₄}. Пусть кодируется сообщение а₃а₃а₄а₄а₃.

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

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

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

110 0   111 0 10 …

а₃ а₃ а₄ а₄ a₃

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

Декодирование происходит по тому же принципу «стопки книг». При этом процессе производятся те же операции, что и при кодировании. Что позволяет восстановить, в случае необходимости, исходную последовательность.