Файл: Методы кодирования данных (Сущность и общие особенности представления данных).pdf
Добавлен: 27.06.2023
Просмотров: 92
Скачиваний: 3
На практике не используют многократное выписывание символов алфавита и их упорядочивание. Обходятся построением кодового дерева так как это показано в таблице 2.4. Верхние ветви кодового дерева кодируются как 0, нижние ‒ 1. Кодирование каждой буквы проводится путем считывания значений (0 или 1) ответвлений, которые находятся на пути от корня кодового дерева (точки с вероятностью 1), до вершин, соответствующих каждому символу алфавита.
Таблица 2.4 ‒ Кодирование по методу Хаффмана
|
Символ алфавита
|
Вероятность
|
Кодовое дерево |
Количество элементарных символов
|
Кодовое слово |
||||||
|
|
0,30 |
0 |
F (0,55) |
2 |
00 |
|||||
|
|
0,25 |
1 |
0 |
G (1) |
2 |
01 |
||||
|
|
0,15 |
0 |
D (0,25) |
0 |
1 |
3 |
100 |
|||
|
|
0,1 |
1 |
C (0,2) |
E (0,45) |
3 |
101 |
||||
|
|
0,1 |
0 0 |
1 |
1 |
3 |
110 |
||||
|
|
0,05 |
0 |
1 |
B (0,1) |
4 |
1110 |
||||
|
|
0,04 |
A (0,05) |
5 |
11110 |
||||||
|
|
0,01 |
1 |
5 |
11111 |
||||||
Код Дэвида Хаффмана основан на построении дерева вероятностей. В столбце сортированных вероятностей складываются два последних значения. Полученный результат помещается в этот же столбец с учётом сортировки, а также записывается код прежней позиции слагаемых. Так продолжается до получения единственного элемента в столбце. Схема построения кода Хаффмана представлена на рисунке 2.1.
Код Хаффмана по схеме на рисунке 2.1 составляется из элементов кода при движении по веткам до номера позиции символа, код которого требуется построить.
Рис. 2.1 – Код Хаффмана
Таблица 2.5 – Метод Хаффмана для сообщения 8 символов
|
Символ |
Вероятность |
Код |
|
XI |
0.25 |
10 |
|
Х2 |
0.25 |
11 |
|
ХЗ |
0.125 |
010 |
|
Х4 |
0.125 |
011 |
|
Х5 |
0.0625 |
0010 |
|
Х6 |
0.0625 |
0011 |
|
Х7 |
0.0625 |
0000 |
|
Х8 |
0.0625 |
0001 |
Метод Хаффмана находит широкое применение как при кодировании фотографий (в составе стандарта JPEG), видео (в составе стандартов MPEG), так и в архиваторах (например, в PKZIP). Хотя в качестве самостоятельного алгоритма кодирования метод применяется редко, чаще он используется в комплексе с другими алгоритмами кодирования.
2.3. Сравнение методов оптимального кодирования
Методика Шеннона–Фано не всегда приводит к однозначному построению кода.
Ведь при разбиении на подгруппы на 1-й итерации можно сделать большей по вероятности как верхнюю, так и нижнюю подгруппу. В результате среднее число символов на букву окажется другим.
Таким образом, построенный код может оказаться не самым лучшим.
От указанного недостатка свободна методика Хаффмана. Она гарантирует однозначное построение кода с наименьшим для данного распределения вероятностей средним числом символов на букву.
Метод Хаффмана производит идеальное кодирование (то есть, кодирует данные до их энтропии), если вероятности символов точно равны отрицательным степеням числа 2. Результаты эффективного кодирования по методу Хаффмана всегда лучше результатов кодирования по методу Шеннона-Фано.
Предложенный Хаффманом алгоритм построения оптимальных неравномерных кодов – одно из самых важных достижений теории информации, как с теоретической, так и с прикладной точек зрения. Этот весьма популярный алгоритм служит основой многих компьютерных программ кодирования текстовой и графической информации. Некоторые из них используют непосредственно алгоритм Хаффмана, а другие берут его в качестве одной из ступеней многоуровневого процесса кодирования.
Этот алгоритм был придуман в 1952 г. студентом Дэвидом Хаффманом в процессе выполнения домашнего задания.
Кодирование методом Хаффмана называют двухпроходным, так как его реализация распадается на два этапа[15]:
- на первом этапе реализуется алгоритм Хаффмана,
- а на втором этапе строится дерево Хаффмана.
Дальнейшим развитием идеи, лежащей в основе метода Хаффмана, является арифметическое кодирование.
Отличие этого алгоритма в том, что он работает с непрерывным отрезком, который мы будем называть рабочим отрезком. Вначале объявим рабочим отрезком единичный отрезок. Расположим на нем точки таким образом, что отношения длин образованных подотрезков к длине всего рабочего отрезка будут равны частотам символов, а каждый такой подотрезок будет соответствовать одному символу.
Теперь возьмем очередной символ кодируемого текста, выберем соответствующий ему отрезок среди только что сформированных и объявим его рабочим. Разобьем и его вышеприведенным образом и т.д. Отрезок будет постоянно уменьшаться. После того, как мы таким образом обработаем все символы кодируемого текста, возьмем любое число, принадлежащее рабочему отрезку. Оно и будет закодированным сообщением.
Метод арифметического кодирования позволяет достичь высокого коэффициента кодирования.
Метод PPM (prediction by partial matching) представляет собой метод контекстнозависимого моделирования ограниченного порядка. Он основан на оценке вероятности символа в зависимости от контекста, т.е. от символов, стоящих перед ним. Если для этой оценки используется контекст длины n, то говорят об использовании контекстноограниченной модели порядка n.
В рамках модели порядка n, при n > 0 , оценка вероятности символа c равна отношению количества раз, которое встретилась конкатенация данного контекста с символом c к количеству раз, которое встретился данный контекст. При использовании модели нулевого порядка, оценка вероятности равна частоте, с которой данный символ встретился в тексте. При использовании модели порядка –1, вероятность каждого символа оценивается как , где A – алфавит.
Например, пусть следует закодировать строку 121123123122123 над алфавитом {1,2,3}. Оценим вероятность последнего символа.
В модели порядка 2 вероятность символа «3» оценивается как 2/4, поскольку контекст длины 2 встретился в строке 4 раза, причем 2 раза в этом контексте имел место символ «3». Модель первого порядка оценивает вероятность символа «3» как 2/5. Для модели порядка 0 эта вероятность оценивается как 1/5, а для модели порядка –1 – как 1/3.
Рассматриваемый алгоритм работает следующим образом. К алфавиту кодируемой последовательности добавляется специальный символ – код ухода «ESC». Вводится понятие вероятности ухода, т.е. вероятности, которую имеют еще не появлявшиеся символы. При этом любая модель должна выдавать отличную от нуля оценку вероятности ухода.
Пусть задан максимальный порядок m. Для кодирования очередного символа рассматривается модель порядка m. Если она выдает ненулевую оценку вероятности этого символа, то эта вероятность и используется в качестве исходных данных для его кодирования. Если же модель не может произвести оценку вероятности данного символа, либо эта оценка равна нулю, выдается код ухода и производится следующая попытка оценки вероятности этого символа с помощью модели порядка m – 1.
Если и эта модель не может произвести такую оценку, то применяется модель порядка m – 2 и т.д. Так продолжается до тех пор, пока не будет получена ненулевая оценка вероятности. Получение такой оценки гарантируется моделью порядка –1. В результате, каждый символ может предваряться несколькими символами ухода. При этом символы кодируются, например, с помощью кода Хаффмана, используя вместо частоты символа, полученную оценку вероятности.
Метод PPM демонстрирует один из самых высоких коэффициентов кодирования, прежде всего, для текстов на естественном языке, что обуславливает весьма широкое его применение. Мы также можем предложить его использовать для кодирования текстов на естественном языке перед кодированием с помощью различных криптоалгоритмов, например, предложенных в работах. Недостатком метода PPM является медленное декодирование[16].
Заключение
Для достижения цели курсовой работы были решены следующие задачи:
1. Дано определение представления данных
Решение данной задачи позволило сформулировать следующие выводы:
Было установлено, что представление данных — это характеристика, которая выражает правила кодирования элементов и формирования конструкций данных на конкретном уровне рассмотрения в вычислительной системе.
Было также отмечено, что единицей измерения информации служит бит: один ответ на вопрос типа «да-нет».
2. Проведен анализ кодирования данных
Решение данной задачи позволило сформулировать следующие выводы:
В ходе реализации данной задачи было установлено, что возможность для кодирования файла заключается в оптимизации двоичного кодирования его алфавита.
Можно констатировать, что двоичная сложность вопроса об индивидуализации произвольного элемента n-элементного множества не меньше чем log2 n.
Решение проблемы кодирования данных представляет не только научный, но и прикладной интерес и возможно с помощью оптимальных методов.
3. Исследованы основные методы кодирования данных
Решение данной задачи позволило сформулировать следующие выводы:
Рассмотренный метод Шеннона-Фано основан на представлении информации с помощью кода переменной длины, в котором символы, встречающиеся с большей частотой, кодируются кодом меньшей длины, а встречающиеся с большей частотой – кодом большей длины, используя таким образом избыточность сообщений, заключающуюся в неравномерном распределении частот символов, для кодирования. Было отмечено, что на сегодняшний день метод Шеннона-Фано практически не используется и представляет лишь исторический интерес.
Рассмотренный метод кодирования Хаффмана основан на построении дерева вероятностей. В столбце сортированных вероятностей складываются два последних значения. Полученный результат помещается в этот же столбец с учётом сортировки, а также записывается код прежней позиции слагаемых. Так продолжается до получения единственного элемента в столбце.
4. Проведено сравнение методов оптимального кодирования и изучено их развитие
Решение данной задачи позволило сформулировать следующие выводы:
Было отмечено, что методика Шеннона–Фано не всегда приводит к однозначному построению кода, т.к. построенный код может оказаться не самым лучшим. Методика Хаффмана гарантирует однозначное построение кода с наименьшим для данного распределения вероятностей средним числом символов на букву.
Метод PPM (prediction by partial matching) представляет собой метод контекстнозависимого моделирования ограниченного порядка. Он основан на оценке вероятности символа в зависимости от контекста, т.е. от символов, стоящих перед ним. Если для этой оценки используется контекст длины n, то говорят об использовании контекстноограниченной модели порядка n.
Метод PPM демонстрирует один из самых высоких коэффициентов кодирования, прежде всего, для текстов на естественном языке, что обуславливает весьма широкое его применение. Мы также можем предложить его использовать для кодирования текстов на естественном языке перед кодированием с помощью различных криптоалгоритмов, например, предложенных в работах. Недостатком метода PPM является медленное декодирование.