Файл: Методы кодирования данных (Сущность и общие особенности представления данных).pdf

Но для многих языков (например, арабского, японского, китайского) 256 символов недостаточно, поэтому развитие кодировок продолжалось, что привело к появлению UNICODE^[6].

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

Кодирование информации (англ. information coding) — отображение данных на кодовые слова. Обычно в процессе кодирования информация преобразуется из формы, удобной для непосредственного использования, в форму, удобную для передачи, хранения или автоматической обработки. В более узком смысле кодированием информации называют представление информации в виде кода. Средством кодирования служит таблица соответствия знаковых систем, которая устанавливает взаимно однозначное соответствие между знаками или группами знаков двух различных знаковых систем^[7].

Пусть — множество исходных символов, — кодовый алфавит, — множество всех строк конечной длины из .

Код (англ. code) — отображение и так, что ^[8]

Существуют такие виды кодов:

1) Код фиксированной длины (англ. fixed-length code) — кодирование каждого символа производится с помощью строк одинаковой длины. Также он называется равномерным или блоковым кодом.

2) Код переменной длины (англ. variable-length code) — кодирование производится с помощью строк переменной длины. Также называется неравномерным кодом.

Префиксный код — код, в котором, никакое кодовое слово не является началом другого. Аналогично, можно определить постфиксный код — это код, в котором никакое кодовое слово не является концом другого. Предпочтение префиксным кодам отдается из-за того, что они упрощают декодирование. Поскольку никакое кодовое слово не выступает в роли префикса другого, кодовое слово, с которого начинается файл, определяется однозначно, как и все последующие кодовые слова^[9].

Преимущества префиксных кодов

- Однозначно декодируемый и разделимый

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

---

- Возможности декодировки сообщения, не получая его целиком, а по мере его поступления.

Недостатки префиксных кодов

- При появлении ошибок в кодовой комбинации, при определенных обстоятельствах, может привести к неправильному декодированию не только данной, но и последующей кодовой комбинации, в отличии от равномерных кодов, где ошибка в кодовой комбинации приводит к неправильному декодированию только ее^[10].

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

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

2. Основные методы кодирования данных

2.1 Метод Шеннона-Фано

Метод Шеннона-Фано (Shannon–Fano coding) является одним из первых методов кодирования информации. Впервые он был предложен независимо друг от друга Клодом Шенноном^[11] и Робертом Фано. Метод основан на представлении информации с помощью кода переменной длины, в котором символы, встречающиеся с большей частотой, кодируются кодом меньшей длины, а встречающиеся с большей частотой – кодом большей длины, используя таким образом избыточность сообщений, заключающуюся в неравномерном распределении частот символов, для кодирования. Причем такой код префиксный, то есть никакое кодовое слово не является началом (префиксом) какого-либо другого кодового слова. Свойство это влечет однозначную декодируемость такого кода.

Опишем теперь этот метод.

Кодированный текст будем полагать состоящим из символов некоторого алфавита (в двоичном случае, символ может представлять собой, например, один байт, тогда мощность алфавита равна 256). Сначала вычисляются частоты символов в тексте. Далее производится построение префиксного кода с помощью дерева. Его построение начинается с корня, которому ставится в соответствие весь алфавит. Он разбивается на два подмножества, суммарные частоты символов которых примерно одинаковы. Этим подмножествам ставятся в соответствие две вершины дерева второго яруса, являющиеся детьми корня.

---

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

Заметим, что разбиение множества элементов в некоторых случаях может быть произведено различными способами. При этом неудачный выбор разбиения может привести к неоптимальности кода. Из-за этого код Шеннона-Фано не является оптимальным в общем случае, хотя может быть оптимальным в частных случаях.

Структурируем алгоритм оптимального кодирования Шеннона-Фано:

1. Все символы алфавита^[12] упорядочиваются в порядке убывания вероятности их появления.
2. Кодируемые символы делятся на две равновероятные или приблизительно равновероятные подгруппы.
3. Каждому символу из верхней подгруппы присваивается код «0», а каждому символу из нижней подгруппы ‒ код «1».
4. Каждая из подгрупп снова делится на две равновероятные или приблизительно равновероятные подгруппы. При этом каждому символу из верхней подгруппы присваивается код «0», а из нижней ‒ «1».
5. Деление на подгруппы проводится до тех пор, пока в подгруппе не останется по одному символу.
6. Результирующие кодовые слова записываются слева направо по кодам подгрупп, соответствующих кодируемому символу.

Пример оптимального кодирования по методу Шеннона-Фано приведен в таблице 2.1.

Таблица 2.1 ‒ Кодирование по методу Шеннона-Фано

Символ алфавита	Вероятность	Шаги алгоритма					Количество элементарных символов	Кодовое слово
		1	2	3	4	5
	0,30	0 0,55	0 0,3				2	00
	0,25	0	1 0,25				2	01
	0,15	1	0 0,25	0 0,15			3	100
	0,1	1	0	1 0,1			3	101
	0,1	1 0,45	1 0,2	0 0,1			3	110
	0,05	1	1	1 0,1	0 0,05		4	1110
	0,04	1	1	1	1 0,05	0 0,04	5	11110
	0,01	1	1	1	1	1 0,01	5	11111

---

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

В коде Шеннона-Фано метод решения основы­вается на делении столбика вероятностей на две части, так чтобы сумма вероятностей сверху и снизу была примерно одинакова. Для полученных частей ставятся коды 0 и 1. Далее деление каждой полученной части повторяется. И так далее до того момента, когда образуются неделимые части. В таблице 2.2 представлена схема построения равно­мерного двоичного кода, в таблице 2.3 - схема Шеннона-Фано.

Таблица 2.2 – Схема построения равномерного двоичного кода

Символ	Вероятность	Код
XI	0.125	000
Х2	0.125	001
ХЗ	0.125	010
Х4	0.125	011
Х5	0.125	100
Х6	0.125	101
Х7	0.125	ПО
Х8	0.125	111

Среднее количество бит на символ:

Таблица 2.3 – Схема построения двоичного кода Шеннона-Фано^[13]

Символ	Вероят­ность	Код	Схема кодирования
XI	0.25	00	0	0
Х2	0.25	01		1
ХЗ	0.125	100	1	0	0
Х4	0.125	101			1
Х5	0.0625	1100		1	0	0
Х6	0.0625	1101				1
Х7	0.0625	1110			1	0
Х8	0.0625	1111				1

---

Среднее количество бит на символ:

Код составляется из полученных, по горизон­тали, в схеме кодирования нолей и единиц.

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

На сегодняшний день, метод Шеннона-Фано практически не используется и представляет лишь исторический интерес. Подмножеством кодов Шеннона-Фано являются коды Хаффмана.

2.2 Метод Хаффмена

Метод Хаффмана был впервые предложен в 1952 г^[14]. Этот метод похож на метод Шеннона-Фано.

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

1. Для каждого символа строится по листу дерева. Каждому листу ставится в соответствие вес равный частоте этого символа. Все листья добавляются в список свободных вершин.

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

3. Одно ребро инцидентное отцовской вершине помечается двоичной цифрой «0», а другое – двоичной цифрой «1».

4. Повторять шаги начиная с шага 2 до тех пор, пока в списке свободных вершин не останется ровно одна вершина. Она станет корнем дерева.

Кодом символа является последовательность меток ребер на пути от корня к листу, соответствующему этому символу.

Структурируем метод Хаффмана.

Алгоритм оптимального кодирования Хаффмана:

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

---