Методы кодирования данных (Основные понятия

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

МОСКОВСКИЙ ФИНАНСОВО-ПРОМЫШЛЕННЫЙ УНИВЕРСИТЕТ

«УНИВЕРСИТЕТ»

Факультет Финансов

курсовая работа

По дисциплине
Технологии программирования

На тему
Методы кодирования данных

Работу выполнил (а) студент (ка)
группы	ОБИн-1410ГРД
Направление	ИСиТ
Профиль	Информационные системы и технологии
Гук Денис Михайлович
(Ф.И.О.)
Научный руководитель
(Ф.И.О.)

МОСКВА 2018 г.

СОДЕРЖАНИЕ

Введение 3

1. Кодирование целых чисел 5

2. Побуквенное кодирование 11

2.1. Основные понятия побуквенного кодирования 10

2.2. Метод оптимального побуквенного кодирования Д. Хаффмана 16

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

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

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

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

3.3. Словарные коды класса Lz 28

Заключение 33

Список литературы 35

Введение

Теория кодирования и теория информации появились в начале 20-го века. Начало развитию этих теорий как академических дисциплин положило возникновение в 1948 г. заметок К. Шеннона, которые положили основу для последующих изучений в данной сфере.

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

Кодирование данных – метод представления данных в удобном для сохранения и передачи варианте. В связи с развитием информационных технологий кодирование считается главным вопросом при решении самых различных задач программирования, подобных равно как:

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

Изучением методов кодирования данных занимались такие ученые как: Е.В. Курапова [10], Е.Ф. Березкин [2], Д.В. Ломакин [11], Ю.М. Штарьков [16], В.В. Бахтизин [1] и др.

Все выше изложенное и определяет актуальность данной темы курсовой работы.

Цель курсовой работы: рассмотреть методы кодирования данных.

Объект исследования: методы кодирования.

Предмет исследования методы кодирования данных в технологиях программирования.

Для достижения цели были поставлены следующие задачи:

1. Раскрыть особенности кодирования целых чисел.
2. Рассмотреть особенности побуквенного кодирования.
3. Изучить другие методы кодирования данных.

Структура и объем курсовой работы: работа состоит из введения, трех глав, заключения, списка литературы. Полный объем курсовой работы составляет 36 страниц.

1. Кодирование целых чисел

Рассмотрим семейство методов кодирования, не учитывающих вероятности возникновения символов источника. Так как все без исключения символы алфавита источника возможно пронумеровать, в таком случае станем считать, что алфавит источника складывается из целых чисел. Любому целому числу из конкретного спектра устанавливается в соответствие свое кодовое слово, по этой причине данную категорию методов также именуют представлением целых чисел (representation of integers) [10, с. 8].

Главная концепция кодирования основана на том, чтобы в отдельности кодировать порядок значения числа («экспоненту» ) и в отдельности – значащие цифры числа («мантиссу» ). Значащие цифры мантиссы начинаются со старшей отличной от нуля цифры, а порядок числа обусловливается местом старшей отличной от нуля цифры в двоичной записи числа. Равно как и при десятичной записи, порядок равен количеству чисел в записи числа в отсутствии предыдущих незначащих нулей [2, с. 143].

Выделяют 2 категории методов кодирования целых чисел. Условно их возможно разделить на:

• Fixed + Variable (фиксированная длина экспоненты + переменная длина мантиссы);
• Variable + Variable (переменная длина экспоненты + переменная длина мантиссы).

В кодах класса Fixed + Variable под запись значения порядка числа отводится фиксированное количество бит, а значение порядка числа определяет, сколько бит понадобится под запись мантиссы. Для кодирования целого числа следует осуществить с числом 2 процедуры: установление порядка числа и акцентирование бит мантиссы (возможно сохранять в памяти отделанную таблицу кодовых слов). Проанализируем процедуру построения кода данного класса на примере [6, с. 211].

Приведем пример. Пускай R = 15 – число бит исходного числа. Отведем E = 4 бита под экспоненту (порядок), т.к. R≤24. При записи мантиссы возможно сберечь один бит: никак не записывать первую единицу, т.к. это постоянно будет только единица. Таким образом, число бит мантиссы меньше на один бит, нежели количество бит для порядка.

Таблица 1.1 Код класса Fixed + Variable [10, с. 9]

Число	Двоичное представление	Кодовое слово	Длина кодового слова
0 1	000000000000000 000000000000001	0000 0001	4 4
2 3	000000000000010 000000000000011	0010 0 0010 1	5 5
4 5 6 7	000000000000100 000000000000101 000000000000110 000000000000111	0011 00 0011 01 0011 10 0011 11	6 6 6 6
8 9 10 … 15	000000000001000 000000000001001 000000000001010 … 000000000001111	0100 000 0100 001 0100 010 … 0100 111	7 7 7 .. 7
16 17 …	000000000010000 000000000010001 …	0101 0000 0101 0001 …	8 8 ..

Рассмотрим коды класса Variable + Variable

В качестве кода числа принимается двоичная очередность, выстроенная последующим способом: ряд нулей (число нулей равно значению порядка числа), далее единица как критерий окончания экспоненты неустойчивой длины, далее мантисса неустойчивой длины (равно как в кодах Fixed + Variable) [4, с. 119].

Рассмотрим образец построения кода данного класса (см. таблицу 1.2).

Таблица 1.2 Код класса Variable + Variable [10, с. 9]

число	двоичное представление	кодовое слово	длина кодового слова
1	2	3	4
0 1	00000000000 00000000001	1 0 1	1 2

Продолжение таблицы 1.2

1	2	3	4
2 3	00000000010 00000000011	00 1 0 00 1 1	4 4
4 5 6 7	00000000100 00000000101 00000000110 00000000111	000 1 00 000 1 01 000 1 10 000 1 11	6 6 6 6
8 9 10 …	00000001000 00000001001 00000001010 …	0000 1 000 0000 1 001 0000 1 010 …	8 8 8

В случае если в осмотренном ранее коде устранить кодовое слово для нуля, то в таком случае, возможно, сократить длины кодовых слов на один бит, сняв первый нуль. Подобным способом создается гамма-код Элиаса (γ-код Элиаса) (см. таблицу 1.3).

Таблица 1.3 Гамма-код Элиаса [10, с. 10]

число	кодовое слово	длина кодового слова
1	1	1
2 3	01 0 01 1	3 3
4 5 6 7	00 1 00 00 1 01 00 1 10 00 1 11	5 5 5 5
8 9 10 …	000 1 000 000 1 001 000 1 010 …	7 7 7

Иным примером кода класса Variable + Variable считается омега-код Элиаса (ω-код Элиаса). В нем 1-ое значение (кодовое слово для единицы) задается в отдельности. Прочие кодовые слова имеют структуру из очередности групп длиной , начинающихся с единицы. Окончание всей очередности задается нулевым битом. Протяженность первой группы равна 2 бита, протяженность любой последующей группы равна двоичному значению битов предыдущей группы плюс единица. Значение битов заключительной группы является окончательным значением всей последовательности групп, т.е. первые групп предназначаются только с целью для указания длины последней группы [7, с. 241].

Таблица 1.4 Омега-код Элиаса [10, с. 10]

Число	Кодовое слово		Длина кодового слова
1 2 3	0 10 0 11 0		1 3 3
4 5 6 7	10 100 0 10 101 0 10 110 0 10 111 0	6 6 6 6
8 9 .. 15	11 1000 0 11 1001 0 … 11 1111 0	7 7 .. 7
16 17 .. 31	10 100 10000 0 10 100 10001 0 … 10 100 11111 0	11 11 .. 11
32	10 101 100000 0	12

При кодировании создается сперва заключительная группа, далее предпоследняя и т.д., до тех пор, пока процесс не будет окончен. При декодировании, напротив, сперва считывается 1-ая группа, по значению ее битов обусловливается протяженность последующей группы, или итоговое значение кода, в случае следующая группа – 0 [9, с. 73].

Рассмотренные типы кодов имеют все шансы быть эффективными в последующих вариантах:

1. Вероятности чисел спадают с увеличением значений элементов и их распределение близко к этому: , при каждом x, т.е. небольшие числа попадаются чаще, чем крупные.

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

3. При применении в составе иных методик кодирования, к примеру, кодировании длин серий [13, с. 114].

Рассмотрим кодирование длин серий

Способ кодировки данных, известный равно как метод кодировки длин серий и представленный П. Элиасом, при построении применяет коды целых чисел. Входной поток для кодирования рассматривается как равно как очередность из нулей и единиц. Концепция кодирования состоит в том, чтобы кодировать очередности схожих элементов (к примеру, нулей) равно как целые числа, указывающие число элементов в этой очередности. Очередность схожих элементов именуется серией, число элементов в ней – длиной серии [15, с. 56].

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

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 бит [10, с. 11].

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

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

В кодах класса Fixed + Variable под запись значения порядка числа дается определенное число бит, а значение порядка числа устанавливает, сколько бит необходимо под запись мантиссы. Для кодирования целого числа нужно проделать с числом две определенные операции: нахождение порядка числа и выделение бит мантиссы (есть возможность сохранять в памяти готовую таблицу кодовых слов).

В кодах класса Variable + Variable в качестве кода числа принимается двоичная очередность, выстроенная последующим способом: ряд нулей (число нулей точно равно значению порядка числа), далее единица как критерий завершения экспоненты неустойчивой длины, далее мантисса переменной длины (как это реализуется в кодах Fixed + Variable).

2. Побуквенное кодирование

2.1. Основные понятия побуквенного кодирования

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

В случае если вероятностный источник с алфавитом А={a₁, a₂, ..., a_n} порождает знаки алфавита вне зависимости друг от друга, т.е. знание предыдущих символов не влияет на вероятность последующих, то такой источник именуется бернуллиевским. В таком случае для любой последовательности x₁x₂...x_L, L≥1, порождаемой источником, выполняется равенство:

P(x₁x₂...x_L ) = P(x₁)·P(x₂)·...·P(x_L), (2.1)

где P(x) – вероятность появления символа х,

Р(x₁x₂x₃...x_L) – вероятность появления последовательности x₁x₂x₃...x_L.

Для иного класса источников (марковских) имеется статистическая связь среди порождаемых символов. В последующем мы будем анализировать кодирование стационарных (с неизменным распределением вероятностей) бернуллиевских дискретных источников без памяти [17, с. 117].

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

. (2.2)

Энтропия охарактеризовывает меру неопределенности выбора для предоставленного источника.

Приведем пример. В случае если А={a₁,a₂}, p₁=0, p₂ =1, т.е. источник имеет возможность породить лишь только знак a₂, то неопределенности нету, энтропия H(p₁,p₂)=0 [16, с. 82].

Источник с равновероятными символами А={a₁,a₂}, p₁ =1/2, p₂ =1/2, станет иметь наибольшую энтропию H(p₁,p₂)=1.

Величина называется энтропией на символ последовательности длины L, где A^L  множество всех последовательностей длины L в алфавите A, x=(x₁,x₂,...,x_L)  последовательность L букв дискретного cтационарного источника. Обозначим через предел энтропии H_L при L  . Данное значение именуют предельной энтропией источника. Показано, собственно, что для стационарного бернуллиевского источника:

. (2.3)

Для практических применений принципиально, дабы коды сообщений имели по возможности кратчайшую длину [14, с. 77].

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

Средней длиной кодового слова именуется величина , которая демонстрирует среднее количество кодовых букв на 1-ну букву источника.

Приведем пример. Пускай есть 2-ва источника с одинаковым алфавитом А={a₁,a₂,a₃} и различными вероятностными распределениями P₁={1/3, 1/3, 1/3}, P₂={1/4, 1/4, 1/2}, которые кодируются одинаковым кодом:

. (2.4)

Средняя длина кодового слова для различных источников станет разной:

L_ср(P₁)=1/3^.2 + 1/3^.3 + 1/3^.2= 7/3 ≈2.33;

L_ср(P₂)=1/4^.2 + 1/4^.3 + 1/2^.2= 9/4 =2.25.

Побуквенный разделимый код именуется оптимальным, в случае если средняя длина кодового слова мала между всех побуквенных разделимых кодов для предоставленного рассредотачивания возможностей символов [12, с. 32].

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

. (2.5)

Избыточность кода – есть показатель качества кода, подходящий код имеет минимальную избыточность. Задача действенного неискажающего сжатия заключается в построении кодов с минимальной избыточностью, у коих средняя длина кодового слова близка к энтропии источника. К этим кодам относятся традиционные коды Хаффмана, Шеннона, Фано, Гилберта-Мура и арифметический код [10, с. 17].

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

Теорема 1 (Шеннон). Для источника с алфавитом А={a₁,…,a_n} и вероятностями p_i =P(a_i), и любого разделимого побуквенного кода средняя длина кодового слова всякий раз не меньше энтропии:

L_cp ≥ H(p₁,…,p_n) (2.6)

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

L_cp < H(p₁,…,p_n)+1 (2.7)

Возможно получить больше крепкие итоги, в случае если кодовые слова приписывать не отдельными буквами, а блоками из L букв источника. Так, для неравномерных блоковых кодов справедлива приведенная ниже теорема.

Теорема 2. Пусть H_L  энтропия на букву в блоке длины L дискретного источник. Тогда есть префиксный код для кодировки блоков длины L, такой, что средняя длина кодового слова L_cp станет удовлетворять неравенствам:

. (2.8)

Отметим, что в случае бернуллиевского стационарного источника для всякого >0 возможно избрать довольно большущее L, дабы размер L_cp удовлетворял неравенствам:

, (2.9)

и левое неравенство для L_cp ни разу не нарушается для разделимого кода.

Приведем кое-какие качества, которыми владеет всякий подходящий побуквенный код [8, с. 186].

Лемма 1. Для рационального кода с длинами кодовых слов L₁,…,L_n: правильно соответствие L₁≤L₂≤…≤L_{n ,} если p₁≥p₂≥…≥p_n.

Подтверждение (от противного): Пусть имеется i и j, что L_i>L_j при p_i>p_j. Отсюда будем иметь:

L_ip_i+L_jp_j=

=L_ip_i+L_jp_j+L_ip_j+L_jp_i-L_ip_j-L_jp_i=

=p_i(L_i-L_j)-p_j(L_i-L_j)+L_jp_i+L_ip_j=

=(p_i-p_j)(L_i-L_j) +L_ip_j+L_jp_i>L_ip_j+L_jp_i,

т.е. в случае если заменим между собой L_i и L_j, то получим код, имеющий наименьшую среднюю длину кодового слова, собственно, что противоречит с оптимальности кода. Лемма 1 подтверждена.

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

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

Этим образом, новая схема кодирования также считается префиксной, при этом с наименьшей средней длиной кодового слова , что собственно противоречит оптимальности начальной схемы кодировки [5, с. 141].

Пусть теперь 2 кодовых слова и наибольшей длины различаются не в конечном разряде, т.е. , , , . Причем , не считаются префиксами для иных кодовых слов и напротив. Тогда новая схема также считается префиксной, при этом , что противоречит оптимальности начальной схемы кодировки. Лемма 2 подтверждена [10, с. 19].

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

2.2. Метод оптимального побуквенного кодирования Д. Хаффмана

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

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

1. Упорядочим знаки начального алфавита А={a₁,…,a_n} по убыванию их вероятностей p₁≥p₂≥…≥p_n.
2. Если А={a₁,a₂}, то a₁0, a₂1.
3. Если А={a₁,…,a_j,…,a_n} и известны коды <a_j  b_j >, j = 1,…,n, то для алфавита {a₁,…a_j^/, a_j^//…,a_n} с новыми символами a_j^/ и a_j^// вместо a_j, и вероятностями p(a_j)=p(a_j^/)+ p(a_j^//), код символа a_j заменяется на коды a_j^/  b_j0, a_j^// b_j1 [10, с. 19].

Пример. Пусть дан алфавит A={a₁, a₂, a₃, a₄, a₅, a₆} с вероятностями

p₁=0,36, p₂=0,18, p₃=0,18, p₄=0,12, p₅=0,09, p₆=0,07.

Тут знаки источника уже упорядочены в согласовании с их вероятностями. Станем складывать 2 меньшие вероятности и включать суммарную вероятность на соответствующее место в упорядоченном списке вероятностей до тех пор, пока в списке не останется 2 символа. Тогда закодируем эти 2 символа 0 и 1. Дальше кодовые слова достраиваются, как указано на рисунке 2.1.

Рис. 2.1 Процесс построения кода Хаффмана [10, с. 20]

Таблица 2.1 Код Хаффмана [10, с. 20]

ai	pi	Li	кодовое слово
a1 a2 a3 a4 a5 a6	0,36 0,18 0,18 0,12 0,09 0,07	2 3 3 4 4 4	1 000 001 011 0100 0101

Рассчитаем среднюю длину, построенного кода Хаффмана:

L_ср(P)=1^.0,36 + 3^.0,18 + 3^.0,18 + 3^.0,12 + 4^.0,09 + 4^.0.07 =2,44,

при этом энтропия этого источника:

H(p₁,…,p₆) = − 0,36^.log0,36 − 2^.0,18^.log0,18 −

− 0,12^.log0,12 − 0,09^.log0,09 − 0,07log0,07=2,37

Код Хаффмана как правило основывается и хранится в облике двоичного дерева, в листьях которого присутствуют знаки алфавита, а на «ветвях» – 0 или же 1. Тогда уникальным кодом символа является путь от корня дерева к к данному символу, по которому все 0 и 1 объединяются в одну уникальную последовательность (рис. 2.2).

Рис. 2.2 Кодовое дерево для кода Хаффмана [10, с. 20]

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

Построение оптимального кода Хаффмана (n, P).

Обозначим:

• n – количество символов исходного алфавита;
• P – массив вероятностей, упорядоченных по убыванию;
• С – матрица элементарных кодов;
• L – массив длин кодовых слов.

Huffmаn (n,P)

IF (n=2) С [1,1]:= 0, L [1]:= 1

С [2,1]:=1, L [2]:=1

ELSE q:= Р [n-1]+P [n]

j:= Up (n,q) (поиск и вставка суммы)

Huffmаn (n-1,Р)

Dоwn (n,j) (достраивание кодов)

FI

Функция Uр (n,q) находит в массиве Р место, куда поставить число q, и вставляет его, сдвигая вниз другие элементы.

DО (i=n-1, n-2,…,2)

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].

№ п/п	Кодовое слово	Начальная «стопка»	Преобразования «стопки»
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

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

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

При декодировании применяется эта же «стопка книг», оказавшаяся изначально в том же состоянии. Над «стопкой» ведутся эти же преобразования, что и при кодировании. Это гарантирует идентичное восстановление начальной очередности [10, с. 40].

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

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

Код «Стопка книг» получил название по аналогии со стопкой книг, лежащей на столе. Как правило, сверху стопки присутствуют книги, которые не так давно применялись, а понизу стопки – книги, которые применялись давным-давно, и впоследствии всякого обращения к стопке использованная книга кладется сверху стопки.

3.3. Словарные коды класса Lz

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

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

Словарные коды активно изучаются и конструируются, начиная с 1977 года, когда возникло описание 1-го метода, разработанного А. Лемпелом и Я. Зивом. В данное время есть большое количество методов, объединенных в класс LZ-кодов, которые представляют собой всевозможные трансформации метода Лемпела-Зива [10, с. 45].

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

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

По методике организации хранения и розыска слов словарные методы возможно поделить на 2-ве большие группы:

• алгоритмы, осуществляющие поиск слов в какой-нибудь части раньше закодированного текста, именуемой окном;
• алгоритмы, использующие адаптивный словарь, который подключает раньше встретившиеся слова. В случае если словарь заполняется до завершения процесса кодирования, то в кое-каких методах он обновляется (на место ранее встретившихся слов записываются новые), а в кое-каких кодирование длится без обновления словаря.

Алгоритмы класса LZ отличны размерами окна, способами кодирования слов, алгоритмами обновления словаря и т.п. Все обозначенные факторы воздействуют и на свойства данных способов: скорость кодирования, объем требуемой памяти и уровень сжатия данных, всевозможные для различных алгоритмов. Но в целом методы из класса LZ представляют значительное практическое внимание и дают возможность довольно действенно сжимать данные с неизвестной статистикой [10, с. 46].

Рассмотрим кодирование с применением скользящего окна.

Выделим главные этапы кодирования сообщения Х=х₁х₂х₃х₄…, которое порождается некоторым источником информации с алфавитом А. Пусть используется окно длины W, т.е. при кодировании символа x_i исходной последовательности учитываются W предыдущих символов:

Вначале происходит поиск в окне символа х₁. Если символ не находится, тогда в качестве кода происходит передача 0 как признак того, что этого символа нету в окне и двоичное представление х₁.

В случае если символ х₁ отыскан, то происходит поиск в окне слова х₁х₂, начинающегося с сего знака. В случае если слово х₁х₂ есть в окне, то происходит поиск слова х₁х₂х₃ , потом х₁х₂х₃х₄ и так далее, до тех пор пока не будет разыскано слово, состоящее из наибольшего числа входящих символов в порядке их появления. В данном случае в качестве кода передается 1 и пара чисел (i, j), показывающая позицию найденного слова в окне (i – номер позиции окна, с которой начинается это слово, j – длина данного слова, позиции в окне нумеруются справа налево). Вслед за тем окно двигается на j символов вправо по тексту и кодирование продолжается.

Для кодирования чисел (i, j) можно использовать рассмотренные раньше коды целых чисел.

Приведем пример. Пускай алфавит источника А={а, b, с}, длина окна W=6. Нужно закодировать начальное сообщение bababaabacabac. (см. рис. 3.3)

Рис. 3.3. Кодирование последовательности bаbаbааbаcаbаc [10, с. 47].

После окончания кодирования 1-ых 6-ти букв окно примет вид bababa.

• Дальше проверяется наличность в окне буквы а. Она найдена, добавляем к ней b, ищем в окне ab. Данная пара имеется в окне, добавляем букву а, делаем поиск аbа. Данное слово есть в окне, добавляется букву с, ищем abac. Данного слова нет в окне, тогда происходит кодирование aba кодовой комбинацией (1,3,3), где 1– признак того, что слово есть в «окне», 3– номер позиции в окне, с которой начинается данное слово, 3 – длина данное слова.
• Далее окно передвигается на три символа вправо и происходит поиск в окне букву с. Ее нет в данном окне, посему кодируется комбинацией (0, «с»), где 0 – признак того, что буквы нет в данном окне, «с» – двоичное представление буквы. Окно передвигается на один символ вправо.
• Производится поиск в окне букву а, она найдена, добавляется к ней b, производится поиск в окне ab. Данная пара есть в окне, добавляется буква а, производится поиск аbа. Данное слово имеется в окне, добавляется буква с, производится поиск аbаc. Это слово имеется в окне, тогда кодируется аbас кодовой комбинацией (1, 4, 4), где 1 – признак того, что слово есть в окне, 4 –номер позиции в окне, с которой начинается данное слово, 4 – длина данного слова [10, с. 48].

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

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

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

Код «Стопка книг» получил название по аналогии со стопкой книг, лежащей на столе. Как правило, сверху стопки присутствуют книги, которые не так давно применялись, а понизу стопки – книги, которые применялись давным-давно, и впоследствии всякого обращения к стопке использованная книга кладется сверху стопки.

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

Заключение

В результате нашего исследования мы пришли к следующим выводам:

1. Кодирование целых чисел осуществляется с использованием группы метод кодирования целых чисел Fixed + Variable и Variable + Variable.

В кодах класса Fixed + Variable под запись значения порядка числа дается определенное число бит, а значение порядка числа устанавливает, сколько бит необходимо под запись мантиссы. Для кодирования целого числа нужно проделать с числом две определенные операции: нахождение порядка числа и выделение бит мантиссы (есть возможность сохранять в памяти готовую таблицу кодовых слов).

В кодах класса Variable + Variable в качестве кода числа принимается двоичная очередность, выстроенная последующим способом: ряд нулей (число нулей точно равно значению порядка числа), далее единица как критерий завершения экспоненты неустойчивой длины, далее мантисса переменной длины (как это реализуется в кодах Fixed + Variable).

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

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

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

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

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

Код «Стопка книг» получил название по аналогии со стопкой книг, лежащей на столе. Как правило, сверху стопки присутствуют книги, которые не так давно применялись, а понизу стопки – книги, которые применялись давным-давно, и впоследствии всякого обращения к стопке использованная книга кладется сверху стопки.

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

Список литературы

1. Бахтизин В.В. Технологии разработки программного обеспечения / В.В. Бахтизин. – Минск: БГУИР, 2010. – 267 с.
2. Березкин Е.Ф. Основы теории информации и кодирования / Е.Ф. Березкин. – М.: НИЯУ МИФИ, 2010. – 312 с.
3. Брауде Э. Технология разработки программного обеспечения / Э. Брауде. – СПб.: Питер, 2004. – 655 с.
4. Вернер М. Основы кодирования / М. Вернер. – М.: Техносфера, 2004. – 288 с.
5. Верещагин Н.К. Информация, кодирование и предсказание / Н.К. Верещагин. – М.: ФМОП, МЦНМО, 2012. – 236 с.
6. Витерби А.Д. Принципы цифровой связи и кодирования / А.Д. Витерби. – М.: Радио и связь, 1982. – 536 с.
7. Гагарина Л.Г. Технология разработки программного обеспечения / Л.Г. Гагарина. – М.: Форум, ИНФРА-М, 2008. – 400 с.
8. Кудряшов Б.Д. Теория информации / Б.Д. Кудряшов. – СПб.: Питер, 2009. – 320 с.
9. Кузьмин И.В. Основы теории информации и кодирования / И.В. Кузьмин. – К.: Вища шк., 2000. – 238 с.
10. Курапова Е.В. Основные методы кодирования данных / Е.В. Курапова. – Новосибирск: СибГУТИ, 2010. – 62 с.
11. Ломакин Д.В. Прикладная теория информации и кодирования / Д.В. Ломакин. – Горький: Горьковский политехнический институт, 2015. – 219 с.
12. Мирошниченко Е.А. Технология программирования / Е.А. Мирошниченко. – Томск: ТПУ, 2008. – 124 с.
13. Панин В.В. Основы теории информации. Часть 2. Введение в теорию кодирования / В.В. Панин. – М.: МИФИ, ФГУП ИСС, 2004. – 391 с.
14. Сидельников В.М. Теория кодирования. Справочник по принципам и методам кодирования / В.М. Сидельников. – М.: МГУ, 2006. – 289 с.
15. Хэмминг Р.В. Теория кодирования и теория информации / Р.В. Хэмминг. – М.: Радио и связь, 1983. – 176 с.
16. Штарьков Ю.М. Универсальное кодирование. Теория и алгоритмы / Ю.М. Штарьков. – М.: ФИЗМАТЛИТ, 2013. – 288 с.
17. Цымбал В.П. Задачник по теории информации и кодированию / В.П. Цымбал. – К.: Вища шк., 1992. – 263 с.