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

IF (P [i-1]≤q) Р [i]:=P [i-1]

ELSE j:=i

ОD

FI

ОD

Р [j]:= q

Процедура Down (n,j) формирует кодовые слова.

S:= С [j,*] (запоминание j-той строки матрицы элем. кодов в массив S)

L:= L[j]

DО (i=j,…,n-2) [10, с. 22].

В заключение данной главы можно сделать вывод, что при кодировании сообщений является то, что символы сообщения порождаются определенным источником информации. Источник является установленным целиком, в случае если предоставлено вероятностное представление процесса появления сообщений на выходе источника. Данное значит, то что в любой момент времени установлена возможность порождения источником любой очередности символов Р(x₁x₂x₃...x_L), L≥1. Такой источник именуется дискретным вероятностным источником.

Метод оптимального побуквенного кодирования был создан Д. Хаффманом. Оптимальный код Хаффмана имеет минимальную среднюю длину кодового слова между всех побуквенных кодов для предоставленного источника с алфавитом А={a₁,…,a_n} и вероятностями p_i =P(a_i).

3. Другие методы кодирования данных

3.1. Арифметический код

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

Проанализируем общую идею арифметического кодирования. Пусть дан источник, порождающий буквы из алфавита А={a₁,a₂,…,a_n} с вероятностями p_i=P(a_i), . Нужно закодировать очередность знаков предоставленного источника Х=х₁х₂х₃х_4.

1. Подсчитаем кумулятивные вероятности Q₀ ,Q₁,…,Q_n:

Q₀=0

Q₁=р₁

Q₂=р₁+р₂

Q₃=р₁+р₂+р₃

...

Q_n=р₁+р₂+…+р_n=1

1. Разделим интервал [Q₀,Q_n) (т.е. интервал [0,1)) таки образом, чтобы всякой букве начального алфавита отвечал свой интервал, равный ее вероятности (см. рис. 3.1):

---

a₁ [Q₀,Q₁)

a₂ [Q₁,Q₂)

a₃ [Q₂,Q₃)

a₄ [Q₃,Q₄)

...

a_n [Q_n-1,Q_n)

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

На рисунке 3.1 показан данный процесс для кодирования последовательности а₃а₂а₃…

Рис. 3.1 Схема арифметического кодирования [10, с. 30]

Для удобства вычислений введем дальнейшие обозначения:

l_i  нижняя грань отрезка, соответственного i-той букве начального сообщения;

h_i  верхняя грань этого отрезка;

r_i  длина отрезка [l_i, h_i), т.е. r_i = h_i  l_i.

Возьмем исходные значения данных величин:

l₀ = Q₀=0, h₀ = Q_k=1, r₀ = h₀  l₀=1

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

, , (3.1)

где m  порядковый номер кодируемой буквы в алфавите источника, m=1,...,n.

Этим образом, конечная длина интервала равна произведению вероятностей всех встретившихся знаков, а начало интервала находится в зависимости от порядка месторасположения знаков в кодируемой очередности.

Для конкретного декодирования начальной очередности можно брать разрядов двоичной записи любой точки из интервала [l_i,h_i), где r_k  длина интервала после кодирования k знаков источника [1, с. 164].

Рассмотрим кодирование безграничной очередности X=a₃a₂a₃a₁a₄... в алфавите A={a₁, a₂, a₃, a₄} с помощью арифметического кода. Пусть вероятности букв начального алфавита равны соответственно: р₁ = 0,1; р₂ =

---

= 0,4; р₃ = 0,2; р₄ = 0,3 с поддержкой арифметического кода. Пусть вероятности букв начального алфавита равны в соответствии с этим

Вычислим кумулятивные вероятности Q_i :

Q₀ = 0,0;

Q₁ =р₁ = 0,1;

Q₂ =р₁+р₂ = 0,5;

Q₃ =р₁+р₂+р₃ = 0,7;

Q₄ =р₁ +р₂ +р₃ + р₄ = 1 [10, с. 31].

Получим грани интервала, соответствующего первому знаку кодируемого сообщения а₃:

l₁ = l₀ + r₀·Q₂ = 0 + 1·0,5 = 0,5;

h₁ = l₀ + r₀·Q₃ = 0 + 1·0,7 = 0,7;

r₁ = h₁  l₁ = 0,7  0,5 = 0,2.

Для 2-го знака кодируемого сообщения а₂ грани интервала станут таковыми:

l₂ = l₁ + r₁·Q₁ = 0,5 + 0,2·0,1 = 0,52;

h₂ = l₁ + r₁·Q₂ = 0,5 + 0,2·0,5 = 0,6;

r₂ = h₂  l₂ = 0,6  0,52 = 0,08 и т.д.

В итоге всего объема вычислений получаем последующую очередность интервалов для сообщения а₃ а₂ а₃ а₁ а₄

В итоге всех вычислений получаем надлежащую очередность интервалов для сообщения

В начале [0,0; 1,0)

После рассмотрения а₃ [0,5; 0,7)

После рассмотрения а₂ [0,52; 0,6)

После рассмотрения а₃ [0,56; 0,576)

После рассмотрения а₁ [0,56; 0,5616)

После рассмотрения а₄ [0,56112; 0,5616)

Кодом очередности а₃ а₂ а₃ а₁ а₄ станет двоичная запись всякой точки из интервала [0,56112; 0,5616), например, 0,56112. Для однозначного декодирования берем lоg₂(r₅) = lоg₂(0,00048) = 12 разрядов, имеем 100011111010 [3, с. 328].

Этим образом, при арифметической кодировке сообщение представляется вещественными числами в интервале [0; 1]. По мере кодирования сообщения отображающий его интервал уменьшается, а численность битов для представления интервала растет. Очередные символы сообщения уменьшают значение интервала в зависимости от значений их вероятностей. Более вероятные символы делают это в меньшей степени, чем наименее вероятные, и следовательно, прибавляют меньше битов к итогу [10, с. 33].

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

---

3.2. Адаптивные методы кодирования: код Хаффмана, код «Стопка книг»

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

Основная масса адаптивных методов для учета перемен статистики начальных данных применяют так называемое окно. Окном именуют последовательность символов, предыдущих кодируемой букве, а длиной окна  количество символов в окне [10, с. 35].

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

Рис. 3.2 Схема перемещения окна при кодировании [10, с. 36]

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

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

Впрочем, для всех способов адаптивного кодирования, которые приводятся в данной главе, справедлива ниже указанная теорема:

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

, (3.2)

где Н – энтропия источника информации;

C – константа, зависящая от объема алфавита источника и длины окна.

Рассмотрим адаптивный код Хаффмана

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

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

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

---

Р(а₁)= q(а₁)/W, Р(а₂) =q(а₂)/W, ..., Р(а_n)= q(а_n)/W. (3.3)

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

Рассмотрим код «Стопка книг»

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

До начала кодирования буквы начального алфавита упорядочены случайным образом и всякой позиции в стопке присвоено свое кодовое слово, при этом 1-ой позиции стопки соответствует самое краткое кодовое слово, а последней позиции  самое большое кодовое слово. Следующий символ кодируется кодовым словом, подходящим номеру его позиции в стопке, и переставляется на 1-ую позицию в стопке. [10, с. 38].

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

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

Таблица 3.1 Кодирование методом «стопка книг» [10, с. 39].

---