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

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

___________________

¹ Герасеймчук К.А. Кодирование. Основа кодирования: Учебник для вузов / К.А. Герасеймчук – СПб.: Питер, 2011. – 136 с.

Глава 2. Методы кодирования - сжатие или упаковка данных

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

Сжатие данных (data compression) – технический прием сокращения объема (размеров) записи данных на их носителе (жестком магнитном диске, дискете, магнитной ленте), реализуется разными методами, предпочтительно использующими кодирование (повторяющихся слов, фраз, символов). Выделяют две группы режимов сжатия данных – статическую и динамическую. Различают также виды сжатий:

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

Алгоритм Шеннона-Фано – один из первых алгоритмов сжатия, который впервые сформулировали американские ученые Шеннон и Роберт Фано. Данный метод сжатия имеет большое сходство с алгоритмом Хаффмана, который появился на несколько лет позже и является логическим продолжением алгоритма Шеннона.¹⁴

Далее рассмотрим подробнее алгоритмы Шеннона-Фано и Хаффмана.

___________________

¹¹ Шавенько Н.К. Основы теории информации и кодирования / Н.К. Шавенько. – М.: МИИГАиК, 2012. – 28 с.

⁷ Русанов К.Л. Приемы сокращения объемов информации / К.Л. Русанов. – М.: ЮНИТИ-ДАНА, 2013. – 58 с.

¹⁴ https://ru.wikipedia.org/wiki/

2.1. Алгоритм Шеннона-Фано

Суть алгоритма Шенона-Фано заключается в том, что все символы алфавита источника сообщений ранжируют, т.е. располагают в порядке убывания вероятностей их появления и при использовании двоичного кода объем алфавита элементов символов кода равен 2. Впоследствии символы алфавита делятся на две группы примерно равной суммарной вероятности их появления. Все символы первой группы в качестве первого элемента кодового символа получают «0», а все символы второй группы – «1». Дальше группы делятся на подгруппы, по тому же правилу примерно равных суммарных вероятностей, и в каждой подгруппе присваивается вторая позиция кодовых символов. Процесс повторяется до закодирования всех символов алфавита кодируемого источника сообщений. В кодовый символ, который соответствует последней группе, добавляется в качестве последнего элемента «0» для того, чтобы начальный элемент символов кода не совпадал с конечным, что позволяет исключить разделительные элементы между символами кода (см. Таблицу 2 – построения кода Шеннона-Фано на примере источника сообщений, алфавит которого состоит из восьми символов).

Таблица 2

Процесс построения кода Шеннона-Фано

Продолжение Таблицы 2

На рис. 2 представлен граф кодирования (кодовое дерево), показывающий, как «расщепляется» ранжированная последовательность символов кодируемого источника сообщений на группы и отдельные символы и какие кодовые символы присваиваются группам и отдельным символам алфавита источника сообщений на каждом шаге разбиения.

Рис. 2. Граф кодирования по алгоритму Шеннона-Фано

Алгоритм Шеннона-Фано применим и при иных числовых основаниях кода (k > 2). В этом случае алгоритм получения кода аналогичен рассмотренному примеру, только алфавит кодируемого источника сообщений разбивается на k групп и подгрупп примерно одинаковой суммарной вероятности.

Представляет интерес сравнение эффективного кодирования равномерным кодом и неравномерным кодом по алгоритму Шеннона-Фано.

В качестве примера рассмотрим предложенный выше (Табл. 2) источник сообщений с объемом алфавита равным 8 и соответствующими вероятностями появления отдельных символов (P_i). Для кодирования используем двоичный код ( k = 2).

Энтропия рассмотренного источника сообщений (H_и) определяется по формуле Шеннона-Фано:

Максимально же возможное значение энтропии источника сообщений

(H_u.max), при условии равновероятного и взаимно независимого появления символов, находится по формуле Хартли:

Следовательно, избыточность рассматриваемого источника сообщений (R_и) может быть найдена из соотношения:

Используя формулу для эффективного равномерного кода, при k = 2,

получим значность равномерного двоичного кода (п_р):

и избыточность равномерного кода (R_рк):

Энтропия элементов символов равномерного кода , то есть количество информации, приходящееся на один элемент символа кода, будет равна:

При использовании эффективного кодирования по алгоритму Шеннона-Фано соответствующие информационные параметры кода будут следующие.

Средняя длина неравномерного кода (п_Н) определяется выражением:

(1)

где п_i – значность i - го кодового символа, соответствующего символу алфавита m_i.

Избыточность неравномерного кода (R_НК) определим из соотношения:

(2)

Энтропия элементов символов эффективного неравномерного кода

может быть легко найдена:

(3)

Сравнивая выражения (1) и (3) видно, что, при использовании эффективного кодирования по алгоритму Шеннона-Фано, энтропия элементов символов такого неравномерного кода на 50% выше, чем энтропия элементов символов в случае использования равномерного кода. Предполагая, что скорость передачи по каналу элементов символов кода (W) одинакова для равномерного и неравномерного кода, то скорость передачи информации (V), определяемая выражением:

где Н – энтропия элементов символа кода, также будет на 50% выше при

использовании эффективного кодирования по алгоритму Шеннона-Фано по

сравнению с равномерным кодированием.

Алгоритм Шеннона-Фано часто применяют также и для блочного кодирования, где также существенно повышается эффективность кодирования. Для иллюстрации данного кодирования рассмотрим процедуру эффективного кодирования двоичным числовым кодом сообщений, генерируемых источником сообщений с объемом ал­фавита равным 2 (m = 2), то есть с алфавитом, который состоит только из двух символов m₁ и m₂ с вероятностями появления P(m₁) = 0,9 и P(m₂) = 0,1 и, следовательно, с энтропией Н = 0,47.

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

Осуществим кодирование блоков по алгоритму Шеннона-Фано, которые состоят из комбинаций двух символов источника сообщений, считая

симво­лы взаимнонезависимыми. Результат приведен в Таблице 3.

Таблица 3

Кодирование блоков по алгоритму Шеннона-Фано

Среднее число элементов символов кода на один символ исходного сообщения, вычисленное по формуле (2), равно 0,645, что значительно ниже, чем при посимвольном кодировании.

Кодирование блоков, соответствующих комбинациям из трех символов

источника сообщений, дает еще больший эффект. Результат приведен в Таблице 4.

Таблица 4

Кодирование блоков, соответствующих комбинациям

из трех символов источника сообщений

Продолжение Таблицы 4

В этом случае среднее число элементов символов кода на один символ исходного источника сообщений равно 0,53.

Теоретический минимум Н = 0,47 может быть достигнут при кодировании блоков неограниченной длины.

Алгоритм Шеннона-Фано не всегда приводит к однозначному построению кода, т.к. если разбивать группы на подгруппы, то можно сделать большей по суммарной вероятности как верхнюю, так и нижнюю подгруппы. Такого недостатка нет в алгоритме Хаффмена, гарантирующим однозначное построение эффективного кода.¹¹

2.2. Алгоритм Хаффмена

Алгоритм Хаффмана – скупой алгоритм оптимального префиксного кодирования алфавита с минимальной избыточностью. Он был разработан в 1952 году аспирантом Массачусетского технологического института Дэвидом Хаффманом при написании им курсовой работы. Данный алгоритм в настоящее время используется в многочисленных программах сжатия данных.